Chapter 8. AVL Search Trees Internet Computing Laboratory @ KUT Youn-Hee Han

0. BST Reviews Binary Search Tree (이진 탐색 트리)의 삭제 When we delete a node, we need to consider how we take care of the children of the deleted node. This has to be done such that the property of BST is maintained.

0. BST Reviews Binary Search Tree (이진 탐색 트리)의 삭제 Flash 예제 (Click) Data Structure

0. BST Reviews Binary Search Tree (이진 탐색 트리)의 삭제 get max of left subtree get min of right subtree Data Structure

0. BST Reviews 키 Lee인 노드를 찾기 키 Yoo인 노드 찾기 Park, Kim, Lee(왼쪽 트리) 대 Cho, Kim, Lee(오른쪽 트리) 키 Yoo인 노드 찾기 Park, Seo, Yoo: (왼쪽 트리) 대 Cho, Kim, Lee, Park, Seo, Yoo (오른쪽 트리) Data Structure

0. BST Reviews 균형 최악의 경우 탐색은 Leaf Node까지 왼쪽 트리는 완전한 균형. 오른쪽 트리는 왼쪽 서브트리의 Heighr가 0(빈 트리), 오른쪽 서브트리(Root가 Kim인 트리)의 높이가 5로서 균형이 현저히 무너짐. 최악의 경우 탐색은 Leaf Node까지 왼쪽 트리는 최악의 경우에도 높이가 3. 오른쪽 트리는 최악의 경우 높이 6를 모두 타고 내려와야 함. 오른쪽 트리는 연결 리스트(Linked List)에 가까움. 연결이 한쪽으로 일직선으로(Linear Structure) 진행하는 트리  편향 이진트리 (Skewed Binary Tree) Data Structure

0. BST Reviews 이진 탐색 트리에서의 탐색 효율 균형이 잘 잡혀있는 경우 균형이 무너진 경우 높이는 lgN에 가까움. 높이만큼 키 비교를 요함. 효율 O(lgN) 균형이 무너진 경우 최악의 경우 연결 리스트에 가까움 효율 O(N) Data Structure

1. AVL Tree Basic Concepts Motivation Complexity of BST Average case: O(log n) Inserting sorted data Worst case: O(n) If BST is unbalanced, the efficiency is bad. Balance (복습) Balance factor (B) = HL – HR Balanced binary tree: |B|  1 HL HR Data Structure

1. AVL Tree Basic Concepts AVL Tree: a binary search tree in which the heights of the subtrees differ by no more than 1 |HL-HR|<=1 for all nodes Cf. HL-HR is called balance factor An AVL is a balanced tree Invented by G.M Adelson-Velskii and E.M. Landis, 1962. Data Structure

1. AVL Tree Basic Concepts AVL Tree Example Data Structure

1. AVL Tree Basic Concepts -1 1 Is It an AVL Tree? 10 40 30 45 20 35 25 60 7 3 8 1 5 Data Structure

1. AVL Tree Basic Concepts AVL Trees Non-AVL Trees Data Structure

1. AVL Tree Basic Concepts 삽입과 삭제시 고려졈 Balance Factor의 범위가 넘어선 노드 확인 삽입, 삭제가 일어나면 반드시 해당 위치로부터 루트까지 올라가면서 모든 노드에 대한 Balance Factor가 그 범위를 넘어섰는지 확인 typedef struct { char Name[ ];        이름 필드 node* LChild;          왼쪽 자식을 가리키는 포인터 node* RChild;          오른쪽 자식을 가리키는 포인터 int balance_factor; } node;                  노드는 구조체 타입 typedef node* Nptr;  노드를 가리키는 포인터를 Nptr 타입으로 정함 Disadvantage: needs extra storage for maintaining node balance Data Structure

2. Balancing AVL Trees Inserting a node into an AVL tree 1. Connect the new node to a leaf node with the same algorithm with BST insertion 2. Check the balance of each node 3. If an unbalanced node “r” is found, rebalance it and then continue up the tree Not all insertion breaks the balance Data Structure

2. Balancing AVL Trees All unbalanced tree fall into one of these 4 cases At the nearest unbalanced ancestor r from the new node x Left of left: A subtree (r) that is left high has also become left high Right of right: A subtree (r) that is right high has also become right high Data Structure

2. Balancing AVL Trees All unbalanced tree fall into one of these 4 cases At the nearest unbalanced ancestor r from the new node x Right of left: A subtree (r) that is left high has included right high subtree Left of right: A subtree (r) that is right high has included left high subtree Data Structure

Node 4 attached to new parent 2. Balancing AVL Trees Rotation: switching children and parents among two or three adjacent nodes to restore balance of a tree. Rotation with Re-attachment 1 2 3 5 6 4 Node 4 attached to new parent Data Structure

2. Balancing AVL Trees A rotation may change the depth of some nodes, but does not change their relative ordering. Mar May Nov rotation -1 -2 Insertion-> unbalancing -> rebalancing Data Structure

2. Balancing AVL Trees Case I: Left of left 경우  “LL Rotation” 으로 해결 불균형 노드 r의 왼쪽 서브트리의 왼쪽 서브트리에 새 노드 Y가 삽입된 경우 마지막의 RChild에 삽입되는 경우와, LChild에 삽입되는 경우 BF: 2 BF: 2 12 L 12 L L 7 20 L 7 20 3 10 3 10 5 2 Data Structure

2. Balancing AVL Trees LL Rotation 원리 – Single Right Rotation After rotation, BF(x) = 0, BF(r) = 0,-1,1 * r: nearest ancestor of the new node whose BF(r) is +2 or -2 Data Structure

2. Balancing AVL Trees LL Rotation Examples Data Structure

2. Balancing AVL Trees Case II: Right of Right 경우  “RR Rotation” 으로 해결 불균형 노드 r의 오른쪽 서브트리의 오른쪽 서브트리에 새 노드 Y가 삽입된 경우 RR Rotation 원리 – Single Left Rotation After rotation, BF(x) = 0, BF(r) = 0,-1,1 Data Structure

2. Balancing AVL Trees RR Rotation Examples Data Structure

2. Balancing AVL Trees Case III: Right of Left 경우  “LR Rotation” 으로 해결 불균형 노드 r의 왼쪽 서브트리의 오른쪽 서브트리에 새 노드 Y가 삽입된 경우 LR Rotation 원리 – Double Rotation After rotation, BF(x) = 0, BF(r) = 0,-1,1 Data Structure

2. Balancing AVL Trees LR Rotation Examples Data Structure

2. Balancing AVL Trees LR Rotation Examples Data Structure

2. Balancing AVL Trees Case IV: Left of Right 경우  “RL Rotation” 으로 해결 불균형 노드 r의 오른쪽 서브트리의 왼쪽 서브트리에 새 노드 Y가 삽입된 경우 RL Rotation 원리 – Double Rotation After rotation, BF(x) = 0, BF(r) = 0,-1,1 Data Structure

2. Balancing AVL Trees RL Rotation Examples Data Structure

3. Efficiency of AVL Trees 가장 먼저 시도된 균형 트리 이론 균형을 잡기 위해 트리 모습을 수정 실제 코딩면에서 볼 때 AVL 트리는 매우 까다롭고 복잡 트리의 균형 탐색효율 O(lgN)을 보장 삽입, 삭제 될 때마다 균형 파괴여부 검사하는 시간이 필요 트리를 재구성(Rebuilding)하는 시간이 필요 통계적으로 삽입, 삭제 이후… 회전이 필요없는 경우: 54% LL/RR 회전이 필요한 경우: 23% LR/RL 회전이 필요한 경우: 23% Data Structure