학교 수업 '자료구조' 복습입니다.
Binary Search Trees(BST)란?
- 다음 조건을 따르는 이진 트리이다.
1) 모든 노드는 유일한 키를 갖는다.
2) K라는 키를 갖는 노드의 왼쪽 subtree에 있는 모든 노드는 K보다 작은 키를 갖는다.
3) K라는 키를 갖는 노드의 오른쪽 subtree에 있는 모든 노드는 K보다 큰 키를 갖는다.
4) 모든 subtree는 BST이다.
BST as a Dictionary
| Implementation | Search | Insert/Remove |
| Sorted list(array) | O(log𝓃) | O(𝓃) |
| Unsorted list(array) | O(𝓃) | O(𝓃) |
| Binary Search Tree | O(𝑑) = O(log𝓃) (이상적인 경우) |
O(𝑑) = O(log𝓃) (이상적인 경우) |
*𝑑 : depth of the tree
1. BST Search
- 키가 x인 노드 찾기
1) 루트노드에서 시작
2) x와 루트노드의 키 rt.key와 비교해서(재귀)
- x = rt.key 이면 rt를 리턴
- x < rt.key 이면 rt의 왼쪽 subtree에서 다시 찾기
- x > rt.key 이면 rt의 오른쪽 subtree에서 다시 찾기
2. BST Insert
- 키가 x인 노드 넣기
1) BST Search를 실행한다.
- Search가 된다면 넣기 실패
2) 탐색을 실패한 위치에 x를 넣는다.
3. BST Remove
- 키가 x인 노드 삭제
1) BST Search를 실행한다.
- Search가 수행에 실패하면 삭제 실패
2) 찾은 노드를 지움
3) 다른 노드를 지운 자리로 옮겨줌 ﹥어떤 노드를 옮겨야하는가?
- 어떤 노드를 옮겨야 하는가?
왼쪽 subtree의 가장 오른쪽 노드 or 오른쪽 subtree의 가장 왼쪽 노드 - pseudo
1) Root 에서 시작
- x < rt.key 인 경우, x를 왼쪽 subtree에서 지움
- x > rt.key 인 경우, x를 오른쪽 subtree에서 지움
- x = rt.key 인 경우, rt를 지움
2) 지운 자리를 채우는 방법
- 왼쪽 자식이 없다면, 오른쪽 subtree가 현재 subtree를 대체한다.
- 오른쪽 자식이 없다면, 왼쪽 subtree가 현재 subtree를 대체한다.
- 양쪽 자식 모두 있다면, 오른쪽 subtree에서 가장 작은 키를 갖는 노드가 현재 subtree의 새로운 루트가 된다.
(가장 작은 키를 갖는 노드의 오른쪽 subtree가 가장 작은 키를 갖는 노드의 subtree를 대체한다.)
BST and Traversal
- BST에서 중위순위를 하면?
Sorted key values ( in increasing order)
Time Complexity of BST Operation(시간복잡도)
- Find : O(𝑑)
- Insert : O(𝑑)
- Removal : O(𝑑)
- 𝑑 : depth of the tree
'자료구조' 카테고리의 다른 글
| 5. [백준] 1991번 트리 순회 - 이진 트리 Binary Tree(3) (2) | 2022.09.26 |
|---|---|
| 5. 이진 트리 Binary Tree(2) (0) | 2022.09.19 |
| 5. 이진 트리 Binary Trees (0) | 2022.09.18 |
| 4. 트리 Tree (0) | 2022.09.18 |
| 3. 큐 Queues (0) | 2022.09.13 |