(cs)이진 탐색 트리 (Binary Search Tree, BST)
이진 탐색 트리 (Binary Search Tree, BST)
1. 개념
이진 탐색 트리(Binary Search Tree, BST)는
이진 트리의 일종으로, 다음의 조건을 만족하는 트리 구조를 말한다.
- 모든 노드의 왼쪽 서브트리: 현재 노드의 값보다 작은 값을 가진 노드들로 구성
- 모든 노드의 오른쪽 서브트리: 현재 노드의 값보다 큰 값을 가진 노드들로 구성
이러한 규칙 덕분에 탐색(search), 삽입(insert), **삭제(delete)**를 효율적으로 수행할 수 있다.
2. 이진 탐색 트리 순회 방법 (Traversal)
트리의 모든 노드를 방문하는 방법을 **트리 순회(Tree Traversal)**라고 한다.
이진 탐색 트리에서는 주로 다음 세 가지 순회 방법을 사용한다.
(1) 중위 순회 (In-order Traversal)
"왼쪽 → 현재 → 오른쪽" 순서로 방문
- 왼쪽 서브트리를 재귀적으로 순회
- 현재 노드를 방문
- 오른쪽 서브트리를 재귀적으로 순회
특징:
BST에서 중위 순회를 수행하면 노드 값이 오름차순으로 출력된다.
(2) 전위 순회 (Pre-order Traversal)
"현재 → 왼쪽 → 오른쪽" 순서로 방문
- 현재 노드를 방문
- 왼쪽 서브트리를 재귀적으로 순회
- 오른쪽 서브트리를 재귀적으로 순회
특징:
트리 구조를 복원하거나 저장할 때 주로 사용한다.
(3) 후위 순회 (Post-order Traversal)
"왼쪽 → 오른쪽 → 현재" 순서로 방문
- 왼쪽 서브트리를 재귀적으로 순회
- 오른쪽 서브트리를 재귀적으로 순회
- 현재 노드를 방문
특징:
메모리 해제(삭제) 작업 등 하위 노드를 먼저 처리해야 할 때 사용한다.
3. 노드의 후임자(석세서, Successor)와 선임자(프레드세서, Predecessor)
(1) 후임자(Successor)
- 현재 노드보다 값이 큰 노드들 중 가장 작은 노드를 의미한다.
- 보통 오른쪽 서브트리의 최솟값이 후임자가 된다.
(2) 선임자(Predecessor)
- 현재 노드보다 값이 작은 노드들 중 가장 큰 노드를 의미한다.
- 보통 왼쪽 서브트리의 최댓값이 선임자가 된다.
4. 삽입, 삭제, 검색 연산
BST의 규칙(왼쪽은 작고 오른쪽은 크다)을 기반으로,
다음과 같은 기본 연산을 수행할 수 있다.
(1) 삽입 (Insertion)
- 루트 노드에서부터 시작하여,
- 삽입하려는 값이 현재 노드보다 작으면 왼쪽으로, 크면 오른쪽으로 이동
- 비어 있는 자리에 새로운 노드를 삽입한다.
시간복잡도: 평균 O(log N), 최악 O(N)
(2) 검색 (Search)
- 루트 노드에서부터 시작하여,
- 찾고자 하는 값이 현재 노드보다 작으면 왼쪽 서브트리로,
- 크면 오른쪽 서브트리로 이동하며 탐색한다.
시간복잡도: 평균 O(log N), 최악 O(N)
(3) 삭제 (Deletion)
삭제할 노드의 형태에 따라 세 가지 경우로 나뉜다.
- 자식 노드가 없는 경우 (Leaf Node)
- 해당 노드를 단순히 삭제한다.
- 부모 노드의 레퍼런스를 null로 설정.
- 자식 노드가 하나인 경우
- 삭제할 노드를 건너뛰고 자식 노드를 부모 노드와 연결한다.
- 자식 노드가 둘인 경우
- 삭제할 노드를 대체할 값을 찾는다.
- 보통 **오른쪽 서브트리에서 가장 작은 값(후임자)**을 찾는다.
- 삭제할 노드의 값을 후임자의 값으로 교체한 후,
- 후임자 노드를 삭제한다. (이때 후임자는 자식이 하나 이하라 삭제가 쉽다.)
- 삭제할 노드를 대체할 값을 찾는다.
특수 케이스: 루트 노드를 삭제할 경우에도 동일한 원칙을 적용한다.
5. 이진 탐색 트리의 장단점
장점
- 삽입과 삭제가 유연하다
- 레퍼런스(포인터)만 재조정하면 되므로 구조적 수정이 쉽다.
- 탐색이 빠르다 (평균 O(logN))
- 값의 크기에 따라 왼쪽/오른쪽으로 반씩 좁혀가므로 효율적이다.
- 값의 정렬된 순서에 따라 순회 가능
- 중위 순회를 이용하면 노드들이 오름차순으로 출력된다.
단점
- 최악의 경우 성능 저하
- 삽입 순서가 잘못되면 트리가 한쪽으로 편향(Degenerate)될 수 있다.
- 이 경우 트리가 사실상 **연결 리스트(Linked List)**처럼 변하여 탐색, 삽입, 삭제 모두 O(N)이 된다.
- 균형 유지 필요
- 성능 저하를 막기 위해 **자체적으로 균형을 잡는 이진 탐색 트리(AVL 트리, Red-Black 트리 등)**를 사용하기도 한다.
최종 정리
이진 탐색 트리는 간단하면서도 강력한 자료구조로,
정렬된 데이터를 빠르게 탐색하거나 삽입/삭제할 수 있는 기반을 제공한다.
그러나 트리의 균형이 깨질 경우 성능이 급격히 저하될 수 있기 때문에,
스스로 균형을 맞추는 트리(예: AVL, Red-Black 트리)와의 차이점도 이해하는 것이 중요하다.