v 이원탐색트리 (binary search tree) u 인덱스를조직하는한가지방법 u 이진트리 (binary tree) 유한한수의노드를가진트리 공백 (empty) 이거나루트와두개의분리된이진트리즉, 왼쪽서브트리 (left subtree) 와오른쪽서브트리 (right su

Size: px

Start display at page:

Download "v 이원탐색트리 (binary search tree) u 인덱스를조직하는한가지방법 u 이진트리 (binary tree) 유한한수의노드를가진트리 공백 (empty) 이거나루트와두개의분리된이진트리즉, 왼쪽서브트리 (left subtree) 와오른쪽서브트리 (right su"

재원 모
6 years ago
Views:

1 6장인덱스구조 v 인덱스 (index) u 특징 화일의레코드들에대한효율적접근을위한조직 < 키값, 레코드주소 ( 포인터 )> 쌍으로구성 u 종류 키값의유형에따른인덱스 기본인덱스 (primary index) : 키값이기본키인인덱스 보조인덱스 (secondary index) : 기본인덱스이외의인덱스 화일조직에따른인덱스 집중인덱스 (clustered index) : 화일의데이타레코드들의물리적순서와인덱스엔트리순서가동일한인덱스 비집중인덱스 (unclustered index) : 집중형태가아닌인덱스 데이타범위에따른인덱스 밀집인덱스 (dense index) : 데이타레코드하나에하나의인덱스엔트리가만들어지는인덱스. 역인덱스 (inverted index) 희소인덱스 (sparse index) : 데이타레코드그룹또는데이타블록에하나의엔트리가만들어지는인덱스

2 v 이원탐색트리 (binary search tree) u 인덱스를조직하는한가지방법 u 이진트리 (binary tree) 유한한수의노드를가진트리 공백 (empty) 이거나루트와두개의분리된이진트리즉, 왼쪽서브트리 (left subtree) 와오른쪽서브트리 (right subtree) 로구성 u 이원탐색트리 이진트리 각노드 N i 는레코드키 K i 와이키를가지고있는레코드포인터를포함 공백이아닌이원탐색트리의성질 모든노드는상이한키값들을갖는다. 루트노드 N i 의왼쪽서브트리 (Left(N i )) 에있는모든노드의키값들은루트노드의키값보다작다. 루트노드 N i 의오른쪽서브트리 (Right(N i )) 에있는모든노드의키값들은루트노드의키값보다크다. 왼쪽서브트리와오른쪽서브트리는모두이원탐색트리이다. 3 v 이원탐색트리 u 이진트리와이원탐색트리 그림 (a): 이원탐색트리가아님 그림 (b), (c): 이원탐색트리 (a) (b) (c) 4

3 이원탐색트리에서의검색 u 루트노드가 N i 인이원탐색트리에서키값이 K인노드를검색하는방법. 트리가공백 : 검색실패. K=K i : 노드 N i 가원하는노드 3. K<K i : N i 의왼쪽서브트리를검색, 즉 N i Root(Left(N i )) 로하여다시검색시작. K>K i : N i 의오른쪽서브트리를검색즉, N i Root(Right(N i )) 로하여다시검색시작 5 이원탐색트리에서의검색 u 연결리스트로표현된이원탐색트리에서의검색 노드는 key, left, right 필드로구성 searchbst(b, s_key) // B는이원탐색트리, s_key는검색키값 p B; if (p = null) then // 공백이진트리로실패 return null; if (p.key = s_key) then // 검색성공 return p; if (p.key < s_key) then // 오른쪽서브트리검색 return searchbst(p.right, s_key); else return searchbst(p.left, s_key); // 왼쪽서브트리검색 end searchbst() 6

4 이원탐색트리에서의삽입 u 루트노드가 N i 인이원탐색트리에키값이 K인노드를삽입. 트리가공백 : K를루트노드로삽입. K=K i : 트리에똑같은키값이이미존재하므로삽입을거부 3. K<K i : N i 의왼쪽서브트리로이동하여계속탐색 4. K>K i : N i 의오른쪽서브트리로이동하여계속탐색 5. K가있어야할위치에없어서탐색이실패로끝나는위치에 키값이 K인노드를삽입 삽입예 : 키값 3, 5 을삽입 (a) 이원탐색트리 (b) 키값 3 을삽입 (c) 키값 5 을삽입 7 이원탐색트리에서의삽입알고리즘 insertbst(b, new_key) // B는이원탐색트리, new_key는삽입할키값 p B; while (p null) do { // 삽입하려는키값을가진노드가이미있는지검사 if (new_key = p.key) then return; q p; // q는 p의부모노드를지시 if (new_key < p.key) then p p.left; else p p.right; } newnode getnode(); // 삽입할노드를만듦 newnode.key new_key; newnode.right null; newnode.left null; if (B = null) then B newnode; // 트리가공백인경우 else if (new_key < q.key) then // q는탐색이실패로종료하게된원소 q.left newnode; else q.right newnode; return; end insertbst()

5 이원탐색트리에서의삭제 u 노드를삭제한뒤에도트리는계속이원탐색트리의성질을유지해야됨 u 삭제할노드의자식수에따라상이한삭제연산. 자식이없는리프노드의삭제 단순히그노드를삭제. 자식이하나인노드의삭제 삭제되는노드자리에그자식노드를위치 3. 자식이둘인노드의삭제 삭제되는노드자리에왼쪽서브트리에서제일큰키값이나또는오른쪽서브트리에서제일작은키값으로대체 해당서브트리에서대체노드를삭제 u 삭제는포인터값의조정으로구조변경 u 삭제표시 ( 논리적삭제 ) 로대체가능 물리적으로즉각삭제하지않는경우 다만검색, 삽입시 : 삭제된노드의키값을참고로이용가능 정상적키값이아니므로특별취급이필요 9 이원탐색트리에서의삭제 u 삭제예 : 키값 4,, 5 삭제 (a) 삭제전 (b) 삭제후 이원탐색트리에서리프노드 (4) 의삭제 (a) 삭제전 (b) 삭제후 이원탐색트리에서자식이하나인노드 () 의삭제 (a) 삭제전 (b) 왼쪽서브트리의최대키값 (3) 으로대체 (c) 오른쪽서브트리의최소키값 (5) 으로대체 이원탐색트리에서자식이둘인노드 (5) 의삭제

6 이원탐색트리에서의삭제알고리즘 deletebst(b, d_key) p node to be deleted; // 삭제할키 d_key를가진노드 parent parent node of p; // 삭제할노드의부모노드 if (p = null) then return; // 삭제할원소가없음 case { p.left=null and p.right=null : // 삭제할노드가리프노드인경우 if (parent.left = p) then parent.left null; else parent.right null; p.left=null or p.right = null : // 삭제할노드의차수가 인경우 if (p.left null) then { if (parent.left = p) then parent.left p.left; else parent.right p.left; } else { if (parent.left = p) then parent.left p.right; else parent.right p.right; } p.left null and p.right null : // 삭제할노드의차수가 인경우 q maxnode(p.left); // 왼쪽서브트리에서최대키값을탐색 p.key q.key; deletebst(p.left, p.key); } end deletebst() 편향이원탐색트리 u 편향이원탐색트리 (skewed binary search tree) 리프노드의탐색시간은최악 N개의노드로구성된이원탐색트리에서최악의탐색시간 : N번의노드탐색

7 이원탐색트리의성능 u 성능 이원탐색트리의성능은트리의형태와노드에대한접근빈도에의존 우수한성능을위해서는. 가장자주접근되는노드는루트에가장가깝게유지. 이원탐색트리를균형트리 (balanced tree) 로유지 모든노드에대해양쪽서브트리의노드수가가능한똑같게만들어트리의최대경로길이를최소화 u 이원탐색트리의단점 삽입, 삭제후효율적접근을위한균형유지부담이큼 작은분기율 (branching factor) 에따른긴탐색경로와검색시간 분기율이 : 각노드는많아야두개의서브트리 log N + N 개의노드를갖는트리의최소높이 : ë û 3 v AVL 트리 u 96 년러시아수학자 Adelson-Velskii 와 Landis 가고안한높이균형이진트리 (height-balanced binary tree) u 이진트리의높이 : 루트에서어떤리프까지의가장긴경로의길이 u AVL 높이균형이진트리 삽입, 삭제, 검색시간 : O(logN) 트리의일부만재균형시키면서트리전체가균형을계속유지할수있도록함. u AVL 트리의정의 각노드의왼쪽서브트리의높이와오른쪽서브트리의높이차이가 이하인이원탐색트리 ½h(Left(N i )) h(right(n i ))½, N i T 공백서브트리의높이 : - 4

8 AVL 트리 u 균형인수 (balance factor,bf) 왼쪽서브트리의높이에서오른쪽서브트리의높이를뺀수, BF = h(left(t)) h(right(t)) 노드의균형인수가 ± 이하이면이노드는 AVL 성질 (AVL property) 을만족하고 ± 이상이면 AVL 성질을만족하지못한다고말함. AVL 트리의모든노드는균형인수가 ± 이하이다. 즉 AVL 트리의모든노드는이 AVL 성질을만족하고있다. 5 AVL 트리와 non-avl 트리 (a) (b) (c) AVL 트리 (a) (b) (c) non-avl 트리 6

9 AVL 트리에서의검색과삽입 () u 검색 일반이원탐색트리의검색방법과동일 시간복잡도 : O(logN) u 삽입 삽입되는노드에서부터루트까지의경로에있는조상노드들의균형인수 (bf) 에영향을줄수있음 노드삽입으로 AVL 트리가 non-avl 트리가되면삽입된노드와가장가까우면서불균형이된조상노드의균형인수가 ± 이하로되게트리구조를조정해야됨 7 AVL 트리에서의검색과삽입 () (a) AVL 트리 원소 의삽입으로노드 의 AVL 성질상실 (b) 원소 의삽입으로 non-avl 트리로변환 u 노드삽입으로균형인수가 ± 로된노드 x가출현 다음 4 가지경우중하나로인해발생 ( 노드 x 는균형인수가 ±) LL : x 의왼쪽자식 (L) 의왼쪽서브트리 (L) 에삽입 RR : x 의오른쪽자식 (R) 의오른쪽서브트리 (R) 에삽입 LR : x 의왼쪽자식 (L) 의오른쪽서브트리 (R) 에삽입 RL : x 의오른쪽자식 (R) 의왼쪽서브트리 (L) 에삽입

10 AVL 트리에서의검색과삽입 (3) u 회전 (rotation): 불균형이발생할때트리구조를변경하여균형을잡아주는것. 단순회전 (single rotation) 한번의회전만필요한균형 : LL, RR 탐색순서를유지하면서부모와자식원소의위치를교환. 이중회전 (double rotation) 두번의회전이필요한균형 : LR, RL T A B LL B A T T 3 T T T3 i) LL 회전 9 AVL 트리에서의검색과삽입 (4) T - A B - RR B A T T 3 T T T 3 ii) RR 회전 A C - LR(a) B A B C iii) LR(a) 회전

11 AVL 트리에서의검색과삽입 (5) - B A C LR(b) B C - A T T T 3 T 4 T T iv) LR(b) 회전 T 3 T 4 T - B A - C T 4 LR(c) T B C T T 3 A T 4 T T 3 v) LR(c) 회전 AVL 트리에서의검색과삽입 (6) - A C C RL(a) - B A B vi) RL(a) 회전 - A - C B RL(b) A C B T T T 3 T 4 T T T 3 T 4 vii) RL(b) 회전

12 AVL 트리에서의검색과삽입 (7) - A C B RL(c) A C - B T T T 3 T 4 T T T 3 T 4 viii) RL(c) 회전 AVL 트리회전 3 AVL 트리에서의검색과삽입 () 키리스트 (, 9,,,, 5, 3, 6, 4, 7,, ) 를차례대로삽입하면서 AVL 트리를구축하는예 RR 9 Þ (a) 키 삽입 (b) 키 9 삽입 (c) 키 삽입 9 9 LL Þ (d) 키 삽입 (e) 키 삽입 9 4

13 노드삽입에따른균형인수 (BF) 조정 u 노드삽입으로인한균형인수 (BF) 의변화 새로노드를삽입할때 BF에영향을받는노드는오직이새로운노드에서부터루트까지의경로상에있는노드들이다. 새로운노드를왼쪽서브트리로삽입하면그부모노드의 BF 를하나증가 (+) 시키고오른쪽서브트리로삽입하면 BF 를하나감소 (-) 시킨다. 이때이 BF 가 이되면 BF 조정은종료되고아니면다시그의부모노드의 BF 를변경한다. 즉, 자기가부모노드의왼쪽서브트리이면 BF 를하나증가 (+) 시키고오른쪽서브트리이면 BF 를하나감소 (-) 시키면서루트까지의경로를따라가면서 BF 조정작업을계속한다. 5 AVL 트리에서의검색과삽입 (9) (h) 키 6 삽입 LR Þ (f) 키 5 삽입 RL Þ (g) 키 3 삽입 (i) 키 4 삽입 4 6 6

14 AVL 트리에서의검색과삽입 () LR Þ (j) 원소 7 삽입 RR Þ (k) 원소 삽입 AVL 트리에서의검색과삽입 () (l) 키 삽입

15 AVL 트리에서의삽입알고리즘 () /* AVL 트리삽입알고리즘 */ insertavl(new_key) if (root = new_key) then { // 공백트리인경우 y gettreenode(); y.key newkey; root y; root.bf ; //bf 는균형인수 root.left null; root.right null; return true; } f null; a p root; q null; found false; // phase : new_key 의삽입위치 (q) 조사 while (p null and found = false) do if (p.bf ) then {a p; f q;} if (new_key < p.key) then {q p; p p.left;} // 왼쪽서브트리로이동 else if (new_key > p.key) then {q p; p p.right;} // 오른쪽서브트리로이동 else {y p; found true;} } // while // phase : new_key 를삽입하고균형화 9 AVL 트리에서의삽입알고리즘 () // phase : new_key 를삽입하고균형화 if (found = false) then { // new_key 는트리에없음. // new_key 를 q 의적절한자식으로삽입 y gettreenode(); y.key newkey; y.left null; y.right null; y.bf ; if (new_key < q.key) then q.left y; //q 의왼쪽자식으로삽입 else q.right y; //q 의오른쪽자식으로삽입 // a 에서 q 까지의경로에있는노드의균형인수를조정. // a 의정의에따라이경로상에있는모든노드들은그 // 균형인수가 이어야되기때문에이들의균형인수는 // ± 로변경된다. 따라서 // d= 은 new_key 가 a 의왼쪽서브트리로삽입되었다는 // 것을의미하고 // d=- 은 a 의오른쪽서브트리로삽입되었다는것을 // 의미한다. 3

16 AVL 트리에서의삽입알고리즘 (3) if (new_key > a.key) then {p a.right; b p; d -;} else {p a.left; b p; d ;} while (p y) do { if (new_key > p.key) then {p.bf -; p p.right;} // 오른쪽서브트리의높이가 증가 else {p.bf ; p p.left;} // 왼쪽서브트리의높이가 증가 } //while (p y) unbalanced true; // 트리가불균형인지를검사 if (a.bf = or a.bf+d = ) then // 트리가아직균형 {a.bf a.bf+d; unbalanced false; } if (unbalanced = true) then // 트리가불균형. 회전유형을결정 if (d = ) then { // 왼쪽불균형 if (b.bf = ) then { // LL 회전타입 a.left b.right; b.right a; a.bf ; b.bf ;} } else { // LR 회전타입 c b.right; b.right c.left; a.left c.right; c.left b; c.right a; switch (c.bf) { case : a.bf -; b.bf ; break; //LR(b) case - : b.bf ; a.bf ; break; //LR(c) case : b.bf ; a.bf ; break; //LR(a) } c.bf ; b c; // b 는새로운루트 } // else LR 회전타입 3 AVL 트리에서의삽입알고리즘 (4) if (unbalanced = true) then // 트리가불균형. 회전유형을결정 if (d = ) then { // 왼쪽불균형 if (b.bf = ) then { // LL 회전타입 ************ } else { // LR 회전타입 ************ } // else LR 회전타입 } // 왼쪽불균형 else { // 오른쪽불균형. 왼쪽불균형의대칭코드..// RR 회전타입..// RL 회전타입 } if (f = null) then root b; else if (a = f.left) then f.right b; } // if (unbalanced = true) return true; } // if (found = false return false; end insertavl() // b 를루트로하는서브트리가 // 균형을맞추고새로운서브트리가됨 3

17 AVL 트리의높이 u 높이균형이진트리의높이 N개의노드를가진높이균형이진트리는완전균형이진트리보다 45% 이상높아지지않음 log(n+) h.444log(n+)-.3 u 높이균형이진트리대완전균형이진트리 O(.4 log N) 대 O(log N) 높이균형이진트리의탐색시간이더길다 이유 : 트리의전체재균형을수행하지않기때문 u 수백만개의노드로구성된 AVL 트리가디스크에저장된상태에서의노드탐색은많은횟수의디스크접근을요구한다. 그래서 m-원탐색트리를고려하게된다. 33 v m-원탐색트리 (m-way search tree) u u 이원탐색트리보다높은분기율 : m개서브트리 장점 : 트리의높이가감소 ( 특정노드의탐색시간감소 ) 단점 : 삽입, 삭제시트리의균형유지를위해복잡한연산이필요 m-원탐색트리의성질 노드구조는 <n, P, K, P, K, P,, P n-, K n, P n > (n: 키값수, n<m, P i : 서브트리에대한포인터, K i : 키값 ) 한노드에있는키값들은오름차순 : K i < K i+, i n- 3 P i ( i n-) 가지시하는서브트리모든노드들의키값 < K i+ 4 P n 이지시하는서브트리의모든노드들의키값 > K n 5 P i 가지시하는서브트리는 m-원서브트리 34

18 3-원탐색트리 4 a b c d ^ ^ e f g h i j ^ ^ 키값 K i : (K i, A i ) 를의미하고, A i 는키값 K i 를포함하고있는데이타레코드의주소 35 m-원탐색트리의검색 searchmt(key) // m-원탐색트리의검색알고리즘 // key : 검색키값 // x : 노드 (<n, P, K, P, K, P,, P n-, K n, P n >) // root : 루트노드 // n : 노드에있는키의개수 x root; while( x!= null ) do { i ; n x.n; while( i <= n && key > x.k i ) i i+; if ( i <= x.n && key = x.k i ) then return A i ; // 키값 key를가진레코드의주소를반환 if (i > n) then x x.p n else x x.p i- } //while return null; // key와일치하는값이트리에없는경우 end searchmt() 36

19 m-원탐색트리의분석 u m-원탐색트리의탐색시간 : 탐색경로길이 ( 높이 ) 에비례 각레벨에서는한개의노드만탐색 분기율 (m) 을최대로하면트리의높이가낮아짐 u 한노드에 m-개키값을저장하는 m-원탐색트리 높이 h : n = (m h -) 개키값저장 ( 예 ) 4-원탐색트리 : 높이가 3이면 n=(4 3 -)=63개의키값을저장 u n개의키를가진 m-원탐색트리 최소높이 h = é log m (N+) ù 최대탐색시간 : O(log m (N+)) ( 예 ) m= 이면 : 이진트리탐색시간 37 v B-트리 u 97 년 Bayer & McCreight 가제안 u 균형 m-원탐색트리 가장많이사용되는인덱스방법 효율적인균형알고리즘을제공 u 차수 (order) 가 m인 B-tree 의특성 B-트리는공백이거나높이가 이상인 m-원탐색트리 루트와리프를제외한내부노드 - 최소 é m/ ù, 최대 m개의서브트리 - 적어도 é m/ ù - 개의키값 ( 노드의반이상이채워짐 ) 3 루트 : 리프가아니면적어도두개의서브트리를가짐 4 모든리프는같은레벨 3

20 m차 B-트리노드구조 u 노드구조 < n, p, <K, A >, P, <K, A >, P,, P n-, <K n, A n >, P n > n : 키값의수 ( n<m), P,, P n : 서브트리에대한포인터, 각키값 K i 는그키값을가진레코드에대한포인터 A i 를포함 각노드의키값들은항상오름차순 ( i n- à K i < K i+ ) 을유지 3 P i 가지시하는서브트리의키값들은모두 K i+ 보다작다. 4 P n 이지시하는서브트리의키값들은모두 K n 보다크다. 5 P i ( i n) 가지시하는서브트리들은모두 m- 원서브탐색트리이다. u B-트리의장점 삽입, 삭제뒤에도트리의균형상태를유지 저장장치의효율성 각노드의반이상은항상키값으로채워짐 39 3차 B-트리구조 a 69 ^ b c d e f g h i ^ ^ ^ ^ ^ 3 45 j k l m n o p q r s t u v

21 B-트리에서의연산 u 검색 : m-원탐색트리의직접검색과같은과정 직접탐색 : 키값에따라왼쪽또는오른쪽서브트리로분기 노드에서의검색은순차검색예 ) 키값 4 검색 B-트리전체의순차검색은트리의중위순회 (inorder traversal) 로수행 u 삽입 : 새로운키값은항상리프노드에삽입 노드에공간이있는경우 : 단순히순서에만맞게삽입 노드에공간이없는경우 : overflow로 split 발생 해당노드를두개의노드로분할 해당노드에새로운키값삽입했다고가정 중간 ( ém/ù 번째 ) 키값을기준으로왼쪽작은키값들은그대로두고오른쪽큰키값들은새로운노드에저장 중간키값은분할된두노드가왼쪽서브트리, 오른쪽서브트리가되도록부모노드에삽입 이때, 다시 overflow가발생하면위와같은분할 (split) 작업을반복 4 B-트리에서의삽입 u 앞의 B-트리에새로운키값, 4, 59, 57, 54, 44, 75, 4,, 3 삽입 l l n 4 n 4 4 (a) 노드 l 에키 의삽입 (b) 리프노드 n 에키 4 의삽입 b b f 6 ^ f 5 6 p o 5 5 p o 5 o 59 (c) 노드 o 에키 59 의삽입 4

22 B-트리에서의삽입 o 5 o 5 57 o 5 57 o 5 o 57 (d) 노드 o 에키 57 의삽입 (d) 키 54 의삽입으로노드 o 의분할 (54 는부모노드 f 로이동 ) f 5 6 o o p f 54 ^ o o f 6 ^ o p (e) 노드 f 에키 54 의삽입 (5 는부모노드 b 에삽입 ) 43 B-트리에서의삽입 b 9 43 d e f b 9 ^ d e b 5 ^ f f (g) 노드 b 에키 5 의삽입 (43 은부모노드 a 에삽입 ) a 69 ^ b c (h) 노드 a 에키 43 의삽입 a b b c 나머지키값인 33, 75, 4, 를차례로삽입 : 문제가발생하지않음마지막키값인 3 을삽입 : B- 트리는한레벨증가됨 44

23 한레벨증가된 B-트리 a o 69 a a 43 b b c c d e e f f g g h i j k l m m n o o o p q r r r s t u v 차 B-트리생성과정 u 키값 43, 69, 3, 9 순으로삽입하여생성 (a) 크기가 인공백루트노드 (b) 키값 43 의삽입 ( 노드 개의 3 차 B- 트리 ) (c) 키값 69 의삽입 ( 노드 개의 3 차 B- 트리 ) (d) 키값 3 의삽입 ( 노드 3 개의 3 차 B- 트리 ) (e) 키값 9 의삽입 ( 노드 3 개의 3 차 B- 트리 ) 46

24 B-트리에서의삽입알고리즘 B- 트리삽입알고리즘 // In-key : 삽입할키 // Finished : 삽입완료를나타내는플래그 // Found : 레코드가발견되었음을나타내는플래그 // P : 노드에대한포인터 // Bignode : 오버플로노드를위한변수 // N : 키카운터 // 노드의주소를스택에저장하면서 In-key 가삽입될위치를탐색 Found = false; read root; do { N = number of keys in current node; if (n-key == key in current node) found = true; else if (In-key < key ) P = P o ; else if (In-key > key N ) P = P N ; else P = P i- ; /* for some i where key i- < In-key < key i */ if (P!= null) { push onto stack address of current node; read node pointed to by P; } } while (!Found && P is not null); 47 B-트리 } if (Found) report In-key already in tree; else { // In-key를 B-트리에삽입 P = null; Finished = false; do { if (current node is not full) { put In-key in current node; // 노드안에서키순서를유지하도록키를정렬 Finished = true; } else { copy current node to Bignode; insert In-key and P into Bignode; In-key = center key of Bignode; current node = st half of Bignode; get space for new node, assign address to P; new node = nd half of Bignode; if (stack not empty) { pop top of stack; read node pointed to; } else { // 트리의레벨이하나증가 get space for new node; new node = pointer to old root, In-key and P; Finished = true; } } } while (!Finished); 4

25 B-트리에서의삭제. 삭제할키값이리프노드에있는경우에는그대로삭제. 삭제될키값이내부노드에있는경우 이키값의후행키값과교환후리프노드에서삭제 B-트리특성상이후행키값은항상리프노드에있음 리프노드에서의삭제연산이더간단 후행키값대신선행키값을사용할수있음 삭제결과로노드의키값수가 B-트리의최소키값 m/ ù - ) 보다작게되면 underflow 가일어나재분배나합병을수행 3. 삭제수 (ém/ 49 B-트리에서의삭제 u 재분배 (redistribution) 해당노드의오른쪽이나왼쪽형제노드중에서최소키값보다많은수의키값을가진노드에서키값하나를차출 부모노드에있는키값을언더플로가일어난노드로이동하고, 이빈자리로차출된키값을이동 트리구조가변경되지않음 u 합병 (merge) 재분배가불가능한경우 ( 두형제노드가최소의키값만을가짐 ) 에적용 언더플로가된노드의오른쪽 ( 또는왼쪽 ) 형제노드에있는키값들과이두노드를분리시키는부모노드의키값을합치고트리구조를조정. 합병으로생긴빈노드는제거 트리구조가변경됨 이합병작업은투트노드까지연쇄적으로파급될수있음. 이경우에는트리의레벨이하나감소될수도있음. 5

26 B-트리에서의삭제 u 앞의 B-트리에서키값 5, 7, 6,, 5 삭제 o 5 5 o 5 j 7 5 j 5 노드 o 에서키값 5 의삭제 노드 j 에서키값 7 의삭제 b b b f 6 f 6 f 6 o 5 p 6 65 o 5 p 6 65 o 5 p 65 노드 f 에서키값 6 의삭제 5 B-트리에서의삭제 b b l e 6 4 m 3 36 n 4 l 6 e 3 4 m 36 n 4 노드 l 에서키값 의삭제 j 5 d 6 k b 9 43 e 3 l 6 a 4 m 36 f n 4 5

27 B-트리에서의삭제 jk 6 jk 6 d d 9 l 6 b 9 43 e 3 l 6 a b 3 43 e 4 m 36 4 a m 36 n 4 f n 4 f 노드 j 에서키값 5 의삭제 53 B-트리삭제알고리즘 B- 트리삭제알고리즘 // Finished : 삭제완료를나타내는플래그 // Tempnode : 재분배를위해사용할정상노드보다 5% 큰노드 // Sibling : 인접형제노드 // D-key : B- 트리에서삭제할키 search tree for D-key forming stack of node addresses; // 탐색은삽입알고리즘참조 if (D-key is not in terminal node) { search for successor key of D-key at terminal level (stacking node addresses); copy successor over D-key; terminal node successor now becomes the D-key; } // 키를삭제하고트리를재조정 Finished = false; 54

28 트리 do { remove D-key if (current node is root or is not too small) Finished = true; else if (redistribution possible) { // Sibling > minimum이면재분배 // 재분배실행 copy "best" Sibling, intermediate parent key, and current (too-small) node into Tempnode; copy keys and pointers from Tempnode to "best" Sibling, parent, and current node so Sibling and current node are roughly equal size; Finished = true; } else { // 적절한 Sibling과합병 choose best Sibling to concatenate with; put in the leftmost of the current node and Sibling the contents of both nodes and the intermediate key from the parent; discard rightmost of the two nodes; intermediate key in parent now becomes D-key; } } while (!Finished); if (no keys in root) { // 트리의레벨을하나감소 new root is the node pointed to by the current root; discard old root; } B- 트리 55 v B*- 트리 u B-트리의문제점 B-트리구조유지를위해추가적인연산이필요 삽입시노드의분할이나재분배, 삭제시노드의합병이나재분배 B*-트리는 B-트리의성능개선을위해 Knuth가제안한 B-트리의한변형 u B*- 트리 공백이거나높이가 이상인 m-원탐색트리 루트는리프가아닌이상최소 개, 최대 ë(m-)/3û+ 개의서브트리를갖는다. 3 루트와리프를제외한노드는적어도 ë(m-)/3û+개의서브트리, 즉최소 ë(m-)/3û 개의키값을갖는다. 4 모든리프는같은레벨에있다. 56

29 v B*- 트리 u u 삽입으로인한노드분할의빈도를축소 노드가오버플로되면즉시분할하는대신. 오버플로가된키값과포인터를바로인접한형제노드의여유공간을이용해재분배. 인접형제노드가모두만원이면두인접형제노드의키값들을 3개의노드로분할 한노드가만원이되더라도다른인접형제노드가만원이될때까지분할은지연 각내부노드는항상 /3 이상키값으로채워짐 같은키값의수에대해 B-트리보다적은수의노드가필요 57 7차 B*- 트리의생성 (a) 개의키값삽입으로만원이된 7 차 B*- 트리루트노드 (7 차에대한노드분할을위해서는 개의키값을갖는루트노드크기가필요 ) (b) 키값 9 의삽입으로루트노드가최초로분할된 7 차 B*- 트리 5

30 B*- 트리에서의삽입 u u 오버플로가발생하면인접형제노드에여유공간이있는지검사. 여유공간이있으면 오버플로키값을부모노드로올려보내고부모노드에있던분리키값을형제노드로이동시키거나또는 오버플로가된노드와인접형제노드의키값에다분리키값을포함해서이들을균등하게양분해서저장하고중간키값을분리키값으로부모노드에저장여유공간이없으면 만원이된두인접형제노드의키값들을부모노드의분리키값과함께 3개의노드로분할해서각노드의키값수가적어도 ë(m-)/3û이되도록재분배한다. 이때 개의키값은분리키값으로부모노드에저장된다. 59 5차 B*- 트리에서의삽입 u 재분배를이용한키값 4 의삽입 ( 노드 q) r 33 q 6 s r 6 q 4 s

31 5차 B*- 트리에서의삽입 u 노드분할을이용한키값 3 의삽입 ( 노드 q) r 6 q 4 s q r 33 q s B*- 트리에서의삭제 u B-트리에서의삭제와비슷. 키값삭제로최소키값수가유지되지않으면. 형제노드로부터재분배를받도록시도. 형제노드에여유키값이없으면 3개의노드를 개의노드로합병 합병으로인해트리의높이가한레벨낮아질수있음. 6

32 v 트라이 (Trie) u Trie: retrieval 의약자 u 키를구성하는문자나숫자의순서를이용해키값을검색할수있는자료구조 m- 진트리이지만 m- 원탐색트리는아님 : 키값의배열순서가다름 u m진트라이 (m-ary trie) 차수 m : 키값을표현하기위해사용하는문자의수, 즉기수 (radix) 숫자 : 기수가 이므로 m=, 영문자 : m = 6 m진트라이 : m개의포인터를표현하는 차원배열 각원소 ( 포인터 ) 는기수의원소에 :로대응 (p 는, p 5 는5) u 진트라이의노드구조 P P P P 3 P 4 P 5 P 6 P 7 P P 9 63 v 트라이 (Trie) u 트라이의높이 = 키필드의길이 u 진트라이의레벨 j의포인터 p i 는 j번째숫자가 i인모든키값을나타내는서브트라이를가리킴. 레벨 3에있는 p 4 는키값의 3번째숫자가 4인키값을가진서브트라이를가리킴. 해당숫자가없을때는널포인터로표시 u 키값 : 루트노드의 p i 에서리프노드의 p j 까지의경로를각포인터에대응하는기수원소로표현한것. u 리프노드에는해당키값을가진레코드의주소가저장됨 u 키검색뿐만아니라키의존재유무를빠르게결정 u 트라이에서널포인터만가지고있는공백노드는생성하지않음. 64

33 높이가 4인 진트라이 레벨 r P 레벨 a P 4 ¼ ¼ ¼ ¼ 레벨 3 b P 레벨 4 c ****** d ******* ******* ******* ********* **** ****** ***** : 널포인터 * : 해당키값을가지고있는데이타레코드의주소 65 m진트라이연산 u 검색 검색은리프에서종료되거나, 키값이없을때중간노드에서종료 검색속도는키필드의길이 ( 트라이의높이 ) 에비례 최대검색비용은키필드의길이 장점 : 균일한탐색시간 선호이유 : 없는키에대한빠른검색 u 삽입 새로운키값이삽입되어야할노드를검색 리프노드에새레코드의주소나존재표시를삽입 리프노드가없을때 : 새리프노드를생성하고중간노드를첨가 노드의첨가나삭제는있으나분열이나병합은없음 u 삭제 노드와원소들을찾아서널값으로변경 노드의원소값들이모두널 ( 공백노드 ) 인경우에는노드삭제 66

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

13. 탐색트리 AVL 트리, B- 트리, 2-3-4 트리 정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2 이진탐색트리의예 3 BST 의최선과최악의경우