하나 이상의 노드로 이루어진 유한집합으로, 하나의 루트 노드를 가지며 나머지 노드들은 루트의 서브트리로 분할된다.
- 원소들 간에 1:n 관계를 가지는 비선형 자료구조
- 원소들 간에 계층 관계를 가지는 계층형 자료구조
- 트리 구조는 재귀적
- 구성요소 : 노드(node), 간선(edge)
- 서브트리 : 하나의 노드와 그 노드들의 자손들로 이루어진 트리
- 노드의 차수 : 노드의 서브트리 개수 ( = 노드 밑으로 뻗어나간 간선의 수)
- 루트 노드 : 부모가 없는 최상위 노드
- 단말 노드 : 자식이 없는 노드 ( = 차수가 0 )
- 형제 노드 : 부모가 같은 자식들
- 트리의 차수 : 노드의 차수 최댓값
- 노드 레벨 : 트리의 각 층의 번호 (ex. 루트 노드 = 레벨 1)
- 트리의 높이 : 노드레벨의 최댓값
- 조상 : 루트까지의 경로상에 있는 모든 노드
각 노드의 자식은 최대 2개
각 노드가 가질 수 있는 자식의 수에 제한 X
모든 노드가 최대 2개(0~2개)의 서브트리를 가지는 트리
- 이진트리의 서브트리도 이진트리로 구성
트리의 각 레벨에 노드가 가득 차 있는 이진트리
-
깊이가 k일 때, 최대의 노드 개수인 2^k-1의 노드를 가진 이진트리
-
루트를 1번으로 하고, 레벨별로 왼쪽에서 오른쪽으로 번호 순차적으로 부여
레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져있는 이진트리
- 포화 이진트리와 노드 번호가 일치
- n개의 노드를 가진 완전 이진트리의 높이 = log2(n+1)
깊이가 k일 때, k개의 노드를 가지면서 모든 노드가 왼쪽이나 오른쪽 중 한 방향으로만 서브트리를 가지고 있는 이진트리
탐색을 효율적으로 하기 위한 자료구조
- 이진트리이며 모든 원소는 서로 다른 유일한 key를 가짐 (= 중복되는 값 X)
- 왼쪽 서브트리의 key 값 < 루트의 key값 < 오른쪽 서브트리의 key 값
- 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리