13 장. 균형탐색트리 균형탐색트리 트리의작업효율을높이기위한다양한균형트리알고리즘을비교 학습목표 트리의균형이효율에미치는영향을이해한다. AVL 트리에서균형을회복하기위한방법을이해한다. 스플레이기법을이해한다. 2-3 트리에서균형을회복하기위한방법을이해한다. 2-3-4 트리와레드블랙트리의관계를이해한다. 1
균형 균형 2
AVL G. M. Adelson-Velskii and E. M. Landis AVL 트리 : 항상균형을유지하는이진탐색트리삽입삭제가일어날때마다트리의균형상태를점검하고복원 균형의점검 균형인수 (Balance Factor) 를사용 노드마다서브트리의높이에서왼쪽서브트리의높이를뺀것 3
AVL 트리 균형 균형인수값은반드시 -1, 0, +1 중하나. 왼쪽트리로부터노드 K 를삭제함에따라균형이깨어진것이오른쪽트리. 균형인수의범위초과 왼쪽트리에서노드 E 의왼쪽자식에삽입이가해졌다면루트 F 를기준으로왼쪽서브트리의높이가증가 삽입으로인해만약어떤노드의균형인수가범위를벗어났다면, 그노드는삽입위치인 E 의왼쪽자식으로부터루트 F 까지가는길목에있는 E, D, F 중에존재 4
AVL 의회전 회전 (Rotation) 에의한균형회복 불균형노드의위치를기준으로 LL, LR, RL, RR 로분류 LL 회전은불균형노드의왼쪽서브트리의왼쪽서브트리의높이가증가 LL 의 RChild 에삽입되는경우와, LChild) 에삽입되는경우 L -2 12 L -2 12 L 7 20 L 7 20 3 10 3 10 5 2 5
LL 회전 불균형노드 ( 루트노드 ) 루트의 LChild 7 의 RChild 연결이끊어져서루트의 LChild 로붙음 루트의 LChild 인노드 7 을중심으로회전이일어나노드 7 이새로운루트로 7 이루트가되면 7 보다큰 10 은 7 의중위후속자가되어야함. 루트 12 의부모노드로부터내려오던링크를새로운루트 7 에연결 이진탐색트리의키크기가유지되면서트리의균형이회복. 6
LR 회전 불균형이발생한노드의왼쪽서브트리의오른쪽서브트리높이가증가 이중회전 (Double Rotation) 루트의 LChild 의 RChild 10 을회전시켜그것이부모노드인 7 의위치로 삽입된노드 8 은노드 10 과의연결을끊고노드 7 의 RChild 로 루트의 LChild 10 을중심으로회전이이루어져 10 이새로운트리의루트로 원래의루트와연결된부모노드의링크는새로운루트인노드 10 과연결 7
기타회전예 RR, RL 은 LL, LR 에대칭적인경우 예제 : (a) 는노드 10 의삽입으로인해루트 30 을기준으로 LL 회전이필요 (b) 는노드 30 의삽입으로인해루트 10 을기준으로 RR 회전이필요 (d) 는노드 60 의삽입으로인해 RR 회전이필요한경우 8
AVL AVL 트리 가장먼저시도된이론 균형을잡기위해트리모습을수정 실제코딩면에서볼때 AVL 트리는매우까다롭고복잡 트리의균형 탐색효율 O(lgN) 을보장 삽입, 삭제될때마다균형파괴여부검사하는시간이필요 트리를재구성 (Rebuilding) 하는시간이필요 9
자체조정트리 균형트리 최악의경우에도무조건 lgn 시간에탐색 루트로부터리프까지가는경로를최소화 자체조정트리 (Self-Restructuring Tree) 모든노드가동일한빈도 (Frequency) 로탐색되는것이아님 무조건균형을유지할것이아니라자주탐색되는노드를루트근처에갖다놓는것이더욱유리 10
조정방법 I 자체조정트리 어떤노드가탐색될때마다그노드를바로위부모노드로올리는방법 한번의회전만으로충분함. 예 : 키 3 인노드탐색결과 11
조정방법 II 자체조정트리 어떤노드가탐색되면그노드를아예전체트리의루트로올리는방법 한번탐색된노드는이후에탐색될가능성이높다고간주 연속적인회전이필요 예 : 노드 3 의탐색결과. 단, 회전시마다자식노드의오른쪽서브트리는부모노드의왼쪽서브트리로연결됨. 12
조정방법 II 자체조정트리 트리의균형면에서불리노드 1의탐색결과. 트리의높이는줄지않고, 그대로유지됨. 13
스플레이 (Splay, 벌림 ) 조정방법 II 를개선 스플레이 탐색된노드를루트로올리되, 한번에두레벨씩위로올림. 키 3 인노드를탐색. 루트에서키 3 까지는 Left-Left. Left-Left 또는 Right-Right 를지그지그 (Zig-Zig) 경우라부름 지그지그구성에서는두레벨을올리기위해서올려질노드의부모노드를먼저회전시키고, 노드 3 은나중에회전시킴으로조정방법 II 와는다른결과를보임. 14
스플레이 스플레이 올리고자하는노드가그보다두레벨위의노드로부터 Left- Right 또는 Right-Left 경로를따라내려올때를지그재그 (Zig- Zag) 경우라부름 지그재그에대한처리는 AVL 의 LR 또는 RL 회전과완전히동일 두레벨씩위로올렸을때, 최종적으로루트노드와레벨차이가하나만날수도있다. 이경우에는 AVL 과마찬가지로한번만회전을가하면된다. 15
스플레이에의한균형 스플레이 LChild, RChild 링크가벌어져서 (Splay) 활용됨으로인해균형에유리 스플레이기법 트리의균형보다는노드자체의탐색빈도를기준으로함. 어떤노드가상대적으로다른노드보다자주사용된다면유리한구조 모두동일한빈도로사용된다면여전히트리의균형이중요 16
AVL 트리, 2-3 트리 2-3 트리 AVL은균형트리를지향 2-3 트리는완전균형트리를지향 AVL 트리에비해상대적으로단순한논리. 2-3 트리의노드 2- 노드 (Two Node): 자식노드가 2 개이고키가 1 개인노드 3- 노드 (Three Node): 자식노드가 3 개이고키가 2 개인노드 왼쪽자식 (Left Child), 중간자식 (Middle Child), 오른쪽자식 (Right Child) 키크기는 12 < 50 < 65 < 90 <100 17
리프노드 2-3 트리 2- 노드또는 3- 노드모두가능 18
2-3 트리의삽입 이진탐색트리와마찬가지로리프노드에삽입 키 39 의삽입. 이진탐색트리라면 40 보다작으므로 40 의 LChild 노드를만들어삽입. 2-3 트리에서리프는 3- 노드일수있으므로, 키 39 인레코드와키 40 인레코드가합쳐져서하나의노드 키 38 의삽입. 이번에는하나의노드에세개의키가들어감. 3- 노드의키는두개까지만허용. 중간키 39 를지닌레코드가부모노드로올라감. 작은키 38 과큰키 40 이좌우로분리 (Split). 이후, 키 37 을삽입한모습 19
2-3 트리의삽입 키 36 의삽입. 리프노드에키 36, 37, 38 이존재. 중간키 37 이부모노드로올라가고나머지는분리 부모노드의키가 30, 37, 39 로바뀜. 중간키인 37 을그위부모노드로올리고자신은키 30 인노드와 39 인노드로분리 키 39 인노드는키 37, 50 인부모노드의중간자식으로. 키 36 은키 30 의오른쪽자식으로, 키 38 은키 39 의왼쪽자식으로들어간다. 20
2-3 트리의삽입 키 35, 34, 33까지삽입완료. 키 32의삽입. 중간키 33이부모노드로. 부모노드의중간키 33이그위로. 루트노드의키가 3 개. 새로운루트를만들어자신의중간키 37을올림. 나머지키를분리하여키 33과키 50인노드로 21
높이 2-3 트리의삽입 반복된삽입에도 2-3 트리의높이는좀처럼증가하지않음. 3- 노드를사용해서최대한레코드를수용. 이진탐색트리의높이는삽입할때마다리프노드아래로 1만큼자람.2-3 트리의높이는삽입노드로부터루트노드까지경로가 3-노드로꽉찬경우에한해서루트위쪽으로 1만큼자람. 22
2-3 트리의삭제 왼쪽또는오른쪽자매노드를살핌 하나라도 3- 노드가있으면빌려오되반드시부모노드를거쳐서빌려옴. 키 1, 4 로구성된왼쪽자매노드의키 4 인레코드가부모노드로올라가는대신부모노드의키 5 인레코드가삭제된키 10 의자리로들어감. 23
2-3 트리의삭제 키 5 의삭제. 왼쪽오른쪽 3- 노드가없어노드자체가삭제된다. 따라서자식노드가두개로줄어들어부모노드도 2- 노드로바뀌어야함. 부모노드의키중하나가삭제된노드의자매노드로이동한다. 여기서는부모노드의왼쪽키가삭제된노드의왼쪽자매노드로이동. 물론부모노드의오른쪽키가오른쪽자매노드로이동할수도있음. 키 20 인노드를삭제한최종결과. 24
2-3 트리의삭제 키 40 의삭제. 키 80 노드로부터빌릴키가없으므로키 40 인노드는삭제. 부모노드인키 45 노드는더이상 2- 노드상태를유지할수없어삭제된노드의자매노드인키 80 노드로합쳐짐. 키 45 노드가빈자리로남게됨. 왼편의자매노드인키 4 노드를보지만빌릴수없음. 키 45 노드는삭제. 키 35 인루트노드가 2- 노드상태를유지할수없어왼쪽자매노드와합쳐짐. 루트노드자체가삭제되고트리높이가감소. 그러나균형상태는유지. 25
2-3 트리 스택 삽입, 삭제를위해서는어떤노드의부모노드를접근해야함. 삽입시에중간키를올리기위해서, 또삭제시에부모노드의키를아래로내리기위해서 이진트리는부모노드로부터자식노드로가는포인터만유지 루트로부터내려가면서만나는모든노드를가리키는포인터값을계속적으로스택에푸쉬해놓으면팝에의해직전의부모노드를접근할수있음. 26
2-3 트리 탐색효율 모든노드가 3- 노드일때가장높이가낮음. 레벨 0 의루트노드가 3 노드라면그내부에는 2 개의레코드가들어감. 레벨 1 에 3 개의 3 노드가있다면그내부에는각각 2 개의레코드가들어감. 레벨 h 까지의레코드수 N = 2(1 + 3 + 3 2 +... + 3 h ) 3 h 트리높이 h 는최대레벨수와일치하므로결과적으로 h log 3 N 최악의경우는모든노드가 2- 노드로서트리의높이 h log 2 N 2-3 트리에는 2- 노드와 3- 노드가섞여있으므로효율은 O(log 2 N) 과 O(log 3 N) 사이에존재. 이진탐색트리는최악의경우 O(N) 으로전락 2-3 트리는항상완전균형트리를유지하므로최악의경우에도효율을보장 3- 노드는비교해야할키가 2 개이므로비교의횟수가증가 3- 노드는자식을가리키는포인터가 3 개이므로자식노드가없다면 2- 노드에비해널포인터가차지하는공간적부담 널포인터는리프노드에다수가분포 27
2-3-4 트리 O(log 2 N) 과 O(log 4 N) 사이의탐색효율 추가로 4- 노드를정의 자식노드로가는링크 (Link) 가 4 개이고키가 3 개인노드 왼쪽자식 (Left Child), 오른쪽자식 (Right Child), 왼쪽중간자식 (Left Middle Child), 오른쪽중간자식 (Right Middle Child) 으로구분 키크기는 10 < 30 < 65 < 75 < 80 < 95 < 100 28
2-3-4 트리 중요성높이를 log 4 N 으로조금더낮추기위해서? 리프노드근처의널포인터공간도 2-3 트리에비해서더많아짐. 필요시최대 3 개의키를비교해야하는시간적부담. 그렇다면왜? 단일패스삽입 2-3 트리는리프노드가꽉차면중간자식을부모노드로올리고, 만약부모노드가꽉차면다시부모노드의중간자식이그위로올려짐. 2-3-4 트리는이러한사태를배제하기위해, 루트로부터삽입위치를찾아서내려가는도중에 4- 노드를만나면무조건제거하면서내려감. 스택이불필요하나의삽입작업이트리모습을바꾸면서내려가는동안, 동시에이어서두번째삽입작업이루트로부터내려올수있음. ( 파이프라이닝 ) 레드블랙트리와의연관성레드블랙트리로구현 29
삽입시 4- 노드의제거 1) 루트가 4- 노드인경우. 중간키인 Y 가올라가서트리높이증가. 2) 내려가면서만난 4- 노드가 2- 노드의자식노드일경우. 중간노드를올리되, 나머지노드는분리되어부모노드의왼쪽자식과중간자식으로붙게됨. 높이는그대로유지. 3) 내려가면서만난 4- 노드가 3- 노드의자식노드일경우. 부모노드가 4- 노드로바뀌면서왼쪽중간자식, 오른쪽중간자식으로분리시켜붙임. 트리높이는그대로유지. 30
레드블랙트리 레드블랙트리 (Red-Black Tree) 2-3-4 트리를이진트리로표현한것레드블랙트리의링크 (Link) 는색깔을지님포인터변수에색깔이라는속성을추가노드자료구조키를포함한데이터필드, LChild 포인터, RChild 포인터 LColor, Rcolor 색깔변수하나만사용하려면부모노드로부터자신을향한포인터의변수를표시 31
2-3-4 의 RB 표현 모든 2-3-4 트리는레드블랙트리로표현가능 2- 노드는그대로. 3- 노드는왼쪽또는오른쪽키를루트로하는이진트리로. 따라서트리모양이유일하지는않음. 빨강링크는원래 3- 노드, 4- 노드에서같은노드에속했었다는사실을나타냄. 4- 노드의레드블랙표현은유일함. 32
레드블랙트리의속성 1) 트리를내려오면서연속적인빨강링크 2 개는허용하지않음 2) 루트로부터리프노드까지검정링크의수는모두동일하다. 3) 2 개의자식노드가모두빨강링크일때만 4- 노드에해당한다. 1) 번속성의증명 만약첫트리처럼연속된빨강이존재한다고가정하면,X-Y 가빨강이므로그것은둘째트리에서나왔을것이고, 이는다시셋째트리에서유래되었을것. 한데셋째트리의 4- 노드는항상그아래트리처럼유일한모습의레드블랙표현을지닌다. 따라서연속적인빨강이 2 개나올수없음 33
사용이유 레드블랙트리 2-3-4 트리의복잡한노드구조그리고복잡한삽입삭제코드 레드블랙트리는 이진탐색트리의함수를거의그대로사용 2-3-4 트리의장점인단일패스삽입삭제가그대로레드블랙트리에도적용. 언제회전에의해균형을잡아야하는지가쉽게판별됨. 34
레드블랙의 4- 노드제거 루트노드가 4- 노드인경우 (a) 의 2-3-4 트리를레드블랙으로표현한것이 (a') 2-3-4 트리에서 4- 노드를제거하기위해서는 (b) 와같이중간키로루트로하는트리로변형 (a') 의레드블랙트리는이미 (b) 의갖춰져있음 링크의색깔만빨강에서검정으로뒤집음 (Color Flip: 색상반전 ) 35
레드블랙의 4- 노드제거 부모노드가 2- 노드인경우에 4- 노드인자식노드를제거 2-3-4 트리 (a) 에서 4- 노드를제거하면 (b) 가됨. (a) 를나타내는레드블랙트리는 (a') (a') 에서 4- 노드를제거하는과정은키 X 를중심으로부모와자식의링크색상을반전. X-Z 간의링크를검정에서빨강으로, 그리고 X-W, X-Y 간의링크를빨강에서검정으로바꾸면 (b') 이됨. 만약 (b') 을루트를중심으로오른쪽으로회전 (LL Rotation) 시켜도동일한 2-3-4 트리를나타냄. 36
레드블랙의 4- 노드제거 부모노드가 3- 노드인경우에 4- 노드인자식노드를제거 4- 노드인 W 를중심으로부모와자식링크에대해색상을반전 Z-Y-W 로이어지는빨강링크가연속으로 2 개 연속적인 2 개의빨강링크를허용하지않으므로이를피하기위해회전 (RR Rotation) 을가함. 37
레드블랙트리구성예 왼쪽칼럼이레드블랙트리, 오른쪽칼럼은상응하는 2-3-4 트리 키 20 이들어올때루트는아직 4 노드상태가아니므로빨강링크로삽입 키 30 이삽입되면 2 개의빨강링크가연속되므로회전. 결과키 20 을루트로하는트리가좌우에빨강링크이므로 4 노드임이표시됨. 38
레드블랙트리구성예 키 40 이루트로들어오는순간루트가 4- 노드이므로색상반전에의해이를제거한뒤에삽입 키 50 이삽입될때두개의연속된빨강링크이므로회전에의해서변형 키 60 이삽입되려내려올때, 4- 노드인 40 의부모와자식의링크색상이반전 39
레드블랙트리의효율 위예 이진탐색트리에 10, 20,..., 60 의순으로삽입하면결과는모든노드가일렬로늘어서서최악의효율. 탐색효율 삽입삭제를위한코드의간결성은이진탐색트리와비슷하면서도 레드블랙트리의높이는 O(log 2 N) 에근접 레드블랙트리는회전에의해서어느정도균형을이룸. AVL 은회전시기를판단하기위해복잡한코드실행. 회전방법역시복잡한코드실행. 그에따를실행시간증가 레드블랙트리는빨강링크의위치만으로회전시기를쉽게판단, 회전방법도간단. 40
B- 트리 B 트리 (B Trees) 2-3 트리, 2-3-4 트리개념의확장 2-3-4-5-. M: M 웨이트리 (M-way Tree) 최대링크수가 M 개. M 이커질수록하나의노드내부에서비교의횟수가증가하고또, 빈포인터공간도많아지지만트리의높이는그만큼낮아진다. 외부탐색 (External Search) 방법 외부저장장치인파일로부터찾는레코드를읽어오기위함. 데이터베이스탐색방법의일종 파일로부터메인메모리로읽혀지는기본단위를페이지 (Page) 라함. 외부탐색에서알고리즘의효율을좌우하는것은입출력시간 입출력시간은페이지를몇번입출력했는가에좌우 41
B- 트리 한페이지에노드하나를저장한다고가정. 페이지접근 (Access) 횟수를줄이기위해루트노드는항상메인메모리에올려놓음. 포인터는디스크번호와페이지번호에의해표시. 루트의 LChild 인노드 B 는디스크 1 번의페이지 0 에저장. 42
B- 트리 검색효율 2- 노드, 3- 노드,..., M- 노드를모두감안하면평균적인링크수는 M/2 O(log (M/2) N) B- 트리의변형레코드자체가차지하는공간으로인해하나의노드즉, 하나의페이지안에들어갈수있는레코드수가제한됨. 자식노드를가리키는포인터수가제한됨. 2-3-4 트리라면 4- 노드하나에레코드 3 개와자식노드를가리키는포인터 4 개를둘수있음. 어떤노드가자식노드 100 개를가리키게하려면 2-3-4-5... -100 트리를구성해야하는데이때의 100- 노드에는레코드 99 개가들어가야함. 레코드크기가커질수록한페이지에이렇게많이넣을수는없음. 하나의노드가가질수있는 M 값이작아지면트리의높이가커지고, 트리를따라내려오면서만나는모든노드 ( 페이지 ) 가많아지므로입출력 (Page I/O) 횟수가증가함. 레코드와링크정보를하나의노드안에몰아넣은이러한방식은외부탐색의효율을좌우하는입출력면에서는상당히불리. 43
B- 트리 B- 트리의변형 일반적인 B 트리는내부노드에는키값만넣고, 실제레코드는외부노드즉, 리프노드에몰아넣음. 내부노드의키는리프노드의레코드를찾기위한일종의인덱스기능수행하게함으로써 M 의값을대폭증가하여트리높이를대폭감소시킴. 44
B- 트리 고정된 M 을사용 모든 M 값을크게할경우필요한페이지수가급증 1, M, M 2, M 3... 으로기하급수적으로늘어남. 레코드가몇개없는페이지, 사용되지않는페이지로인한공간낭비 레벨별 M 값의변화 루트에 M을작게잡고리프근처에 M만크게잡을경우트리를다내려온다음에리프근처에서노드하나에하는수많은키에대해서일일이순차적인탐색 존재 트리의위에서아래로내려오면서검색범위를적절히축소. 루트근처의 M 값을 2048, 리프근처의 M 값은 1024 로했을때, 10 억개의레코드에대해서 3 번정도의페이지입출력으로끝낼수있음. 45