Binary Search Tree란?
Binary Search Tree는 임의의 노드에 대해 왼쪽 서브 트리는 작은값, 오른쪽 서브 트리는 큰값으로 이루어져 있으며, 저장과 동시에 정렬이 수행되는 이진 트리입니다. 추가로, 검색, 추가, 삭제 등 연산 모두 O(log n)의 시간 복잡도를 가지고 있으며, 최악의 경우 O(n)입니다.
이제, 그림을 통해 살펴보겠습니다.
위 그림을 살펴보면 모든 임의의 노드에 대하여 왼쪽 서브 트리는 작은값, 오른쪽 서브 트리는 큰값으로 구성되어 있음을 확인할 수 있습니다.
이제 4를 추가하면 위 그림과 같이 대소비교(작으면 왼쪽, 크면 오른쪽으로 이동)를 수행하여 올바른 위치에 저장됩니다. 이 과정을 통해 트리의 노드를 왼쪽부터 정렬하면 다음과 같은 결과가 나오는 것을 알 수 있습니다.
이진 트리 vs 완전 이진 트리
이진 트리는 모든 노드는 최대 2개의 자식 노드를 가질 수 있다는 특징이 있습니다. 이를 기본으로 '마지막 레벨을 제외한 모든 노드가 존재', '노드는 왼쪽에서 오른쪽 방향으로 추가'를 추가로 만족하게 되면 완전 이진 트리가 됩니다. 즉, 이진 트리라는 기본적인 조건을 충족하고 추가로 만족하는 조건에 따라 '완전 이진 트리', '포화 이진 트리' 등으로 분류할 수 있습니다.
예상 질문
BST는 어떤 자료 구조인가요?
이진 트리로서 모든 임의의 노드에 대하여 왼쪽 서브 트리는 작은값, 오른쪽 서브 트리는 큰 값으로 이루어진 자료구조입니다. 또한, 검색, 추가, 삭제 등 연산 모두 O(log n)의 시간 복잡도를 가지고 있으며, 최악의 경우 O(n)입니다.
BST의 경우 Worst Case가 발생하는 경우와 시간 복잡도는 어떻게 되나요?
데이터 불균형으로 인해 한 방향으로만 노드들이 존재하는 경우를 최악의 경우라고 합니다. 원래 트리의 높이인 O(log n)의 시간 복잡도를 가지지만, 이 경우는 Linked-List와 같이 일렬로 나열된 형태이므로 O(n)의 시간 복잡도를 가집니다.
최악의 경우는 어떻게 해결하나요?
알고리즘을 사용해 최대한 높이를 최소로 유지하도록 하여 균형을 유지합니다. 이를 자가 균형 이진 탐색 트리라고 합니다. 대표적으로, AVL 트리와 Red-Black Tree가 있습니다.
