AVL Tree

3 minute read

AVL Tree

Balanced Tree 라고도 한다. Adelson-Velsky and Landis가 발명한 트리이다. 스스로 균형을 잡는 이진 탐색 트리이다.

사용 이유 : 이진 검색 트리의 연산은 세 가지가 있다. 검색, 삽입, 삭제. 한 노드의 위치를 찾아야 그 노드 자리에 삽입하거나 삭제할 수 있기 때문에 검색 연산이 핵심이다. AVL TREE 검색연산의 시간 복잡도는 $O\left(log n \right)$로 다른 자료구조에 비해 속도가 빠르다. 그렇기 때문에 balanced tree중 하나인 AVL TREE를 사용한다.
특징 : 모든 노드에 대해, 두 자식 서브트리의 높이는 항상 최대 1만큼 차이난다. -> 코드 구현의 핵심이다.
구현 설계 : 삽입과 삭제 연산은 재귀적으로 구현하기.

구현

class NODE()
- 각 노드는 key, left, right, height, bf를 갖는다. 이진 검색 트리와 다른점은 AVL TREE에 노드가 생성되어 삽일될 때, 해당 노드의 왼쪽, 오른쪽 자식 노드 또한 NIL 노드로 생성이 되도록 구현한다.
  - 이유는 높이 계산시 처음 0으로 초기화 되고 다음 높이 계산은 해당 노드의 $max\left(왼쪽 자식 노드의 높이 - 오른쪽 자식 노드의 높이 \right)$를 사용하기 때문이다. 오른쪽 자식 노드의 높이를 구하기 위해서는 해당 노드의 자식 노드들이 Node()로 새로운 노드로 할당되어야 height 속성을 가져올 수 있기 때문이다.
- height : 초기값 0. $1 + max\left(왼쪽 자식 노드의 높이 - 오른쪽 자식 노드의 높이 \right)$
- balanced factor : $|왼쪽 자식 노드의 높이 - 오른쪽 자식 노드의 높이|$
```
class Node:

    def __init__(self):
        self.key = None # 이진 검색 트리에서 해당 노드의 key값
        self.left = None
        self.right = None
        self.parent = None
        self.height = -1
        self.bf = 0

    def setKey(self,key):
        self.key = key

    def disconnect(self):
        self.key = None
        self.left = None
        self.right = None
        self.height = -1
        self.bf = 0
```
$Insert\left(T,z\right)$
- 필요한 함수 :
  - leftRotation(), rightRotation() : balanced factor의 절댓값이 1 이하가 아닐 때, AVLtree의 규칙을 지키기위해 사용된다.
  - rebalance() : balanced factor, height 계산을 위해 사용된다.
1. BST insert 연산과 동일하게 z를 삽입한다.
2. AVL tree 속성에 맞춰 rotation 한다. 2-1. z원소의 조상 노드 중 가장 가까운 노드의 높이차가 2 이상이면 rotation을 시행한다.

def Insert(self,x,z):
    if x is None or x.key is None:
        self.root = Node()
        self.root.setKey(z)
        self.root.left = Node()
        self.root.right = Node()
        self.heightUpdate(self.root)

    elif x.key > z:
        if x.left.key is None:
            x.left.setKey(z)
            x.left.left = Node()
            x.left.right = Node()
            x.left.parent = x
            self.rebalance(x.left)
        else:
            self.Insert(x.left,z)

    elif x.key < z:
        if x.right.key is None:
            x.right.setKey(z)
            x.right.left = Node()
            x.right.right = Node()
            x.right.parent = x
            self.rebalance(x.right)
        else:
            self.Insert(x.right,z)
    else:
        return "동일한 값을 삽입할 수 없습니다."

BSTREE와 달리 AVLTREE에서는 모든 노드의 자식 노드를 빈 노드로 만들어준다.

def rebalance(self,x):
    print("rebalance : ",x.bf)
    while x is not None:
        self.heightUpdate(x)
        self.balanceUpdate(x)
        if x.bf == 2:
            if x.left.bf > 0:
                self.rightRotation(x)
            else:
                self.leftRotation(x.left)
                self.rightRotation(x)

        elif x.bf == -2:
            if x.right.bf > 0:
                self.rightRotation(x.right)
                self.leftRotation(x)
            else:
                self.leftRotation(x)
        self.heightUpdate(x)    
        x = x.parent  

def heightUpdate(self,x):
    if x.key:
        print('height Update : ', x.key)
        x.height = 1 + max(x.right.height,x.left.height)

def balanceUpdate(self,x):
    if x.key:
        print('balance Update : ', x.key)
        x.bf = x.left.height - x.right.height

rotation
1. LL
2. LR
3. RR
4. RL LL, RR은 단순 회전, LR, RL은 이중 회전이다.

def leftRotation(self,x):
    print('leftrotation',x.key)
    y = x.right
    x.right = y.left
    if y.left is not None:
        y.left.parent = x
    y.parent = x.parent
    if x.parent is None:
        self.root = y
    elif x.key == x.parent.left.key:
        x.parent.left = y
    else:
        x.parent.right = y

    y.left = x
    x.parent = y

def rightRotation(self,x):
    print('rightrotation',x.key)
    y = x.left
    x.left = y.right
    if y.right is not None:
        y.right.parent = x
    y.parent = x.parent
    if x.parent is None:
        self.root = y
    elif x.key == x.parent.left.key:
        x.parent.left = y
    else:
        x.parent.right = y
    y.right = x
    x.parent = y

delete
1. BST delete 연산과 동일하게 원소를 삭제한다.
2. 삭제

def Delete(self,x,z):
    if x.key is None:
        if self.root is None: return print("<Empty Tree>")
        else: return print("삭제할 node가 없습니다.")
    else:
        if x.key == z:
            if not x.left.key and not x.right.key:
                print("자식 노드 없음")
                x.disconnect() # 빈 노드로 할당.
            elif x.left.key and not x.right.key:
                print("왼쪽 자식 노드만 있음")
                x.key = x.left.key
                x.left.disconnect()
            elif not x.left.key and x.right.key:
                print("오른쪽 자식 노드만 있음")
                x.key = x.right.key
                x.right.disconnect()
            else:
                print("자식 노드 둘 다 있음")
                y = self.TreeMinimum(x.right)
                x.key = y.key
                y.key.disconnect()
        elif x.key > z:
            return self.Delete(x.left,z)
        else:
            return self.Delete(x.right,z)
    print(x.key)
    self.rebalance(x)

Share on

Twitter Facebook LinkedIn

인공지능 대학원 준비생

AVL Tree

구현

Share on