2.4.1 이진 검색 트리
이진 검색 트리(BST, Binary Search Tree)는 널리 사용되는 형태의 이진 트리입니다. BST는 다음과 같은 속성이 있습니다.
• 부모 노드의 값 ≥ 왼쪽 자식 노드의 값
• 부모 노드의 값 ≤ 오른쪽 자식 노드의 값
즉, (왼쪽 노드 ≤ 부모 노드 ≤ 오른쪽 노드)의 관계를 가집니다.
이러한 관계식은 재미난 특징이 있는데, 부모 노드보다 작거나 같은 모든 원소는 항상 왼쪽에 있고, 부모 노드보다 크거나 같은 원소는 항상 오른쪽에 있게 됩니다. 따라서 원소 검색을 위해 루트 노드부터 차례대로 값을 비교하는 경우, 각 단계마다 검색 범위가 절반으로 줄어듭니다.
BST가 마지막 레벨을 제외한 모든 노드에 두 개의 자식 노드가 있을 경우, 이 트리의 높이는 log2N이 됩니다. 여기서 N은 원소의 개수를 나타냅니다. 이로 인해 BST의 검색 및 삽입 동작은 O(log N)의 시간 복잡도를 갖습니다. 이러한 형태의 이진 트리를 완전 이진 트리(complete binary tree)라고 합니다.