용어

루트 : 트리의 가장 윗 부분에 위치하는 노드

레벨 : 루트로부터 얼마나 떨어져 있는지 _아래로 한 단계 ⇒ +1레벨

리프 : 트리의 가장 아래에 위치해 자식이 없는 노드

높이 : 루트에서 리프까지의 거리

이진트리

각 노드가 두 개의 자식노드(오른쪽, 왼쪽)를 갖는 트리

완전이진트리

• 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 채워진 이진트리
• 높이가 $n$일 때, 노드 개수의 최댓값은 $2ⁿ-1$
• 따라서 $k$개의 노드를 저장할 수 있는 완전이진트리의 높이는 $log$ $k$

포화이진트리

• 완전이진트리에서 위에서 아래, 왼쪽에서 오른쪽으로 끝까지 채워진 트리

이진검색트리