Chapter 2. AVL Trees Search (4)

1. AVL Tree 특징

특징

1. 2 개의 Subtree 들간에 depth 차이 <= 1
2. 4 개의 회전 ( LL, LR, RL, RR ) 에 의해 tree 재구성
3. 포인터 변화는 5 개 이내로 국한
4. 예: B C G E F D A 순으로 입력될 때
5. Search cost : 1.44log2(N+2)

2. AVL Tree 재구성