이진 탐색 트리 (Binary Search Tree) 핵심 메커니즘과 복잡도

이진 트리와 이진 탐색 트리의 원리

이진 트리(binary tree)란 각 노드에 최대 두 개의 자식 노드가 있는 트리 자료 구조다. 이진 탐색 트리(binary search tree)란 정렬된 이진 트리로서 모든 노드는 자신의 왼쪽 브랜치 노드들보다 큰 값을 갖고, 오른쪽 브랜치 노드들보다 작은 값을 갖는 특징을 가진다.

탐색 대상 키와 트리 구조(균형 트리 vs 편향 트리)에 따라 노드 비교 및 분기 경로가 어떻게 달라지는지 확인할 수 있다.

시간 복잡도와 균형 트리의 필요성

이진 탐색 트리의 조회 성능은 균형 트리일 때 $O(\log n)$이지만, 한쪽으로 치우친 편향 트리(unbalanced)일 경우 최악 $O(n)$으로 저하된다. 이를 방지하기 위해 AVL 트리나 레드-블랙 트리(Red-Black Tree)와 같은 자가 균형 트리를 사용하여 성능을 개선한다.