13. 탐색 트리

13.1 키와 Comparable 타입 (1) Comparable 인터페이스 public int compareTo(Object object) 다음 세 가지 가능성 중의 하나에 대한 정보를 가지고 있는 정수 c를 리턴 만일 c<0이면, this 객체는 주어진 object보다 작음 만일 c=0이면, this 객체는 주어진 object와 같음 만일 c>0이면, this 객체는 주어진 object보다 큼 디스크 주소를 위한 인터페이스 interface DiskAddress { public Object get(Comparable key); }

키와 Comparable 타입 (2) 탐색 트리가 만족해야 하는 조건 탐색 트리의 구현 예 탐색 트리 구조 내에 있는 키는 유일함 각각의 키는 그것이 표현하는 데이터의 주소를 가지고 있음 키의 타입은 java.lang.Comparable 인터페이스를 구현함 주소의 타입은 Address 인터페이스를 구현함 탐색 트리의 구현 예 탐색 트리가 내부 레드-블랙 트리 Object[] data = new Object[200]; 탐색 트리가 내부 B-트리 class DiskAddress implements Address { private String drive; private long sector, block; }

13.2 이진 탐색 트리 (1) 정의 이진 탐색 트리(BST: binary search tree)는 각각의 노드가 BST 특성을 만족하는 키-주소 쌍을 가지고 있는 이진 트리 BST 특성 트리에 있는 각각의 키에 대해, 왼쪽 서브트리에 있는 모든 키는 이것보다 작고, 오른쪽 서브트리에 있는 모든 키는 이것보다 큼 < >

이진 탐색 트리 (2) 이진 탐색 트리의 순회 BST 검색 알고리즘 1. 만일 T가 공백이면, null을 리턴. 이진 탐색 트리의 중위 순회는 키를 오름차순으로 방문 BST 검색 알고리즘 입력 : 이진 탐색 트리 T와 키. 출력 : 키를 위한 데이터 주소 또는 키가 T에 없다면 null. 1. 만일 T가 공백이면, null을 리턴. 2. 만일 key < root.key 이면, 키를 찾기 위해 왼쪽 순환 탐색에 의해 반환되는 값을 리턴. 3. 만일 key > root.key 이면, 키를 찾기 위한 오른쪽 순환 탐색에 의해 반환되는 값을 리턴. 4. root.address를 리턴.

이진 탐색 트리의 예

BST 삽입 BST 삽입 알고리즘 1. 만일 T가 공백이면 키-주소 쌍을 포함하는 단독 트리를 만들고, true를 리턴. 출력 : 키가 T에 이미 있다면 false, 아니면 true. 선조건 : 키-주소 쌍은 T에 있음. 1. 만일 T가 공백이면 키-주소 쌍을 포함하는 단독 트리를 만들고, true를 리턴. 2. 만일 key < root.key 이면, 순환적으로 왼쪽 서브트리에서 키-주소 쌍의 삽입에 의해 반환되는 값을 리턴. 3. 만일 key < root.key 이면, 순환적으로 오른쪽 서브트리에서 키-주소 쌍의 삽입에 의해 반환되는 값을 리턴. 4. false를 리턴.

BST 삽입의 예

BST 구축 예

BST의 최선과 최악의 경우

BST BST 최소값 알고리즘 BST 후속자 알고리즘 입력 : 공백이 아닌 이진 탐색 트리 T. 1. x를 T의 루트라 하자. 2. x.left가 공백이 아닌 동안 x=x.left로 설정. 3. x를 리턴. BST 후속자 알고리즘 입력 : 공백이 아닌 이진 탐색 트리 T와 노드 x. 출력 : x의 중위 후속자 또는 x가 T의 최대 원소일 경우에는 null. 1. 만일 x의 오른쪽 서브트리가 공백이 아니면, 그것의 최소값을 리턴(BST 최소값 알고리즘). 2. 만일 x의 오른쪽 서브트리가 공백이면, x가 오른쪽 자식인 동안 x=x.parent로 설정. 3. x.parent(null이 될 수 있음)를 리턴.

노드의 중위 후속자 사례 1: 후속자는 오른쪽 서브트리의 최소 원소임 사례 2: 후속자는 값이 크면서 가장 가까운 조상임 사례 3: 트리에서 가장 오른쪽 원소는 후속자를 가지지 않음

BST 삭제 노드 44를 삭제하기 위한 부적절한 시도

BST 삭제 노드 44를 삭제하는 올바른 방법

BST 삭제의 세 가지 경우

BST 삭제 입력 : 이진 탐색 트리 T와 키. 출력 : T에서 키를 발견할 수 없으면 false; 아니면 true. 2. 만일 key < root.key 이면, 순환적으로 왼쪽 서브트리로부터 키의 삭제에 의해 반환되는 값을 리턴. 3. 만일 key > root.key 이면, 순환적으로 오른쪽 서브트리로부터 키의 삭제에 의해 반환되는 값을 리턴. 4. 만일 T가 단독 트리이면, 이것을 공백 트리로 만들고, true를 리턴. 5. 만일 왼쪽 서브트리가 공백이면, T의 오른쪽 서브트리의 루트, 왼쪽, 오른쪽 필드를 T 자체에 복사하고, true를 리턴. 6. 만일 오른쪽 서브트리가 공백이면, T의 왼쪽 서브트리의 루트, 왼쪽, 오른쪽 필드를 T 자체에 복사하고, true를 리턴. 7. 후속자 노드를 찾아 루트와 교체한 후 후속자 노드에 대해 BST 삭제 알고리즘 순환 호출.

13.4 BST 성능 이진 탐색 트리의 삽입과 탐색 BST 탐색과 삽입 알고리즘에 대한 평균 시간 복잡도 B(n) = Θ(1) A(n) = Θ(lg n) W(n) = Θ(n) BST 탐색과 삽입 알고리즘에 대한 평균 시간 복잡도

13.5 AVL 트리 AVL 트리 어떤 노드에서도 두 서브트리가 거의 같은 높이를 갖도록 강제하여 균형을 유지하는 이진 탐색 트리 불균형이 발생할 때마다 서브트리를 회전하여 균형을 맞추어 줌 AVL 회전의 패턴 왼쪽 단순 회전 오른쪽 단순 회전 복합 오른쪽-왼쪽 회전 복합 왼쪽-오른쪽 회전

왼쪽 회전 알고리즘 (1) x에 대해 왼쪽으로 회전 x에 대해 왼쪽으로 회전

왼쪽 회전 알고리즘 (2) x에 대해 왼쪽으로 회전 x에 대해 왼쪽으로 회전

이중 회전 알고리즘 (1) y에 대해 오른쪽으로 회전 x에 대해 왼쪽으로 회전

이중 회전 알고리즘 (2) y에 대해 오른쪽으로 회전 x에 대해 왼쪽으로 회전

AVL 회전의 패턴 왼쪽 단순 회전 오른쪽 단순 회전 복합 오른쪽-왼쪽 회전 복합 왼쪽-오른쪽 회전

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(); 14 grow(key); 15 return size()>oldSize; 16 } 17

AVL 트리의 구현 (2) 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 }

AVL 트리의 구현 (3) 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 }

AVL 트리의 구현 (4) 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 }

AVL 특성 AVL 트리가 아님 : AVL 트리임 :

회전이 있는 AVL 삽입 35 삽입 오른쪽 회전 왼쪽 회전

AVL 회전 라인 62 : 라인 63 : 라인 64 :

13.7 피보나치 트리 피보나치 트리 높이가 1인 이진 트리 높이 h=2인 네 가지 피보나치 트리 피보나치 수를 생성하는 것과 동일한 순환적인 아이디어를 사용하여 생성 이 트리는 최악의 경우 AVL 트리이며 이것을 분석해 보면 일반적인 AVL 트리가 최악의 경우에도 로그 시간에 수행된다는 것을 증명할 수 있음 높이가 1인 이진 트리 높이 h=2인 네 가지 피보나치 트리

피보나치 트리의 특성 피보나치 트리 피보나치 트리의 크기에 대한 범위 AVL 트리의 최악의 경우 성능 피보나치 트리는 AVL 특성을 만족하며, 주어진 높이에서 AVL 특성을 만족하는 모든 이진 트리 중에서 최소 크기를 가짐 피보나치 트리의 크기에 대한 범위 AVL 트리의 최악의 경우 성능 AVL 트리에 대한 탐색과 삽입은 최악의 경우 Θ(lgn)에 실행됨

피보나치 트리의 예

높이 h=4인 최소와 최대 AVL 트리 피보나치 트리 포화 이진 트리 h = 4 n = 12 n = 31

13.8 다원 탐색 트리 정의 다원 탐색 트리(MST: Multiway Search Tree) 특성을 만족하는 트리 MST 특성 만일 Ti에 있는 각각의 xi에 대해 x0, x1, x2, …, xd-1을 서브트리에 있는 키라고 하면, x0<k0<x1<k1<x2<k2<…xd-2<kd-2임

다원 탐색 트리의 예 차수가 7인 다원 탐색 노드 차수가 5인 다원 탐색 트리

다원 탐색 트리의 Java 정의 1 public class MST { 3 private class Node { 4 int degree; 5 Comparable[] keys; 6 DiskAddress[] locs; 7 Node[ ] kids; 9 Node(int m) { 10 keys = new String[m-1]; 11 locs = new DiskAddress[m-1]; 12 kids = new Node[m]; 13 } 14 } 16 private int degree; 17 private Node root; 19 public MST(int m) { 20 degree = m; 21 root = new Node(m); 22 } 23 }

Java MST.Node 객체

13.9 B-트리 차수가 m인 B-트리는 다음을 만족하는 차수가 m인 다원 탐색 트리임 모든 리프 노드는 동일한 레벨에 있음 루트가 아닌 모든 내부 노드는 최소한 의 차수를 가짐 B-트리의 크기에 대한 범위 B-트리의 높이에 대한 범위

B-트리의 예 972년 R. Bayer와 E. McCreight에 의해 개발되었다

B-트리 삽입 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를 리턴.

B-트리 삭제 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를 리턴.

높이가 2이고 차수가 4인 B-트리

B-트리 검색 B-트리 검색 알고리즘 입력 : 다원 탐색 트리 T와 키 x. 출력 : x가 T에 존재하는지 여부. 1. 만일 T가 NIL이라면, false를 리턴. 2. T의 루트에 있는 키 시이퀀스를 이진 탐색; i를 ki-1<x≤ki에 대한 인덱스로 설정. 3. 만일 x=ki이면, true를 리턴. 4. T를 서브트리 Ti로 설정. 5. x에 대해 Ti를 탐색한 결과 반환되는 값을 리턴. 6. 만일 x=ki이면, false를 리턴. 7. 만일 Ti가 NIL이면, ki-1과 ki 사이에 x를 삽입 8. Ti에서 x를 삽입한 결과 반환되는 값을 리턴.

B-트리 분할 연산 B-트리 분할 알고리즘 포화 노드는 하나의 단독 노드 A와 이것의 두 자식이 되는 두 개의 반-포화(half-full) 노드 B와 C로 교체됨 A에 있는 하나의 원소는 원래 노드에 있는 키의 중앙값이다.

13.10 레드-블랙 트리 2-3-4 트리 2-3-4 트리를 이진 트리로 저장 레드-블랙 트리 차수가 4인 B-트리는 각각의 내부 노드가 2, 3, 4 개의 자식을 가지고 있기 때문에 2-3-4 트리라고도 불림 세 개의 자식을 가지고 있는 노드를 3-노드라고 부르고, 네 개의 자식을 가지고 있는 노드를 4-노드라고 부름 2-3-4 트리를 이진 트리로 저장 2-3-4 트리를 이진 트리로 저장하는 아이디어는 각각의 3-노드를 크기 2인 이진 트리로 표현하고, 각각의 4-노드는 크기 3인 이진 트리로 표현 레드-블랙 트리 이진 트리의 일반적인 노드는 블랙으로 표현하고, 3-노드와 4-노드는 레드로 표현한 트리 모든 단독 노드는 블랙이고, 3-노드와 4-노드는 레드-블랙 서브트리로 교체

레드-블랙 트리 노드를 B-트리 노드로 표현

B-트리를 표현하는 레드-블랙 트리

레드-블랙 트리로 변환 방법 레드-블랙 트리로 변환된 후에도 순서가 유지되는 2-3-4 트리에 있는 서브트리

레드-블랙 트리 특성 다음과 같은 레드-블랙-트리 특성을 만족하는 모든 이진 탐색 트리는 2-3-4 트리로 표현됨 1. 각각의 노드는 레드 또는 블랙이다. 2. 루트와 NIL 노드는 블랙이다. 3. 각각의 레드 노드의 두 자식은 블랙이다. 4. 모든 루트-리프 경로는 동일한 개수의 블랙 노드를 가지고 있다.

블랙 높이가 2인 레드-블랙 트리

레드-블랙 트리 삽입 레드-블랙 트리 삽입 알고리즘 입력 : 레드-블랙 트리 T와 키-주소 쌍. 출력 : 이미 키가 T에 있으면 false, 아니면 true. 후조건 : 키-주소 쌍은 트리 T에 존재. 1. 만일 T가 공백이면, 이것을 블랙 노드로 키를 포함하는 단독 트리로 만들고, true를 리턴. 2. r을 T의 루트로 설정. 3. r이 리프가 아닌 동안, 단계 4-8을 반복. 4. 만일 r이 블랙이고 그것의 두 자식이 레드라면, 모든 세 노드를 다시 색칠. 5. 만일 r과 그것의 부모가 레드라면 r, 부모, 조부모를 회전. 6. 만일 key<r.key 라면, r=r.left로 설정. 7. 아니고, 만일 key>r.key 라면, r=r.right로 설정. 8. 아니면, false를 리턴(key=r.key이기 때문에) 9. 만일 key<r.key 라면, r.left를 키-주소 쌍을 가지는 새로운 레드 노드로 설정. 10. 아니고, 만일 key>r.key 라면, r.right를 키-주소 쌍을 가지는 새로운 레드 노드로 설정. 11. 아니면, false를 리턴(key=r.key이기 때문에) 12. 만일 r이 레드이면, r, 부모, 새로운 노드를 회전 13. true를 리턴.

레드-블랙 트리를 위한 회전

레드-블랙 트리에 삽입하는 예