제 8 장 이진 탐색 트 리 8.1 이진 탐색 트리 정의 8.2 이진 탐색 트리의 탐색 8.3 이진 탐색 트리의 삽입 8.4 이진 탐색 트리의 삭제 8.5 높이 균형 이진 트리(AVL)

1. 정의 (1) 정의 * 아래의 성질을 만족하는 이진 트리로 삽입과 삭제가 비교적 효 율적인 자료구조 (2) 성질 ① 이진 탐색 트리 T의 왼쪽 서브 트리의 모든 노드들은 트리 T의 루트 노드의 키 값(kr)보다 작은 키 값을 갖는다.(kr > kls) ② 이진 탐색 트리 T의 오른쪽 서브 트리의 모든 노드들은 트리 T의 루트 노드의 키 값(kr)보다 큰 키 값을 갖는다.(kr < krs) ③ 이진 탐색 트리 T의 오른쪽 서브 트리와 왼쪽 서브 트리도 이진 탐색트리이다.

10개의 레코드 키 값 {25, 15, 9, 1, 18, 31, 11, 27, 33, 29}로 이진 탐색트리 구성 과정 ① 첫 번째 키 값 25를 루트, 두 번째 키 값 15는 루트보다 작으므로 왼쪽, 세 번째 키 값 9는 15보다 작으므로 15의 왼쪽에 위치 25 15 9 ② 키 값 1은 루트보다 작고 9보다 작으므로 왼쪽 노드에 삽입하고, 키 값 18은 루트보다 작고 15보다 크므로 오른쪽 노드에 삽입 25 15 9 18 1

④ 키 값 27는 루트보다 크므로 오른쪽 자식노드로 삽입, 자식노드 31보다 작으므로 왼쪽에 삽입 ③ 키 값 31는 루트보다 크므로 오른쪽 자식노드로 삽입, 11은 루트보다 작고, 15보다 작으므로 왼쪽 노드에 삽입하나, 키 값 9보다 크므로 오른쪽 노드에 삽입 25 15 31 9 18 1 11 ④ 키 값 27는 루트보다 크므로 오른쪽 자식노드로 삽입, 자식노드 31보다 작으므로 왼쪽에 삽입 25 15 31 9 18 27 1 11

⑤ 키 값 33는 루트보다 크므로 오른쪽 자식노드로 삽입, 자식노드 31보다 크므로 오른쪽에 삽입 25 15 31 9 18 27 33 1 11 ⑥ 키 값 29는 루트보다 크므로 오른쪽 자식노드로 삽입, 자식노드 31보다 작으므로 왼쪽에 삽입하나, 노드 27보다 크므로 오른쪽 자식으로 삽입 25 15 31 9 18 27 33 1 11 29

2. 이진 탐색 트리의 탐색 (1) 탐색방법 ① 현재 서브 트리의 루트 노드의 키 값을 비교한다. ② 루트 노드의 키 값과 검색하고자 하는 키 값이 같으면 루트 노드의 키 값을 반환한다. ③ 루트 노드의 키 값보다 검색 키 값이 작으면 왼쪽 서브 트리를 탐색한다. ④ 루트 노드의 키 값보다 검색 키 값이 크면 오른쪽 서브 트리를 탐색한다.

(2) 알고리즘 bstree_node *binary_search_tree(tree, key) bstree_node *tree; char key; { bstree_node *ptr; boolean found; ptr = tree; found = FALSE; while((ptr ! = NULL) && (!found)) { result = compare(key, ptr→data) switch(result) { case '<' : ptr = ptr→lchild; break; case '=' : found = TRUE; break; case '>' : ptr = ptr→rchild; break; } return ptr;

3. 이진 탐색 트리의 삽입 (1) 삽입과정 이진 탐색 트리의 삽입은 항상 단말 노드에서 일어난다. ① 트리 T가 비어 있는 트리라 하면, 삽입노드는 트리 T의 루트 노드가 된다. ② 트리 T가 비어 있지 않은 트리라 하면, 루트 노드의 키 값(ki)과 삽입노드의 키 값을 비교한다. · 만일 ki > k이면, 노드의 왼쪽 서브트리에서 적당한 위치를 탐색하여 키 k를 삽입한다. · 만일 ki < k이면, 노드의 오른쪽 서브트리에서 적당한 위치를 탐색하여 키 k를 삽입한다.

(2) 알고리즘 bstree_node *bst_insert(x, ptr) bstree_node *ptr; char x; { if(ptr == NULL){ ptr = getNode(); ptr→data = x; ptr→lchild = NULL; ptr→rchild = NULL; } else if(x < ptr→data) bst_insert(x, ptr→lchild); else bst_insert(x, ptr→rchild);

T T 23 23 18 44 18 44 35 12 20 35 12 20 52 52 19 (a) 19의 삽입 전 (b) 19의 삽입 후 T T 23 23 44 18 44 18 12 20 35 52 12 20 35 52 19 19 38 (c) 38의 삽입 전 (d) 38의 삽입 후

4. 이진 탐색 트리의 삭제 (1) 정의 트리의 임의의 위치에서 수행된다. 노드의 삭제는 삭제되는 노드의 부모 노드 위치를 찾아 링크를 수정하여 이진 탐색 트리의 성질을 만족하도록 한다. (2) 삭제과정 ① 단말 노드의 삭제 T T 23 23 삭제노드 18 44 18 44 12 20 35 52 12 20 52 삭제 후 트리

② 하나의 자식 노드를 갖는 노드의 삭제 ③ 두 개의 자식 노드를 갖는 노드의 삭제 삭제 후 트리 삭제 후 트리 삭제하고자 하는 노드의 부모 노드로 하여금 삭제될 노드의 자식 노드를 카리키도록 함으로서 삭제 수행 T T 삭제노드 23 23 18 44 12 44 삭제 후 트리 12 35 52 35 52 ③ 두 개의 자식 노드를 갖는 노드의 삭제 삭제 후에도 탐색 이진 트리의 성질을 만족해야 한다. 왼쪽 서브트리의 가장 큰 원소 또는 오른쪽 서브트리의 가장 작은 원소를 삭제 노드 위치에 대체 삽입 후 노드 삭제 T T 삭제노드 23 23 18 44 19 44 삭제 후 트리 12 21 35 52 12 21 35 52 ① 대체 19 22 20 22 ② 21의 왼쪽 자식노드 20

(2) 이진 탐색 트리가 좋은 탐색 효율을 보이기 위해서는 루트 노드를 중심으로 오른쪽 서브트리와 왼쪽 서브트리가 대칭을 이루고, 레벨이 거의 같은 경우가 되어야 한다. 5. 높이 균형 이진 트리(AVL : Adelson-Velskii & Landis) (1) 정의 서브 트리들의 높이에서 균형을 이루는 이진 트리이며, 삽입과 삭제 연산이 수행된 후에 트리의 높이는 균형을 이루게 된다. ① 공백 트리는 높이가 균형을 이룬다. ② T를 이진 트리라하고, Tl과 Tr를 각각 왼쪽 서브트리와 오른쪽 서브트리로 갖는다면 T는 다음 조건을 만족한다. · Tl와 Tr의 높이가 균형을 이룬다. · hl과 hr을 각각 서브 트리 Tl, Tr의 높이라 하면, | hl - hr | ≤ 1

h i k l n j m d f g e a B c (a) 높이 균형 트리(AVL트리) h i k l j n m o (b) 높이 불균형 트리