8. 이진 탐색 트리 (binary search tree)

1. 이진 탐색 (binary search) 복습

 

- 배열의 중앙값을 찾아서 배열을 반으로 분할하는 과정을 재귀적으로 반복하면서 key 값을 검색

이진 탐색 구조

 

*이진 트리와의 유사성

• 배열이 2개의 부분 배열로 재귀적으로 분할
• 분할 구조 - 배열 : (왼쪽 부분 배열) + 중앙 + (오른쪽 부분 배열)
•              - 이진 트리 : (왼쪽 부분 트리) + 부모 노드 + (오른쪽 부분 트리)
• 재귀적인 구조 - 각 부분 배열이 또 분할됨 , 각 부분 트리가 또 분할됨

 

2. 이진 탐색 트리 정의

 

* 이진 탐색 과정에서 분할되는 배열을 이진 트리에 대응시킨 구조

 

• 이진 트리
• 모든 노드는 서로 다른 하나의 값(key)을 저장
• 왼쪽 부분 트리의 모든 값들은 루트 노드의 값보다 더 작음
• 오른쪽 부분 트리의 모든 값들은 루트 노드의 값보다 더 큼
• 왼쪽 부분 트리와 오른쪽 부분 트리는 모두 이진 탐색 트리임

이진 탐색 트리 예시

 

3. 이진 탐색 트리의 연산

 

3-1. 생성 (초기화)

 

* 이진 탐색 트리의 자료 구조

포인토 기반 자료 구조

 

• root node를 선언
• 원소가 없는 이진 탐색 트리는 root node의 key를 원소로 사용되지 않을 값(예: -1)으로 초기화

 

3-2. 검색

 

* 3가지 경우

 

• x == key  -> Bingo!
• x < key  -> 왼쪽 서브 트리로 이동
• x > key  -> 오른쪽 서브 트리로 이동

이진 탐색 트리의 재귀호출을 이용한 검색 구현

 

 

 

3-2-1. 시간 복잡도

 

* 최선의 경우 (balanced)

• 이진 탐색 트리의 depth는 O(logn)임
• 최악의 경우 검색은 leaf node에서 끝남
• 따라서 시간 복잡도는 O(logn)

 

* 최악의 경우 (skewed)

 

• 이진 탐색 트리의 depth는 O(n)임
• 최악의 경우 검색은 leaf node에서 끝남
• 따라서 시간 복잡도는 O(n)

 

 

 

3-3. 추가

 

* 이진 탐색 트리에 새로운 원소를 더하는 연산

 

• 새로운 원소를 저장하는 노드를 생성하여 추가
• 새로 추가되는 노드는 반드시 leaf node임

 

* 추가 알고리즘 설계

 

3-3-1. 시간 복잡도 (n개의 노드)

 

* 최선의 경우 (balanced)

 

• 이진 탐색 트리의 depth는 O(logn)
• 추가는 항상 leaf node에서 끝
• 따라서 시간 복잡도는 O(logn)

* 최악의 경우 (skewed)

 

•  이진 탐색 트리의 depth는 O(n)임
•  추가는 항상 leaf node에서 끝
•  따라서 시간 복잡도는 O(n)

 

3-4. 제거

 

 

* 이진 탐색 트리의 노드를 지우는 연산

 

• 제거할 노드를 찾아가는 과정은 검색/추가와 비슷한 재귀적 구조로 구현
• 어떤 노드를 제거하느냐에 따라서 다른 연산 방법이 필요함 

* 제거 연산이 검색/추가 연산과 다른점

 

• 함수가 정수형의 리턴값을 갖음
• 노드는 자기 자신을 제거할 수 없어 부모 노드에게 자신을 제거해 달라고 요청
• 따라서 1의 경우 1을 리턴하여 부모에게 제거를 요청

 

*제거 알고리즘 설계

 

재귀적인 제거 구현

 

3-4-1. 시간 복잡도 (n 개의 노드)

 

* 최선의 경우 (balanced)

 

• 이진 탐색 트리의 depth는 O(logn)
• 제거는 항상 leaf node에서 끝
• 따라서 시간 복잡도는 O(logn)

* 최악의 경우 (skewed)

 

•  이진 탐색 트리의 depth는 O(n)임
•  제거는 항상 leaf node에서 끝
•  따라서 시간 복잡도는 O(n)

 

 

3-5. 성능 비교

 

자료구조			추가	제거	검색	최대값 찾기	최대값 제거
정렬된 배열			O(n)	O(n)	O(logn)	O(1)	O(n)
정렬된 연결리스트			O(n)	O(n)	O(n)	O(1)	O(1)
이진 탐색 트리		최선	O(logn)	O(logn)	O(logn)	O(logn)	O(logn)
		최악	O(n)	O(n)	O(n)	O(n)	O(n)

 

4. 균형 이진 탐색 트리

 

* Balanced Binary Search Tree (BBST)

 

• Self-balancing search tree
• Height-balanced search tree

* Height를 최소로 유지하도록 설계된 이진 탐색 트리

 

• AVL tree
• Red-black tree
• 2-3 tree
• B+ tree