AVL Tree

AVL Tree Idea

Search Performance

직관

• 왼 / 오 무게가(개수가) 비슷하면 성능이 좋을 것이다. (log n과 n은 매우 큰 차이 ..!!)
• 6이 root에 있는 한 해결불가 > 루트가 바뀌는건 필수적임
• if) 4가 루트가 되면 6의 왼쪽 child가 비어서 포인터만 이동하면 child 2개로 조정할 수 있다. 

 

AVL Tree Definition

• L: left sub tree 높이
• R: right sub tree 높이

> 각각의 노드는 L과 R인 두개의 label을 가진다.

조건: l L-R l <2 즉, L-R = 0, 1, -1 중 하나

 

> 만약 AVL Tree의 노드가 n개라면 높이는 O(lonN)이 된다.

l L-R l < 2가 모든 노드에서 성립하려면 노드 개수가 많아짐

→ 높이가 상대적으로 낮음

 

• Down Sequence Definition
  • LLRLRRLLRL..L과 R의 string
  • 루트에서부터의 움직임을 나타낸 것 (path) 
• Terminated Down Sequence
  
  • 끝까지(더이상 못 갈때까지) 감
  • 여기서는 빨간색으로 표시할 예정 

Proof

Idea

All Terminated Sequences

terminated sequence와 R, L label 들을 나타낸 것 

 

observation

• 가장 긴 sequence는 가장 짧은 것의 약 2배이다.
• 가장 짧은 sequence위쪽의 모든 레벨은 노드가 존재한다. (빈 곳이 없다.) 
  • 가능한 모든 노드가 존재한다. 

조건을 만족하려면 longest과 shortest의 label은 각각 위와 같은 상황을 만족시킨다.

• longest: label이 1씩 감소한다.
• shortest: label이 2씩 감소한다. (최대 차이가 2임) 

Count the nodes

• 루트에서 가장 큰 label이 k일 때, 트리의 높이는 k+1 이다.
• shortest terminated down sequence는 k/2 이다. (longest 와 shortest가 약 2배 차이)
• 즉, 최소한 2^(k/2)개의 노드가 존재한다는 것이다.
  • 2^(k/2) <= N <= 2^k
  • 2^(k/2) <= N은 k/2 <= log N 을 뜻한다. 즉 k = O(logN)

Insert

Algorithm

• leaf에 노드를 추가한다. 
  • 일단 트리 모양을 해치치 않는 선에서 insert
• 위로 올라가면서 label을 다시 계산한다.
• label 조건이 깨지는 가장 첫 노드에서, ROTATION을 진행한다.
• 끝!

1st Node to Break the Condition

조건이 깨지려면 k쪽에서 insert가 일어나야 한다.

∵ k-1에서 insert가 일어나면 label이 (k-1) + 1 = k 로 해당 노드의 label이 k, k 로 바뀐다.

   label 조건을 만족하므로 따로 바꿀 필요 없음

 

case LL

D근방..밑... 어딘가에서 insert된 것

 

solution ) 

• B를 루트로 올린다.
  • B는 (k,k) : 왼쪽엔 새로운 insert된 노드가 추가되고, 오른쪽엔 밑으로 내려간 A가 추가 된다. 
• A는 B의 오른쪽 child가 된다.
  • A(k-1, k-1) 로 바뀐다. 

 

case LL rotation 후

case LR

E근방..밑... 어딘가에서 insert된 것

case LR의 문제상황과 solution

solution)

• E를 위로 올린다. (루트로 만든다.)
  • E(k,k)
• B는 E의 왼쪽 child
  • B(k-1, k-1) 혹은 (k-1, k-2)
• A는 E의 오른쪽 chile
  • A(k-2, k-1) 혹은 (k-1, k-1)