13. 탐색트리 AVL 트리, B- 트리, 2-3-4 트리
정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2
이진탐색트리의예 3
BST 의최선과최악의경우 4
BST 성능 이진탐색트리의삽입과탐색 B(n) = Θ(1) A(n) = Θ(lg n) W(n) = Θ(n) BST 탐색과삽입알고리즘에대한평균시간복잡도 A( n) (1.39lg n) (lg n) 5
AVL 트리 13.5 AVL 트리 어떤노드에서도두서브트리가거의같은높이를갖도록강제하여균형을유지하는이진탐색트리 불균형이발생할때마다서브트리를회전하여균형을맞추어줌 AVL 트리를발명한 Adelson-Velskii 와 Landis 의이름을땀 Average and worst case: O(log 2 n) AVL 회전의패턴 왼쪽단순회전 오른쪽단순회전 복합오른쪽-왼쪽회전 복합왼쪽-오른쪽회전 6
AVL 트리 (2) Height balanced tree 공백트리 (empty tree) 는높이균형을이룬다. T 가왼쪽서브트리 T L 과오른쪽서브트리 T R 을가진공백이아닌이진트리라고할때, - T 는높이균형을이룬다 iff 1) T L 과 T R 이높이균형을이룬다 2) h L - h R 1 (h L 과 h R 은각각 T L 과 T R 의높이 )
AVL 특성 AVL 트리가아님 : AVL 트리임 : 8
AVL TREES Def) 노드 T 의 balance factor, BF(T) h L - h R (h L 과 h R 은각각왼쪽서브트리 T L 과오른쪽서브트리 T R 의높이 ) AVL 트리의임의의노드 T 에대해 BF(T) = -1, 0, or 1 트리가균형을잃게될때, 트리릐균형을맞추기위해회전 (rotation) 을수행한다
AVL 회전의패턴 왼쪽단순회전 rotateleft() 호출 오른쪽단순회전 rotateright() 호출 복합오른쪽 - 왼쪽회전 복합왼쪽 - 오른쪽회전 10
왼쪽회전알고리즘 (1) x 에대해왼쪽으로회전 x 에대해왼쪽으로회전 11
왼쪽회전알고리즘 (2) x 에대해왼쪽으로회전 x 에대해왼쪽으로회전 12
이중회전알고리즘 (1) y 에대해오른쪽으로회전 x 에대해왼쪽으로회전 13
이중회전알고리즘 (2) y 에대해오른쪽으로회전 x 에대해왼쪽으로회전 14
13.6 AVL 트리의구현 (1) An AVLTree class 1 public class AVLTree { 2 private int key, height; 3 private AVLTree left, right; 5 public static final AVLTree NIL = new AVLTree(); 7 public AVLTree(int key){ 8 this.key = key; 9 left = right = NIL; 10 } 12 public boolean add(int key) { // 주어진키를추가하는데 13 int oldsize = size(); // 성공하면 true 리턴 14 grow(key); 15 return size()>oldsize; 16 } 15
18 public AVLTree grow(int key) { 19 if (this == NIL) return new AVLTree(key); 20 if (key == this.key) return this; // prevent key duplication 21 if (key < this.key) left = left.grow(key); 22 else right = right.grow(key); 23 rebalance( ); 24 height = 1 + Math.max(left.height,right.height); 25 return this; 26 } 28 public int size() { 29 if (this == NIL) return 0; 30 return 1 + left.size() + right.size(); 31 } 33 public String tostring() { 34 if (this == NIL) return ""; 35 return left + " " + key + " " + right; 36 } 16
38 private AVLTree() { // constructs the empty tree 39 left = right = this; 40 height = -1; 41 } 43 private AVLTree(int key, AVLTree left, AVLTree right) { 44 this.key = key; 45 this.left = left; 46 this.right = right; 47 height = 1 + Math.max(left.height, right.height); 48 } 50 private void rebalance() { 51 if (right.height > left.height+1) { 52 if (right.left.height > right.right.height) right.rotateright(); 53 rotateleft(); 54 } 17
55 else if (left.height > right.height+1) { 56 if (left.right.height > left.left.height) left.rotateleft(); 57 rotateright(); 58 } 59 } 60 61 private void rotateleft() { 62 left = new AVLTree(key, left, right.left); 63 key = right.key; 64 right = right.right; 65 } 66 67 private void rotateright() { 68 right = new AVLTree(key, left.right, right); 69 key = left.key; 70 left = left.left; 71 } 72 } 18
회전이있는 AVL 삽입 35 삽입 오른쪽회전 왼쪽회전 19
13.7 다원탐색트리 차수가 d 인다원탐색트리 (d-way search tree) 그것의노드의차수가 <= d 차수가 d 인노드는 d-1 개의키 (k 0,k 1,,k d-2 ), d-1 개의주소 (a 0,a 1,,a d-2 ), d 개의서브트리 (T 0,T 1,,T d-1 ) 를가진다만일 x 0, x 1, x 2,, x d-1 을각서브트리에있는키라고하면 x 0 <k 0 <x 1 <k 1 <x 2 <k 2 < x d-2 <k d-2 <x d-1 임 20
13.9 B- 트리 차수가 m인 B-트리 차수가 m인다원탐색트리 (MST-multiway search tree): 그것의노드의차수가 <= m 모든리프노드는동일한레벨에있음 루트가아닌모든내부노드는최소한의차수를가짐 m / 2 21
B- 트리의크기에대한범위 2 h h m/ 2 1 n m 1 1 B- 트리의높이에대한범위 h log m / 2 n (lg n) B- 트리 (2) B- 트리는데이터베이스테이블을위한외부인덱스를구현하는데사용되는표준자료구조이다. 각각의키는레코드에대한디스크주소를가지고있다. B- 트리의차수는각노드가하나의디스크블럭에저장될수있는값으로선택된다. 따라서어떤레코드를접근하기위한디스크판독횟수는 h+2 를넘지않는다. 22
B- 트리의예 972 년 R. Bayer 와 E. McCreight 에의해개발되었다 차수 m=? 높이 h=? 크기 n=? 23
차수가 3 인 B- 트리로의삽입 8 4 15 20 1 3 5 6 9 16 17 30 40 Insert a pair with key = 2. New pair goes into a 3-node.
B- 트리분할알고리즘 B- 트리분할연산 포화노드는하나의단독노드 A 와이것의두자식이되는두개의반 - 포화 (half-full) 노드 B 와 C 로교체됨 A 에있는하나의원소는원래노드에있는키의중앙값이다. 25
Insert 8 2 4 15 20 1 3 5 6 9 16 17 30 40 Insert a pair with key = 2 plus a pointer into parent.
Insert 8 2 4 15 20 1 3 5 6 9 16 17 30 40 Now, insert a pair with key = 18.
Insert 8 2 4 15 20 1 3 5 6 9 16 17 30 40 Insert a pair with key = 18.
Insert 8 17 2 4 15 20 18 1 3 5 6 9 16 30 40 Insert a pair with key = 17 plus a pointer into parent.
Insert 8 17 2 4 15 20 1 3 5 6 9 16 18 30 40 Insert a pair with key = 17 plus a pointer into parent.
Insert 8 17 2 4 15 20 1 3 5 6 9 16 18 30 40 Now, insert a pair with key = 7.
Insert 8 17 6 7 2 4 15 20 1 3 5 9 16 18 30 40 Insert a pair with key = 6 plus a pointer into parent.
Insert 8 17 4 6 2 15 20 1 9 3 16 18 30 40 5 7 Insert a pair with key = 4 plus a pointer into parent.
Insert 4 8 17 2 6 15 20 1 3 5 7 9 16 18 30 40 Insert a pair with key = 8 plus a pointer into parent. There is no parent. So, create a new root.
Insert 8 4 17 2 6 15 20 1 3 5 7 9 16 18 30 40 Height increases by 1.
B- 트리삽입알고리즘 입력 : B- 트리 T 와키 - 주소쌍 (x,y). 출력 : 만일 T 가변경되었으면 true, 아니면 false. 후조건 : 키 - 주소쌍 (x,y) 는트리 T 에존재. 1. 만일 T 가공백이면, 키 - 주소쌍 (x,y) 를포함하는단독트리로교체하고 true 를리턴. 2. x 를가지고있는리프노드 p 를찾기위해다원탐색알고리즘을적용. 3. 만일 x 가 p 에있고그것의주소가 y 이면, false 를리턴. 4. 만일 x 가 p 에있고그것의주소가 y 가아니면, 그주소를 y 로교체하고 true 를리턴. 5. 만일 x 가 p 에없으면, 키 - 주소쌍 (x,y) 를삽입. 6. 만일 p 가오버플로되면, 그것을분할. 7. true 를리턴. 36
차수가 3 인 B- 트리에서 Delete 8 2 4 15 20 1 3 5 6 9 16 17 30 40 Delete the pair with key = 8. Transform deletion from interior into deletion from a leaf. Replace by smallest in right subtree.
Delete From A Leaf 8 2 4 15 20 1 3 5 6 9 16 17 30 40 Delete the pair with key = 16. 3-node (node with degree 3) becomes 2-node.
Delete From A Leaf 8 2 4 15 20 1 5 6 30 40 9 3 17 Delete the pair with key = 17. Deletion from a 2-node. Check one sibling and determine if it is a 3-node. If so borrow a pair and a subtree via parent node.
Figure 11.7 Rotation in a 2-3 tree
Delete From A Leaf 8 2 4 15 30 1 3 5 6 9 20 40 Delete the pair with key = 20. Deletion from a 2-node. Check one sibling and determine if it is a 3-node. If not, combine with sibling and parent pair.
Delete From A Leaf 8 2 15 1 4 5 9 40 Delete the pair with key = 40. Deletion from a 2-node. Check one sibling and determine if it is a 3-node. If not, combine with sibling and parent pair.
Delete From A Leaf 8 2 1 4 5 9 15 Parent pair was from a 2-node. Check one sibling and determine if it is a 3-node. If not, combine with sibling and parent pair.
Delete From A Leaf 2 8 1 4 5 9 15 Parent pair was from a 2-node. Check one sibling and determine if it is a 3-node. No sibling, so must be the root. Discard root. Left child becomes new root.
Delete From A Leaf 2 8 1 4 5 9 15 Height reduces by 1.
B- 트리삭제알고리즘 입력 : B- 트리 T 와키 x. 출력 : 만일 T 가변경되었으면 true, 아니면 false. 후조건 : 키 x 가트리 T 에없음. 1. x 를가지고있는노드 p 를찾기위해다원탐색알고리즘을적용. 2. 만일 x 를찾을수없으면, false 를리턴. 3. 만일 p 가리프가아니면, x 를중위후속자로교체 ; 그러면 x 는그후속자가되고, p 는그것의노드가됨. 4. 만일 p 가최소가아니면, x 를삭제하고 true 를리턴. 5. 만일 p 의형제들중의하나가최소가아니면, 그것을 x 로회전하고 true 를리턴. 6. p 를그것의형제들중의하나및그들의부모와결합 (join) 한다음, x 를삭제하고 true 를리턴. 47
높이가 2 이고차수가 4 인 B- 트리 삽입 29 삭제 75, 70 48
B- 트리검색알고리즘 B- 트리검색 입력 : 다원탐색트리 T 와키 x. 출력 : x 가 T 에존재하는지여부. 1. 만일 T 가 NIL 이라면, false 를리턴. 2. T 의루트에있는키시이퀀스를이진탐색 ; i 를 k i-1 <x k i 에대한인덱스로설정. 3. 만일 x=k i 이면, true 를리턴. 4. T 를서브트리 T i 로설정. 5. x 에대해 T i 를탐색한결과반환되는값을리턴. 49
2-3 And 2-3-4 Trees 차수가 m 인 B- 트리에서루트가아닌모든내부노드는최소한 ceil(m/2) 의차수를가짐 2-3 tree is B-tree of order 3. 2-3-4 tree is B-tree of order 4. B-tree of order 5 is 3-4-5 tree (root may be 2-node though).