AVR 트리

AVR 트리

1. 이진탐색 트리 성질 충족 (가운데가 기준)

2. 모든 노드의 balance Factor 절대값이 1 이하인 경우(1포함)

3. AVR의 균형유지(balance)유지

 

Balance Factor

임의의 node에 대해서, 다음을 balance factor로 정의

(좌측 Subtree의 높이) - (우측 Subtree의 높이)

 

루트노드와 최하단의 leaf와의 거리 depth

 

 

1. LL 회전( Left-Left-Rotation)

삽입된 노드가 왼쪽 자식의 왼쪽 SubTree에 있는 경우

 

2. RR 회전( Right-Right-Rotation)

1기준으로 보면 오른쪽 자식의 오른쪽 subtree

 

3. LR회전

삽입된 노드가 왼쪽자식의 오른쪽 자식으로 삽입

 

4. RL 회전

오른쪽 자식의 왼쪽 서브트리에 들어감