<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>
이진 검색 트리 (BST)
개요
이진 검색 트리(Binary Search Tree - BST)는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 이진트리의 일종으로서, 특정한 규칙을 통해 검색을 하는 자료구조다. 각 노드는 하나의 값을 가지며, 다음과 같은 특징이 있다.
- 왼쪽 노드의 값 ≤ 부모 노드의 값 ≤ 오른쪽 노드의 값
- 중복된 값을 갖는 노드가 존재하지 않음
- 이진 탐색 트리의 모든 서브 트리도 이진 탐색 트리
따라서 BST는 부모 노드보다 작거나 같은 모든 원소는 항상 왼쪽에 있고, 부모 노드보다 크거나 같은 원소는 항상 오른쪽에 있다. 이를 그림으로 나타내면 다음과 같다.
이러한 BST는 이름에 걸맞게 탐색 속도가 빠르다. BST는 높이에 따라 시간 복잡도가 결정되며, 이를 O(높이)로 표현할 수 있다. 일반적으로 이진 탐색 트리가 균형 잡혀있으면 대략 O(logN) 정도의 성능을 보이지만, 최악의 경우 트리의 높이가 N에 가까워져 검색 성능이 O(N)까지 떨어질 수 있다.
따라서 BST의 성능을 최적화하려면 트리의 높이가 최적화되어야 한다. 이를 위해 균형 잡는 과정이 필요하며, 이러한 과정을 통해 트리의 높이를 최소화하고 검색 성능을 향상할 수 있다. 이렇게 조정되어 편향성이 줄어든 이진 검색 트리를 높이-균형 이진 탐색 트리(height-balanced BST)라고 부른다.
본문
원소 검색
지금부터 이진 탐색 트리에서 원소를 검색하는 방법에 대해 알아보자. 중복되지 않는 양수를 원소로 갖는 BST가 다음과 같이 구성되어 있다고 가정해 보자.
여기서 숫자 3을 검색한다고 하면, 가장 상위 노드인 루트 노드부터 검색할 노드(3)와 차례대로 비교하면서 내려가면 된다. 즉, 다음과 같이 과정을 나눌 수 있다.
- 15와 3을 비교 → 왼쪽 노드
- 13과 3을 비교 → 왼쪽 노드
- 8과 3을 비교 → 왼쪽 노드
- 5와 3을 비교 → 왼쪽 노드 (탐색 완료)
이를 통해 BST에서 원소를 찾을 때, 트리의 모든 원소를 방문하지 않아도 된다는 것을 알 수 있다.
원소 삽입
이어서 위의 이진트리에서 새로운 수 9를 추가한다고 해보자. 새 원소를 삽입하기 위해선 삽입될 위치의 부모 노드를 찾아야 한다. 이 과정은 앞서 설명한 원소를 검색하는 과정을 이용하면 된다. 즉, 루트 노드부터 시작하여 각 노드를 추가할 원소와 비교하며 원소가 삽입될 위치로 이동하면 된다.
- 15와 9를 비교 → 왼쪽 노드
- 13과 9를 비교 → 왼쪽 노드
- 8과 9를 비교 → 오른쪽 노드
- 10과 9를 비교 → 왼쪽 노드
원소 삭제
BST에서 루트 노드인 15를 삭제한다고 해보자. 삭제 과정은 이전 검색, 삽입 과정과 다르게 복잡한 절차를 거친다. 노드 삭제 후 전체 트리가 BST 속성을 만족하도록 다른 적절한 노드로 삭제된 노드를 대체하는 과정이 필요하기 때문인데, 이를 세 가지 경우로 나눠서 따져봐야 한다.
- 자식 노드가 없는 경우: 해당 노드 삭제
- 자식 노드가 하나만 있는 경우: 노드 삭제 후, 부모 노드의 포인터가 해당 자식 노드를 가리키도록 조정
- 자식 노드가 두 개 있는 경우: 노두 삭제 후, 현재 노드를 후속 노드로 대체
여기서 후속 노드(successor)란 현재 노드보다 큰 값 중 가장 작은 값이다. 즉, 현재 노드의 오른쪽 서브트리로 이동한 후, 가장 작은 값이 후속 노드다. 앞서 작성한 BST에서는 16이 후속 노드가 된다.
요약
BST
1. 정의: 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 이진트리의 일종
2. 특징
a. 왼쪽 노드의 값 ≤ 부모 노드의 값 ≤ 오른쪽 노드의 값
b. 균형 잡혀 있는 트리의 경우 O(logN), 일반적으로 O(높이)로 탐색이 빠름
3. 기능
- 원소 삽입, 삭제, 탐색 등
'CS > 자료구조' 카테고리의 다른 글
| [자료구조] 힙 (2) | 2023.04.20 |
|---|---|
| [자료구조] 이진 탐색 트리 (2) - 구현 (0) | 2023.04.20 |
| [자료구조] 트리 순회(Tree traversal) (0) | 2023.04.17 |
| [자료구조] 트리(Tree) (0) | 2023.04.17 |
| [자료구조] 컨테이너 어댑터 (0) | 2023.04.03 |