[CLRS] [13-1] AVL Tree

1. Intro

- CLRS에서의 13챕터는 Red-Black Tree에 대해서 서술한다.

- 하지만, 나는 AVL Tree(13-1) -> Red-Black Tree(13-2) -> LLRB Tree(13-3) 순으로 포스팅하고자 한다.

- 이 순으로 이해해야 비교적 순조롭게 이해가 가능하다.

 

2. AVL Tree?

- AVL Tree는 스스로 균형을 잡는 BST이다. 즉, BBST의 한 종류라고 생각하면 된다.

- 한쪽으로 편향을 가진 이진트리가 되는 것을 방지해준다.

 

3. AVL Tree 특징

I) AVL Tree는 BST의 속성을 가진다.

II) left subtree와 right subtree의 높이 차이가 최대 1이다.

--> Balance Factor의 절댓값이 1이하이다.

--> Balance Factor : (left subtree의 높이) - (right subtree의 높이)

III) 어떤 시점에서 높이 차가 1보다 커지면 회전(rotation) or 재구성(restructure)을 통해 균형을 잡는다. 

--> 필자는 회전과 재구성은 같은 method라고 생각하고 서술하겠다.

 

4. Rotation | Restructure

- AVL Tree을 형성하면서 생기는 불균형의 케이스는 크게 4가지가 존재한다.

 

- 이러한 4가지 케이스를 다음과 같이 재구성(restructure)해준다.

- 여기서 C,B,A는 4가지 케이스에 따라 달라지지만 근본적으로 

C : min(C,B,A)

A : max(C,B,A)

B : middle(C,B,A) 라고 생각하면 된다. 

 

즉, 위의 4가지 케이스의 A,B,C와 아래의 A,B,C는 다르다고 생각하면 된다.

- 코드 구현을 통해 더욱 자세히 알아보자.

 

5. Code (삽입만)

class AVLNode:
    def __init__(self,key, height = 0, left = None,right = None):
        self.key = key
        self.height = height
        self.left = left
        self.right = right

class AVLTree:
    def __init__(self):
        self.root = None
    
    def _height(self,node):
        if node == None:
            return -1
        else: 
            return node.height
        
    def _balance_factor(self,node):
        return self._height(node.left) - self._height(node.right)
    
    def insert(self,key):
        self.root = self._insert(self.root, key)

    def _insert(self,node,key):
        if node == None:
            return node(key)
        if node.key < key:
            node.right = self._insert(node.right, key)
        if node.key > key:
            node.left = self._insert(node.left, key)
        
        node.height = max(self.height(node.left),self.height(node.right)) + 1

        if self._balance_factor(node) > 1:
            if self._balance_factor(node.left) > 0:
                node = self._LL(node)
            else:
                node = self._LR(node)
        
        if self._balance_factor(node) < -1 :
            if self._balance_factor(node.right) > 0 :
                node = self._RL(node)
            else:
                node = self._RR(node)
        
        return node

    def _LL(self,node):
        new = node.left
        node.left = new.right
        new.right = node
        node.height = max(self.height(node.left),self.height(node.right)) + 1
        new.height = max(self.height(new.left),self.height(new.right)) + 1
        return new
    
    def _RR(self, node):
        new = node.right
        node.right = new.left
        new.left = node
        node.height = max(self.height(node.left),self.height(node.right)) + 1
        new.height = max(self.height(new.left),self.height(new.right)) + 1
        return new
    
    def _LR(self,node):
        new = node.left.right
        node.left = new.right
        node.left.right = new.left
        new.left = node.left
        new.right = node
        new.left.height = max(self.height(new.left.left),self.height(new.left.right)) + 1
        new.right.height = max(self.height(new.right.left),self.height(new.right.right)) + 1
        new.height = max(self.height(new.left),self.height(new.right)) + 1
        return new
    
    def _RL(self,node):
        new = node.right.left
        node.right.leeft = new.right
        new.right = node.right
        node.right = new.left
        new.left = node
        new.left.height = max(self.height(new.left.left),self.height(new.left.right)) + 1
        new.right.height = max(self.height(new.right.left),self.height(new.right.right)) + 1
        new.height = max(self.height(new.left),self.height(new.right)) + 1
        return new