[ 자료구조 ] Tree (AVL)

AVL Tree Idea

 

 

아이디어는 다음과 같다. 위의 tree 구조를 살펴 보자. 보기에 아름다운(?) 구조 인가? 아마 대부분 그렇게 생각하지 않을것이다. Tree 가 왼쪽으로 쏠려 있는 모양을 하고 있기 때문이다. 그럼 위의 그림을 직관적으로 봤을떄 어떻게 고치면 높이가 최소화된 Tree 모양이 나올까? 아마 4가 root인 모양으로 변형 시키면 높이가 좀더 낮아질것이라고 생각했을 것이다.

 

 

어떤가 ? 아까 Tree 에 비해 좀더 height가 낮아진 균형이 잡힌 tree 구조로 보일 것이다. 이런식으로  tree구조를 만들어 나가는 과정을 가지게 될것이다.

AVL Tree Definition

• Each Node has Two Labels: L and R
  • L : Height of Left Subtree, R: Height of Right SubTree
• Condition: |L-R| < 2 (제일 중요한 조건), that is , L - R = 0, 1, -1

 

다음과 같이 node에 두개의 label 변수가 추가된다.

 

각 label은 subtree의 height를 뜻한다. 4라고 적혀있으면 6이라 적힌 node에서 빨간 subtree의 맨 아래 노드까지 4번의 edge(막대부분)을 거쳐야 한다는 뜻이다.

 

AVL tree 는 앞의 BST와 다르게 허용이 되는 tree가 있고 안돼는 tree가 존재한다.

 

Height Bound?

• What we want to Prove
• If there are N nodes in an AVL Tree the Height is O(log N)

Proof Idea

 

 

    증명에서 쓰이는 Idea는 다음과 같다. 그림과 같이 루트노드의 왼쪽라벨에서 끝까지 가는 길이 8 이라고 적혀있으면 오 른쪽도 8과 비슷하게 가야 제일 밑의 노드(leaf)에 도착할 수 있다. 이것은 루트노드 뿐만이 아니라 그 아래 노드에서도 모두 적용되는 사항이다. 그렇게 본다면 제일 멀리 있는 leaf 와 제일 가까이에 있는 leaf의 거리는 그렇게까지 차이가 나지 않을 것을 짐작해볼 수 있다. (이 부분에서는 약간의 논리 점프가 있다.)

 

 

검은색 화살표와 빨간색 화살표의 길이는 엄청나게 차이나지 않는다.

 

그리고 빨간 부분의 밑줄까지는 노드의 개수가 가득 차 있는 (1-2-4 형식으로 빡빡하게, height에 비해 노드 개수가 굉장히 많다는 뜻) 모양이다. height에 비해 노드 개수가 굉장히 많다는 의미는 다시 말해 노드 개수에 비해 높이가 작다는 것을 말한다.

 

그래서 결국에는 이 두가지를 합산해보면 우리는 위의 그림의 tree가 상당 부분 이상이 노드가 가득 차 있다는 것을 알수 있다.

Some Definitions (증명을 위해 필요)

• Down Sequence Definition
  • String of L and R, such as, LLRLRRLRLLRLR (내려가는 길을 표시)
  • Represents Movement from Root
  • Notice: Some Down Sequence cannot be followed to the end
    • if there is no child in the direction
  • Terminated Down Sequence
    • Color Impossible Movement with RED( 못가는 곳을 빨간색으로 표시 )
  • Consider the Set of All possible Terminated Down Sequence for an AVL Tree

All Terminated Sequences

 

예시 Tree로 한번 생각해보자.

 

 

Observations

1. The longest Treminated Down Sequences is at most(about) 2 times longer than the shortest

  1) Consider the labels that you see when you move down to the longest and the shortest

 

2. All levels up to the shortest Terminated Down Sequence are FULL

  1) Meaning all possible nodes exist

 

Count the nodes

• (All Calculations maybe off by 1 or 2, that's OK )
• If the maximum label on Root is K
• Then the height of the Tree is K+1
• Then the shortest Terminated Down Sequence is at least K/2
• Meaning that there are at least  Nodes in the Tree
• That is, N is at least 2^k/2N and at most 2^k
• 2^k/2 <= N <=2^k
• 2^k/2 <=N means K/2 <= log N means K = O(log N) !

 

What we know up tp now

 

• If a Tree satisfies the LABEL condition for AVL Tree, then the Height is O(log N)
• So, Search will finish in O(log N) time

 

• But...
• Insert and Delete will change the label
• And may break the condition

 

Next question

• How to keep the conditon after an insert and delete?
• Remember AVL tree Idea section

Insert

• (We will consider only Insert. Similar with Delete)
• The Algorithm
  1. Do the normal insert (you are at the Leaf)
  2. Come back up the tree and recompute Labels
     1.  They increase by at most 1
  3. For the first Node to break the condition, we perform ROTATION
  4. Finish (No more Rotations are needed. Will see why)

 

The First Node to Break the Condition

 

다음과 같은 경우를 생각해보자.

 

Case LL

 

 

다음과 같이 x라는 노드가 Insert 되어서 최초로 Tree의 구조가 깨지게 되어버린 case이다. 이런경우에는 어떻게 바뀌어야할까? 아래 그림과 같이 바뀌면된다.

 

 

B를 가장위로 올리고 A 노드의 왼쪽에 E를 붙인다.

 

 

Case LR

 

 

E를 올리고 E의 오론쪽에 A를 붙인다. A의 왼쪽에 G를 연결하고 B의 오른쪽에 F를 붙인다.

 

 

 

다음 포스팅에서는 이걸 가지고 하나의 예제를 돌려보는 내용을 다루어 보겠다.

출처: https://rino92.tistory.com/20?category=770131 [리노92의 블랙박스:티스토리]