13장. 균형 탐색 트리 and the pain you must suffer to learn them Internet Computing Laboratory @ KUT Youn-Hee Han

1. AVL 트리 AVL 트리 균형의 점검 G. M. Adelson-Velskii and E. M. Landis 항상 균형을 유지하는 이진 탐색 트리 (Binary Search Tree) 삽입 삭제가 일어날 때마다 트리의 균형 상태를 점검하고 복원 트리 T가 왼쪽, 오른쪽 서브 트리 TL, TR을 가짐 TL과 TR이 높이 균형을 이룸 |hL – hR| <= 1 균형의 점검 균형 인수(Balance Factor)를 사용 노드마다 오른쪽 서브트리의 높이에서 왼쪽 서브트리의 높이를 뺀 것 Data Structure

1. AVL 트리 AVL 트리 Non-AVL 트리 Data Structure

1. AVL 트리 AVL 트리의 Balance Factor의 조건 Balance Factor의 범위가 넘어선 노드 확인 반드시 -1, 0, +1 중 하나. 균형 트리 (Balanced Tree)의 정의 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1인 트리 Balance Factor의 범위가 넘어선 노드 확인 삽입, 삭제가 일어나면 반드시 해당 위치로부터 루트까지 올라가면서 모든 노드에 대한 Balance Factor가 그 범위를 넘어섰는지 확인 Balance Factor 왼쪽 트리로부터 노드 K를 삭제함에 따라 균형이 깨어진 것이 오른쪽 트리. Balance Factor 가 AVL 트리 조건에 맞지 않음 Data Structure

1. AVL 트리 AVL 트리의 선언 typedef struct { char Name[ ]; 이름 필드 node* LChild;          왼쪽 자식을 가리키는 포인터 node* RChild;          오른쪽 자식을 가리키는 포인터 int balance_factor; } node;                  노드는 구조체 타입 typedef node* Nptr;  노드를 가리키는 포인터를 Nptr 타입으로 정함 Data Structure

Node 4 attached to new parent 1. AVL 트리 회전(Rotation)에 의한 균형 회복 What is Rotation? Rotation with Re-attachment 1 2 3 5 6 4 Node 4 attached to new parent Data Structure

1. AVL 트리 A 회전(Rotation) 종류 Insert Y LL LR RL RR 불균형 노드 A 와 새 노드 Y의 위치를 기준으로 다음과 같이 분류 LL (Left Left Rotation) LR (Left Right Rotation) RL (Right Left Rotation) RR (Right Right Rotation) A Insert Y LL LR RL RR Data Structure

1. AVL 트리 LL 회전 불균형 노드 A의 왼쪽 서브트리의 왼쪽 서브트리에 새 노드 Y가 삽입된 경우 LL의 RChild에 삽입되는 경우와, LChild에 삽입되는 경우 -2 -2 12 12 L L L L 7 7 20 20 3 3 10 10 2 5 Data Structure

1. AVL 트리 LL 회전 원리 Single Rotation (with or without) reattachment Data Structure

1. AVL 트리 LL 회전 Data Structure

1. AVL 트리 RR 회전 원리 Single Rotation (with or without) reattachment RR 회전 예 Data Structure

1. AVL 트리 LR 회전 불균형 노드 A의 왼쪽 서브트리의 오른쪽 서브트리에 새 노드 Y가 삽입된 경우 원리 – Double Rotation with Reattachment Data Structure

1. AVL 트리 LR 회전 예 Data Structure

1. AVL 트리 RL회전 불균형 노드 A의 오른쪽 서브트리의 왼쪽 서브트리에 새 노드 Y가 삽입된 경우 원리– Double Rotation with Reattachment Data Structure

1. AVL 트리 RL회전 예 Data Structure

1. AVL 트리 4개의 회전 종류에 없는 간단한 회전 L회전, R회전 Data Structure

1. AVL 트리 AVL 트리 트리의 균형 가장 먼저 시도된 균형 트리 이론 균형을 잡기 위해 트리 모습을 수정 탐색효율 O(lgN)을 보장 삽입과 삭제 시간이 많이 걸림 삽입, 삭제 될 때마다 불균형 여부 검사하는 시간이 필요 트리를 재구성(Rebuilding)하는 시간이 필요 통계적으로 삽입, 삭제 이후… 회전이 필요없는 경우: 54% LL/RR 회전이 필요한 경우: 23% LR/RL 회전이 필요한 경우: 23% Data Structure

2. 스플레이(Splay) 기법 일반적인 균형 트리 (Balanced Tree)의 특징 균형트리는 최악의 경우에라도 무조건 lgN 시간에 탐색하기 위함 루트로부터 리프까지 가는 경로를 최소화하기 위함 하지만, 모든 노드가 동일한 빈도(Frequency)로 탐색되는 것은 아님 자체 조정 트리 (Self-Restructuring Tree) – Splay Tree Sleator and Tarjan 탐색의 빈도를 기준으로 스스로 트리 모습을 재 구성하는 트리 무조건 균형을 유지할 것이 아니라 자주 탐색되는 노드를 루트 근처에 갖다 놓는 것이 더욱 유리 A splay tree is a self-balancing binary search tree with the additional unusual property that recently accessed elements are quick to access again. – [wikipedia] Data Structure

2. 스플레이(Splay) 기법 조정방법 I 어떤 노드가 탐색될 때마다 그 노드를 바로 위 부모 노드로 올리는 방법 한번의 회전만으로 충분함. 예: 아래 그림에서 키 3인 노드 탐색결과 탐색될 때 마다 부모로 올라가므로 탐색 빈도가 높은 노드들은 점차 루트 주위로 모인다. Data Structure

2. 스플레이(Splay) 기법 조정방법 II 어떤 노드가 탐색되면 그 노드를 전체 트리의 루트로 옮김 한번 탐색된 노드는 이후에 탐색될 가능성이 높다고 간주 연속적인 회전이 필요 예: 노드 3의 탐색결과. 회전시마다 자식노드의 오른쪽 서브트리는 부모노드의 왼쪽 서브트리로 연결됨 Data Structure

2. 스플레이(Splay) 기법 조정방법 II의 단점 트리의 균형 면에서 불리 노드 1의 탐색결과. 트리의 높이는 줄지 않고, 그대로 유지됨 Data Structure

2. 스플레이(Splay) 기법 스플레이(Splay, 벌림) Zig-Zig step 조정방법 II를 개선 탐색된 노드를 루트로 올리되, 한번에 두 레벨씩 위로 올림. Zig-Zig step 두 번의 step 1st 올림: 탐색된 노드의 부모 노드를 기준으로 올림 2nd 올림: 탐색된 노드 자체를 기준으로 올림 AVL에서의 Single/Double Rotation회전 원리와 다른 방법임에 유의 Data Structure

2. 스플레이(Splay) 기법 Zig-Zig step 예 키 3인 노드를 탐색. 루트에서 키 3까지는 Zig-Zig. Data Structure

2. 스플레이(Splay) 기법 Zig-Zag step Zig-Zag step 예 AVL의 LR 또는 RL회전과 완전 동일 Double Rotation Data Structure

2. 스플레이(Splay) 기법 Zig step Data Structure

2. 스플레이(Splay) 기법 스플레이 트리 (Splay Tree) 의 특징 LChild, RChild 링크가 벌어지는 (Splay) 효과로 인해 균형에 유리. 하지만, 트리의 균형보다는 노드 자체의 탐색빈도를 더 중시함. 어떤 노드가 상대적으로 다른 노드보다 자주 사용된다면 유리한 구조 모두 동일한 빈도로 사용된다면 Splay의 장점은 없음 Zig-Zig Zig Zig-Zig Data Structure