자료구조 - 트리 (tree)

트리형 구조는 개발하면서 많이 보지 못했다.
예에전에 이론 수업때 들었는데, 윈도우 탐색기 부터 지도에서 길찾기나 신호등 로직 등에 쓰이는 것으로 알고있다.
그래프에서도 비슷한 현상이 보이는데 나중에 차이점을 별도로 정리하겠다.

사전적인 의미로 트리(Tree)는 계층적인 자료를 표현하는 데 이용되는 자료구조이다.
트리형 구조이다보니 계층 모델을 띄며, 계층(hierarchy)이 중요한 개념이다.
트리는 노드들로 이루어져 있으며, 그림으로 표시할 때 나무 모양처럼 되어 트리라고 부른다.

트리구조를 배워두면 데이터를 계층 구조로 저장할 때 정리를 편하게 할 수 있다.

트리 자료구조의 구성요소

- 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
- 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
- 내부(internal) 노드: 단말 노드가 아닌 노드
- 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
- 형제(sibling): 같은 부모를 가지는 노드
- 크기(size): 자신을 포함한 모든 자손 노드의 개수
- 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
- 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
- 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
- 트리의 차수(degree of tree): 트리의 최대 차수
- 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

트리 종류

- 이진 트리(Binary Tree)
각 노드가 최대 두 개의 자식을 갖는 트리 (서브트리 포함)
모든 트리가 이진 트리는 아니다.

- 이진 탐색 트리(Binary Search Tree)
이진 트리에 조건이 더해진 것이다.
이진 탐색 트리는 모든 노드가 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드의 순서대로 값이 크다.
즉, 부모 노드보다 왼쪽 자식의 노드가 작다.
그리고 부모 노드보다 오른쪽 자식의 노드가 크다.
같은 데이터 값을 가지는 노드는 없다. (데이터 중복 X)

- 균형 트리
O(logN) 시간에 insert와 find를 할 수 있을 정도로 균형이 잘 잡혀 있는 경우
Ex) 레드-블랙 트리, AVL 트리