[알고리즘] AVL Tree(트리) : 필수기본정리 - Balanced Factor, 4가지 Rotation(회전), 삽입, 제거, Kotlin구현

목차

AVL 트리 개념

우선 AVL 트리는 이진 탐색 트리를 기초로 합니다. 이진 탐색 트리에 대하여 자세히 알고 싶으시다면 아래 링크를 확인해주세요

[알고리즘] Binary Search Tree 이진탐색 트리 : 기본정리 - 탐색,삽입,삭제, 검색연산, 삭제연산 - Kotlin

위 포스트를 보셨다면 이진 탐색트리의 단점은 불균형한 트리 모형을 하고 있을 때 트리의 성능이 O(log n)에서 O(n)으로 떨어진다는 것을 알 수 있었습니다. 

불균형/균형 이진 탐색트리에 5까지 도달하는 과정

AVL트리는 이러한 문제를 해결하기위해 만들어졌습니다. 이진트리이면서, 균형을 유지하기 때문에 이진 검색 시 효율성을 보장하게 됩니다. 

 

 

Balanced Tree (균형트리)

항상 균형트리의 모양을 하고 있는 게 AVL 트리의 특징입니다. 

 

우선 균형트리에는 3가지 상태가 있습니다. 

1. 완전균형상태(Perfect Balance)

2. 충분한균형상태(Good Enough Balance)

3. 불균형상태(Unbalance)

 

 

완전 균형 상태(Perfect Balance)

완전 균형 상태는 모든 레벨에서 노드가 가득 차있는 상태입니다. 

 

 

충분한 균형 상태(Good Enough Balance)

 

가장 아래쪽 레벨을 제외하고 모든 노드가 채워져 있는 상태에 트리일 때입니다. 

 

 

 

불균형 상태(Unbalance)

나머지 트리 모양은 불균형한 상태의 트리라 정의하고 이 트리들은 성능 저하의 원인입니다. 이 문제를 해결하기 위해 AVL Tree를 사용하게 됩니다. AVL Tree는 자동으로 균형 잡힌 트리를 제공하기 때문에, 탐색, 삽입, 삭제 오퍼레이션들은 O(log n)으로 진행할 수 있게 합니다. 

 

BalanceFactor를 이용한 균형/ 불균형 트리 구분

먼저 AVL트리를 만들기 전에 현재 생성되고 있는 트리가 균형인지 불균형인지 파악해야 합니다. 균형인지 파악하기 위해  트리의 Height을 알아야 합니다. Height은 현재 노드로부터 단말 노드까지의 거리를 Height이라고 합니다. 아래 다이어그램은 각 노드에 Height을 표기하였습니다. 트리 용어와 익숙하시지 않으시다면 아래 링크를 확인해주세요.

[알고리즘] Tree 트리 : 기본정리 - 트리 구성, 깊이우선순회(Depth-First Traversal), 레벨순회(LevelOrderTra

 

파란 글씨는 Tree에 Height을 나타냅니다. 트리의 Height을 이용해서 균형 상태를 판별하게 됩니다. Height을 통해 균형을 판별하는 BalanceFactor라는 코드를 작성해보겠습니다. 

 

Balance Factor

var height = 0

val leftHeight: Int
	get() = leftChild?.height?: -1 //leftchild가 없다면 -1을 반환
    
val rightHeight: Int
	get() = rightChild?.height? : -1 //rightChild가 없다면 -1을 반환

val balaneFactor: Int
	get() = leftHeight - rightHeight

BalanceFactor는 왼쪽, 오른쪽 자식의 height을 비교하여, 균형 트리인지 불균형 트리인지 구분하게 됩니다. balanceFactor를 이용해서 어떻게 구분할 수 있을까요? 노드의 Balance Factor에 절댓값이 1 이하이면 balance라고 정의할 수 있습니다. 

위 다이어그램은 균형 트리입니다. 초록 글씨는 BalancFactor를 나타내고 파란 글씨는 현재 노드의 Height을 의미합니다.

25의 balancefactor가 -1인 이유는 무엇일까요? 빈 노드는 -1로 카운트합니다. 그래서 비어있는 왼쪽 자식 노드(-1) height이 0 인 자식 노드 두 개를 이용해 25의 Balance Factor을 구하면 -1이 나오게 됩니다. 

위 다이어그램은 불균형 트리입니다. 보다시피 height을 나타내는 초록색 글씨 중 -2가 있기 때문입니다. -2의 절댓값은 2이므로 1을 초과합니다. 그러므로 불균형 트리임을 확인할 수 있습니다. 

 

 

Rotation(회전)

이제 우리는 어떤 게 불균형한 지 구별 가능해졌기 때문에 이 불균형 트리들을 AVL트리를 만들기 위해 균형 트리로 바꿔줘야 합니다. 이때 우리는 rotation을 활용하여 균형트리로 바꿔줘야합니다.

 

rotation에는 4가지 종류가 있습니다. 

1. left left

2. right right

3. left-right 

4. right-left 

 

LL Rotation

left- left를 쓰는 때는 불균형하면서 leftheavy일 때 left-left회전을 쓰게 됩니다. left-left 회전의 원리는 아래와 같습니다.

balanceFactor가 -2이기 때문에 AVL 트리 조건에 위배되게 됩니다. 따라서 오른쪽 방향으로 회전을 통해 모든 균형 값을 0으로 만들 수 있습니다. 이렇게 leftHeavy인 경우에는 오른쪽으로 1 회전해주면 됩니다. 회전을 하는 법은 가운데 노드를 부모 노드로 만들고 나머지 두 노드를 자식 노드로 만들면 됩니다. 

 

코드로 구현하면 아래와 같습니다. 

 

오른쪽 회전 코드 구현

private fun rightRotate(node: AVLNode<T>):AVLNode<T>{
	//1 
    val pivot = node.leftChild!!
    //2
    node.leftChild = pivot.rightChild
    //3
    pivot.rightChild = node
    //4
    node.height = max(node.leftHeight, node.rightHeight) + 1
    pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1
    
    //5
    return pivot
}

코드를 설명해보겠습니다. 

1. pivot이라는 value를 만들어줬는데 중심점을 뜻합니다. node에 왼쪽 자식을 pivot으로 만듭니다. 즉 위 다이어그램에서 0002를 pivot으로 지정하게 됩니다. 

2. 노드에 leftChild위치에 pivot에 rightChild를 넣습니다. 다이어그램에서 0001을 node의 rightChild위치에 놓습니다.  

3. 현재 pivot은 부모 node위치에 있습니다. 이 pivot노드에 right위치에 node위치에 있는 0003을 배치하면 됩니다.

4. 이제 높이를 업데이트해줌으로써, balancefactor가 0이 되도록 합니다. 

5. 마지막으로 회전된 트리를 반환합니다. 

 

 

RR Rotation

right-right을 사용할 때는 right heavy인 트리일 때 사용하면 됩니다. 

위에서 설명했던 left-left와 방향만 다르고 방식은 같습니다. Right-heavy일 때는 왼쪽으로 1회 회전하면 됩니다. 

 

왼쪽 회전 코드 구현

private fun leftRotate(node: AVLNode<T>): AVLNode<T> {
	val pivot = node.rightChild!!
    node.rightChild = pivot.leftChild
    pivot.leftChild = node
    node.height = max(node.leftHeight, node.rightHeight) + 1
    pivot.hegith = max(pivot.leftHeight, pivot.rightHeight) + 1
    return pivot
}

 

LR 회전

left-right회전은 위에서 했던 회전과 조금 다릅니다. 회전을 두 번 해줘야 합니다. 아래 다이어그램을 확인해보겠습니다. 

먼저 10 node아래에 10보다 더 큰 15 노드가 삽입되었습니다. 그리고 불균형한 트리가 되어버렸습니다. 균형 트리로 만들어주기위해 가장 먼저해야할것은, left 회전을 통해 right rotate을 할수있도록 정렬하는것입니다. 그리고 right roate을 하면 균형트리로 변환할 수 있습니다. 

 

코드로 좀 더 자세히 살펴보겠습니다. 

private fun leftRightRotate(node: AVLNode<T>): AVLNode<T> {
    //1
    val leftChild = node.leftChild ?: return node
    //2
    node.leftChild = leftRotate(leftChild)
    //3
    return rightRotate(node)
}

1. 먼저 leftChild라는 변수를 node에 leftChild로 지정합니다. leftChild는 15입니다. 

2. node.leftChild를 left을 하게 됩니다. leftRotate함수에 파라미터로 위에서 leftchild변수로 지정했던 15가 들어갑니다. 그러면 10과 15의 자리가 바뀌게 됩니다.  

3. 마지막으로 rightRotate을 하면 15가 부모 노드가 되고 나머지 2개의 노드 10과 25가 자식 노드가 됩니다. 

 

RL 회전

 

right left회전은 left-right과 방식은 같고 돌리는 방향 순서를 반대로 해주면 됩니다. 

바로 코드로 확인해보겠습니다. 

private fun rightLeftRotate(node: AVLNode<T>):AVLNode<T> {
	val rightChild = node.rightChild?: return node
    node.rightChild = rightRotate(rightChild)
    return leftRotate(node)
}

leftRight에 정반대로 해주시면 됩니다. 

 

이제 균형인지 불균형인지 구별하는 법과, left heavy일 때 right heavy일때 쓸 rotation까지 구현할 수 있게 되었습니다. 

이제 이 함수들을 종합하여, 각기 다른 불균형 트리를 적절한 함수를 사용해 균형 트리를 자동으로 만들어주는 balanced함수를 구현해주겠습니다. 

 

AVL 트리 구현

이제 AVL트리를 구현하기 위한 모든 준비가 되었습니다. 이제 위에서 만들었던 함수들을 종합하여 AVL Tree를 만들어보도록 하겠습니다. 

 

Balanced함수 구현

Balanced함수는 균형 트리로 바꿔주기 위해 어떤 Rotation함수를 써야 할지 결정해줍니다

 

Balanced함수 구현

private fun balanced(node: AVLNode<T>): AVLNode<T>{
	return when (node.balanceFactor) {
    	2-> {
        	//1 
        	if(node.leftChild?.balanceFactor ==-1) {
            	leftRightRotate(node)
            } else{
            //2
            	rightRotate(node)
            }
        }
        -2 -> {
        	//3
        	if(node.rightChild?.balanceFactor ==1) {
            	rightLeftRotate(node)
            } else {
            //4
            	leftRotate(node)
            }
        }
        else -> node
    }
}

1. node의 balance factor가 2이면 right회전

2. node의 balance factor가 2이면서 node.leftChild가 -1이면 leftright 회전

3. node의 balance factor가 -2이면 left회전

4. node의 balance factor가 -2이면서 node.rightChild가 1이면 rightleft 회전

 

Insert함수 구현

insert함수는 기존 이진 탐색 트리와 balanced함수가 들어가는 것을 제외하면 똑같습니다.

 

insert함수 구현

private fun insert(node:AVLNode<T>?. value: T):AVLNode<T>? {
	node?: return AVLNode(value)
    if(value < node.value) {
    	node.leftChild = insert(node.leftChild,value)
    } else{
    	node.rightChild = insert(node.rightChild, value)
    }
    val balancedNode = balanced(node)
    balancedNode?.height = max(balancedNode?.leftHeight?: 0, balancedNode?.rightHeight?: 0) +1
    return balancedNode
}

이렇게 AVL트리에 insert함수는 insert를 실행해줄 때마다, insert 된 후, balanced로 node들을 회전하여 재배열을 통해 균형 트리를 생성하는 것을 볼 수 있습니다. 

 

이제 insert함수를 활용하여 AVL Tree를 만들어보겠습니다. 

"repeated insertions in sequenece" example{
	val tree = AVLTree<Int>()
    
    (0..14).forEach{
    	tree.insert(it)
    }
    
    print(tree)
}

결과는 다음과 같습니다. 

---Example of repeated insertions in sequence---
  ┌──14
 ┌──13
 │ └──12
┌──11
│ │ ┌──10
│ └──9
│  └──8
7
│  ┌──6
│ ┌──5
│ │ └──4
└──3
│ ┌──2
└──1
 └──0

 

위 예제로는 insert를 이해하기 충분하지 않아서 아래 이미지를 추가합니다. 아래 이미지는 추가되는 과정을 다이어그램으로 설명한 것입니다. 트리에 node가 추가되는 방식은 이진 탐색 트리 포스트에서 설명하였습니다. 

Remove함수 구현

이진 탐색 트리에서 remove에서 balanced함수만 더해주고 balanced 됐을 때 바뀐 위치들의 node의 높이만 업데이트해주면 됩니다.  

val balancedNode = balanced(node)
balancedNode.height = max(
    balancedNode.leftHeight,
    balancedNode.rightHeight
) + 1    
return balancedNode

remove함수도 실행해보겠습니다. 

val tree = AVLree<Int>()
tree.insert(15)
tree.insert(10)
tree.insert(16)
tree.insert(18)
print(tree)
tree.remove(10)
print(tree)

코드를 실행하면 아래와 같이 나옵니다.

---Example of removing a value---
 ┌──18
┌──16
│ └──null
15
└──10
┌──18
16
└──15

이렇게 하면 AVL Tree를 위한 함수들이 모두 업데이트됩니다.