탐색 효율을 높이기 위해 규칙을 부여한 트리 구조인 이진 탐색 트리(Binary Search Tree, BST)의 원리를 정리했다.
BST 탐색 메커니즘 (Java)
BST는 루트 노드부터 크기를 비교하며 탐색 범위를 좁혀나간다.
public Node search(Node root, int key) {
// 탐색 성공 또는 종단 도달 시 반환
if (root == null || root.value == key) return root;
// 키 값 비교를 통한 탐색 방향 결정
if (key < root.value) return search(root.left, key);
return search(root.right, key);
}
비교 시마다 탐색 범위가 감소하여, 트리의 균형 유지 시 O(log N)의 속도로 탐색이 가능하다.
BST의 3대 규칙
- 왼쪽 서브트리: 부모 노드보다 작은 값들로 구성된다.
- 오른쪽 서브트리: 부모 노드보다 큰 값들로 구성된다.
- 재귀적 구조: 모든 서브트리 역시 BST 규칙을 준수해야 한다.
성능과 균형의 관계
BST의 성능은 트리의 형태에 의존한다.
데이터가 편향되게 삽입되어 트리가 한쪽으로 치우칠 경우 연결 리스트와 동일한 O(N)의 성능으로 저하된다.
이를 보완하기 위한 AVL 트리나 레드-블랙 트리와 같은 자가 균형 트리의 중요성을 확인했다.
효율적인 데이터 탐색을 위해 구조적 균형이 필수적인 것 같다.
