이진 탐색 트리

3. 구조

이진 트리의 일종으로, 각 노드는 최대 두 개의 자식 노드를 가질 수 있다. "왼쪽 자식 노드의 값 ≤ 부모 노드의 값 ≤ 오른쪽 자식 노드의 값"과 같은 강한 전순서 관계를 만족하도록 구성되어야 한다.^[9][10] 실제 구현에서는 중복된 값의 처리를 위해 한쪽에 등호를 포함시키는 방식으로 통일한다. (예: "왼쪽 자식 노드의 값 < 부모 노드의 값 ≤ 오른쪽 자식 노드의 값")

4. 연산

이진 탐색 트리는 검색, 삽입, 삭제, 후임자 및 선임자 찾기와 같은 주요 연산을 지원한다. 이러한 연산은 트리의 구조와 속성을 유지하면서 수행된다. 각 연산에 대한 자세한 내용은 하위 섹션에서 다룬다.

4. 1. 검색

• 값이 같으면 검색 성공, 해당 노드를 반환한다.
• 검색하려는 값이 현재 노드의 값보다 작으면 왼쪽 서브트리를 검색한다.
• 검색하려는 값이 현재 노드의 값보다 크면 오른쪽 서브트리를 검색한다.

4. 1. 1. 후임자와 선임자

노드의 최대값 또는 최소값인 키를 가진 노드를 찾는 연산은 노드의 후임자와 선임자를 결정하는 연산과 같이 특정 연산에서 매우 중요하다.^[1]

4. 2. 삽입

• "삽입할 값 < 현재 노드"이면 왼쪽 자식을 다음 노드로 지정한다.
• "현재 노드 ≤ 삽입할 값"이면 오른쪽 자식을 다음 노드로 지정한다.

위 코드는 'x'의 부모 노드를 가리키는 'y'를 유지한다. 만약 'y'가 NIL이면, 트리가 비어있다는 뜻이므로 'z'를 루트 노드로 삽입한다. 'y'가 NIL이 아니면, 키 값을 비교하여 'y'의 왼쪽 또는 오른쪽에 노드를 삽입한다.^[10]

삽입 연산의 시간 복잡도는 트리의 높이에 비례한다. 균형 잡힌 트리의 경우 O(log N)이지만, 최악의 경우(편향된 트리)에는 O(N)이 될 수 있다.

4. 3. 삭제

• 자식 노드가 없는 노드(리프 노드) 삭제: 해당 노드를 단순히 삭제한다.
• 자식 노드가 1개인 노드 삭제: 해당 노드를 삭제하고 그 위치에 해당 노드의 자식 노드를 대입한다.
• 자식 노드가 2개인 노드 삭제: 삭제하고자 하는 노드의 값을 해당 노드의 왼쪽 서브트리에서 가장 큰 값으로 변경하거나, 오른쪽 서브트리에서 가장 작은 값으로 변경한 뒤, 해당 노드(왼쪽 서브트리에서 가장 큰 값을 가지는 노드 또는 오른쪽 서브트리에서 가장 작은 값을 가지는 노드)를 삭제한다.

• 삭제 노드의 왼쪽 자식에서 최대값을 탐색한다.
• 1에서 탐색해온 노드(이하 탐색 노드)를 삭제 대상 노드로 대체하고, 삭제 대상 노드를 삭제한다. 이때 탐색 노드의 왼쪽 자식을 탐색 노드의 원래 위치로 옮겨둡니다(이진 탐색 트리의 특성상, 탐색 노드는 오른쪽 자식을 가지지 않는다).

5. 순회

이진 탐색 트리는 중위, 전위, 후위의 세 가지 기본 알고리즘을 통해 순회할 수 있다.^[10]

• '''중위 트리 순회''': 왼쪽 서브트리의 노드가 먼저 방문되고, 그 다음 루트 노드, 마지막으로 오른쪽 서브트리가 방문된다. 이러한 순회는 키 시퀀스가 증가하지 않는 순서대로 모든 노드를 방문한다.
• '''전위 트리 순회''': 루트 노드가 먼저 방문되고, 그 다음 왼쪽 및 오른쪽 서브트리가 방문된다.
• '''후위 트리 순회''': 왼쪽 서브트리의 노드가 먼저 방문되고, 그 다음 오른쪽 서브트리, 마지막으로 루트가 방문된다.

재귀 호출을 사용하여 이진 탐색 트리에 등록된 모든 데이터를 정렬된 순서로 열거할 수 있다.

# 왼쪽 자식을 루트로 하는 서브트리에 대해 이 처리를 재귀적으로 적용한다.

# 부모를 표시한다.

# 오른쪽 자식을 루트로 하는 서브트리에 대해 이 처리를 재귀적으로 적용한다.

삽입 시에 동일한 값을 오른쪽 자식에 등록해두면 안정 정렬이 된다.

6. 균형 이진 탐색 트리

이진 탐색 트리에서 삽입 또는 삭제를 수행할 때, 재균형 작업이 없으면 트리의 높이가 노드의 수($n$)만큼 커져서 검색 성능이 선형 검색 수준으로 나빠질 수 있다.^[14] 탐색 트리를 균형 있게 유지하고 높이를 $O(\backslash log\; n)$으로 제한하는 것은 이진 탐색 트리가 제 기능을 하도록 만드는 데 매우 중요하다. 이는 트리에 대한 업데이트 작업 중에 "자가 균형" 메커니즘을 통해 달성할 수 있으며, 이 메커니즘은 트리의 높이를 이진 로그 복잡도로 유지하도록 설계되었다.^[4][15]

트리가 높이 균형을 이루려면 왼쪽 서브 트리와 오른쪽 서브 트리의 높이가 상수 인자만큼 차이가 나야 한다. 이 속성은 AVL 트리에서 처음 도입되었고 레드-블랙 트리에서 이어졌다. 트리에 대한 모든 삽입 및 삭제 연산에서 루트에서 수정된 리프 노드까지의 경로에 있는 모든 노드의 높이를 확인하고, 필요하다면 수정해야 한다.

가중치 균형 트리에서 균형 트리의 기준은 하위 트리의 리프(leaf) 수이다. 왼쪽 및 오른쪽 하위 트리의 가중치는 최대 $1$만큼 차이가 난다.^[16] 그러나 차이는 가중치 비율 $\backslash alpha$에 의해 제한되는데, $1$의 강력한 균형 조건은 삽입 및 삭제 연산 중에 $O(\backslash log\; n)$ 재균형 작업을 유지할 수 없기 때문이다. $\backslash alpha$-가중치 균형 트리는 전체 균형 조건 집합을 제공하며, 각 왼쪽 및 오른쪽 하위 트리는 하위 트리의 총 가중치의 $\backslash alpha$ 분율 이상을 갖는다.

T-트리,^[17] 트리프,^[18] 레드-블랙 트리,^[19] B-트리,^[20] 2-3 트리,^[21] 및 스플레이 트리와 같은 여러 가지 자체 균형 이진 탐색 트리가 있다.^[22]

균형 이진 탐색 트리는 데이터의 출현 순서에 따라 성능이 크게 저하되지 않도록 삽입, 삭제 시 트리의 균형을 다시 잡는 처리를 추가한 이진 탐색 트리이다.

7. 응용

이진 탐색 트리는 모든 요소를 한 번에 삽입하고 트리를 중위 순회하는 트리 정렬과 같은 정렬 알고리즘에 사용된다.^[23] BST는 퀵 정렬에도 사용된다.^[24]

이진 탐색 트리는 노드의 키를 우선순위로 사용하여 우선순위 큐를 구현하는 데 사용된다. 큐에 새로운 요소를 추가하는 것은 일반적인 BST 삽입 연산을 따르지만, 제거 연산은 우선순위 큐의 유형에 따라 다르다.^[25]

• 오름차순 우선순위 큐의 경우: 가장 낮은 우선순위를 가진 요소 제거는 BST의 왼쪽 탐색을 통해 수행된다.
• 내림차순 우선순위 큐의 경우: 가장 높은 우선순위를 가진 요소 제거는 BST의 오른쪽 탐색을 통해 수행된다.

참조

_[1] 논문 Explaining the Behaviour of Binary Search Trees Under Prolonged Updates: A Model and Simulations https://academic.oup[...] 1989-01-01
_[2] 논문 Analysis of the standard deletion algorithms in exact fit domain binary search trees https://link.springe[...] Springer Publishing, University of Waterloo 1986-07-28
_[3] 논문 Trees, Forests and Rearranging https://academic.oup[...] 1960-01-01
_[4] 서적 The Art of Computer Programming https://ia801604.us.[...] Addison-Wesley
_[5] 문서 red-black tree https://www.nist.gov[...] 2019-11-12
_[6] 웹사이트 CS 312 Lecture: AVL Trees https://www.cs.corne[...] Cornell University, Department of Computer Science 2022-05-19
_[7] 논문 An algorithm for the organization of information https://zhjwpku.com/[...]
_[8] 웹사이트 CSC263: Balanced BSTs, AVL tree http://www.cs.toront[...] University of Toronto, Department of Computer Science 2022-05-19
_[9] 서적 Data Structures Using C https://global.oup.c[...] Oxford University Press 2018-10-13
_[10] 서적 Introduction to Algorithms https://mitpress.mit[...] MIT Press
_[11] 논문 A Short Note on Binary Search Trees https://academic.oup[...] Oxford University Press 1982-02-01
_[12] 웹사이트 Design and Analysis of Algorithms https://ranger.uta.e[...] University of Texas at Arlington 2021-05-17
_[13] 웹사이트 Binary Search Tree https://cs.lmu.edu/~[...] Loyola Marymount University, Department of Computer Science 2022-05-17
_[14] 웹사이트 ICS 46: Binary Search Trees https://www.ics.uci.[...] University of California, Irvine 2021-10-21
_[15] 서적 Advanced Data Structure https://www.cambridg[...] Cambridge University Press 2011-01-01
_[16] 논문 On the Average Number of Rebalancing Operations in Weight-Balanced Trees http://scidok.sulb.u[...]
_[17] 간행물 A Study of Index Structures for Main Memory Database Management Systems https://archive.org/[...] 1986-08-25
_[18] 간행물 30th Annual Symposium on Foundations of Computer Science IEEE Computer Society Press
_[19] 서적 Introduction to Algorithms MIT Press
_[20] 논문 The Ubiquitous B-Tree 1979-06-01
_[21] 서적 The Art of Computer Programming Addison Wesley
_[22] 논문 Self-Adjusting Binary Search Trees https://www.cs.cmu.e[...]
_[23] 웹사이트 COS226: Binary search trees https://www.cs.princ[...] Princeton University School of Engineering and Applied Science 2021-10-21
_[24] 웹사이트 A Connection Between Binary Search Trees and Quicksort http://mathcenter.ox[...] Oxford College of Emory University, The Department of Mathematics and Computer Science 2022-06-04
_[25] 웹사이트 CS 2112 Lecture and Recitation Notes: Priority Queues and Heaps https://www.cs.corne[...] Cornell University, Cornell University College of Engineering 2021-10-21