[자료구조] Tree - AVL Tree

자료구조 05 - 4 / Tree - AVL Tree / 

---

정의 

AVL 트리(발명자 Adelson-Velsky and Landis), 이진탐색 트리 구조로 스스로 균형을 잡는 데이터 구조중 최초 발명

두 자식 SubTree의 Height는 항상 1 만큼 차이를 유지, 1보다 큰 경우 스스로 균형을 잡음(Rotation)

balance factor = 
abs( height(left subtree) - height(right subtree) )

A의 서브트리의 높이의 차가 1 보다 커지는 경우 Rotation을 진행

 

 

 

 

 

 

원리 

Rotation 이해하기

Single Rotation (raywenderlich.com)

https://github.com/raywenderlich/swift-algorithm-club/tree/master/AVL%20Tree

불균형이 발생하면

root의 SubTree 중 높이가 높은 SubTree의 최상단 노드를 Pivot

Pivot의 높이가 높은 SubTree를 Opposite SubTree

Pivot의 높이가 낮은 SubTree를 Rotation SubTree

 

1. Rotation SubTree - Pivot 간의 Edge를 제거

2. Rotation SubTree를 Root (Pivot의 부모 노드)의 Left Child로 연결

3. Root - Pivot 간의 Edge를 제거

4. Root를  Pivot의 Right Child로 연결

 

위 Rotation은 R Rotation (Single Right Rotation)

https://ratsgo.github.io/data%20structure&algorithm/2017/10/27/avltree/

Double Rotation (rasgo_blog)

https://ratsgo.github.io/data%20structure&algorithm/2017/10/27/avltree/

First Rotation : W중심으로 Left Rotation (A 당겨 내리기)

Second Rotation : W 중심으로 Right rotation (D 당겨 내리기)

 

위 Rotation은 LR Rotation (Left Right Rotation)

 

Rotation 수행은 부모 자식간의 Edge 수정이므로 O(1) 시간 복잡도 소요

 

추가적으로 생각해볼 내용

추가 및 삭제

추가 또는 삭제 동작은 모두 BST와 동일하게 동작 하지만

동작 후 Rebalance 동작이 필요 ( 추가 또는 삭제된 노드를 포함해서 Rotation)

 

 

rasgo Blog
Wikipedia
raywenderlich.com