이진 탐색 트리
최종 수정 : 25.1.2
이진 탐색 트리
1. 소개
이진 탐색 트리는 임의의 키를 가진 원소를 삽입 * 삭제 * 검색하는 데 효율적인 자료구조로 모든 연산은 키값을 기초로 실행한다. 이진 탐색 트리는 이진 트리이며, 공백이 아니면 모든 원소는 다른 키를 갖는다. 왼쪽 서브 틀 원소들의 키가 루트의 키보다 작고, 오른쪽 서브 트리 원소들의 키는 루트의 키보다 큰 값을 가진다.
2. 이진 탐색 트리의 탐색
이진 탐색 트리에서 키값이 X인 원소를 탐색하는 방법은 루트를 시작으로 탐색한다. 이진 탐색 트리가 공백이면 탐색은 종료한다. 탐색하는 노드가 탐색 키와 같으면 탐색이 성공하고 해당 포인터를 반환한다. 반면에 키값이 같지 않으면 현재 노드의 키값과 탐색 키값을 비교하여 탐색 키가 크면 오른쪽 서브 트리를 탐색하고, 탐색 키가 작으면 왼쪽 서브 트리를 탐색한다.
3. 이진 탐색 트리에 대한 삽입
이진 탐색 트리에서 키값이 X인 새로운 원소를 삽입하는 방법은 가장 먼저 X를 키값으로 가진 원소가 있는가를 탐색하고, 탐색이 실패하면 탐색이 종료된 위치에 원소를 삽입한다.
4. 이진 탐색 트리의 삭제
이진 탐색 트리에서의 원소의 삭제는 키값을 가진 원소를 탐색하고 원소를 찾으면 삭제 연산을 수행한다. 삭제 연산은 삭제 노드의 자식 수에 따라 세 가지 연산으로 나누어 볼 수 있다.
1) 자식이 없는 단노드의 경우
분드의 해당 링크 필드를 널(null)로 만들고 삭제한 노드를 반환한다.
2) 자노드가 하나인 경우
삭제되는 노드 자리에 그 자노드를 위치시키는 연산 과정이다. 삭제할 노드가 왼쪽이나 오른쪽 서브 트리 중 하나만 있는 경우에는 그 노드를 삭제하고 서브 트리를 부노드에 연결한다.
3) 자노드가 둘인 경우
자노드가 둘이면 자손 노드 중 후계자를 선택하고, 이진 탐색 트리를 재구성해야 한다. 후계자를 선택하는 방법으로는 왼쪽 서브 트리에서 제일 큰 원소를 선택하거나 오른쪽 서브 트리에서 제일 작은 원소로 대체한다.
5. 이진 탐색 트리의 높이
n개의 원소를 갖는 이진 탐색 트리의 높이는 최악의 경우 n이 될 수 있다. 편향 이진 트리가 그 예이다. 그러나 이진 탐색 트리의 평균적인 높이는 O(log2n)이다. 높이가 O(log2n)이 되도록 구성한 탐색 트리를 균형 탐색 트리(balanced search tree)라고 한다.
참고
독학사 교재