AVL 트리
#DataStructure #DataStructure-Tree #DataStructure-Binary_Tree #DataStructure-BST #DataStructure-AVL_Tree
이진 트리(Binary Tree) 일부 복붙
1. AVL(Adelson-Velsky and Landis) Tree
AVL이 어떤 기능적인 의미를 담고있는것은 아니다. 개발한 사람의 이름이다.
AVL은 균형이 깨지는 것을 민감하게 탐지할 수 있다. 어떤 것을 가지고? BF(Balance Factor)를 가지고!
BF 계산식: 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이
균형 이진 트리라면-1, 0, 1의 값만 나와야 한다. 만약 이 이외의 값이 나왔다면 균형이 깨졌다는 의미이고, 이것은 Self-Balancing을 하게 만든다.
이 BF 때문에 삽입, 삭제가 일어날 때마다 밸런싱을 하게 되어 항상 균형을 유지한다. 때문에 삽입 삭제를 할 때마다 밸런싱이 일어나긴 해도 탐색을 할 때 활용도가 높기 때문에, 삽입과 삭제가 적고 탐색이 많은 데이터를 저장하는 자료구조로 용이하다.
+ AVL 트리는 이진 탐색 트리 + 균형 이진 트리의 성격을 합해 놓은 것이다.
2. Self-Balancing
AVL 트리는 BF의 절댓값이 2 이상이 되면 리밸런싱 작업을 한다.
리밸런싱 부분이 정해지면, 회전 방향과 회전 대상을 정한다. 회전은 좌 또는 우로 진행된다. (= 회전이란 노드가 특정 방향으로 꺾이는 것)
2-1. 리밸런싱 부분 정하기
리밸런싱 되는 경우는 BF의 절댓값이 2 이상 되는 그 부분이다. 더 정확히 말하면, 삽입 또는 삭제가 일어나기 전의 AVL 트리는 항상 균형 상태이기 때문에 삽입 또는 삭제가 일어난다고 해도 BF의 절댓값은 2 이상일 수 없다. 따라서 절댓값이 2가 되는 부분이 리밸런싱 되는 부분이다.
리밸런싱 될 부분의 상황은 4가지이다. 회전 관여 대상에 포함되는 노드는 3개이고, 이 노드가 어떻게 정렬되어 있냐에 따라 달라진다. AVL 트리, 왕초보개발자, nooblette 에 그림으로 잘 설명되어 있다. (어떤 포스트에서는 이 상황들을 LL, RR, LR, RL Rotation이라고 명명해서 __쪽으로 돌리고 다시 __쪽으로 돌리는 operation으로 이해해버릴 우려가 있다. LL, RR, LR, RL은 operation이 아니라 situation case 임을 주의하자.)
- LL(Left, Left): 중간 노드를 기준으로 위쪽 노드의 왼쪽 자손으로 중간 노드가 있고, 중간노드의 왼쪽 자손으로 아래 노드가 있는 경우이다. 왼쪽으로 편향된 경우라고 생각하면 된다.
- RR(Right, Right): 중간 노드를 기준으로 위쪽 노드의 오른쪽 자손으로 중간 노드가 있고, 중간노드의 오른쪽 자손으로 아래 노드가 있는 경우이다. 오른쪽으로 편향된 경우라고 생각하면 된다.
- LR(Left, Right): 중간 노드를 기준으로 위쪽 노드의 왼쪽 자손으로 중간 노드가 있고, 중간 노드의 오른쪽 자손으로 아래 노드가 있는 경우이다. < 이런 모양으로 되어 있는 경우이다.
- RL(Right, Left): 중간 노드를 기준으로 위쪽 노드의 오른쪽 자손으로 중간 노드가 있고, 중간 노드의 왼쪽 자손으로 아래쪽 노드가 있는 경우이다. > 이런 모양으로 되어 있는 경우이다.
2-2. 회전 방향과 회전 대상 정하기
리밸런싱 될 부분의 상황 4가지에 따라 회전 방향과 대상이 결정된다.
- LL의 상황일 때
- 위쪽 노드를 Right Rotation 한다.
- (= 위쪽 노드가 오른쪽으로 꺾인다.)
- (= 위쪽 노드가 중간 노드의 오른쪽 자식 노드가 된다.)
- 중간 노드의 원래 오른쪽 자식 노드를 위쪽 노드의 왼쪽 자식 노드로 만든다.
- -> 위의 두 과정을 모두 1.이라고 표현한 이유는 swap 이기 때문이다. 이 과정을 하고나면 중간노드가 이 노드들의 새로운 루트 노드가 된다.
- 위쪽 노드를 Right Rotation 한다.
- RR의 상황일 때
- 위쪽 노드를 Left Rotation 한다.
- (= 위쪽 노드가 왼쪽으로 꺾인다.)
- (= 위쪽 노드가 중간 노드의 왼쪽 자식 노드가 된다.)
- 중간 노드의 원래 왼쪽 자식 노드를 위쪽 노드의 오른쪽 자식 노드로 만든다.
- -> 위 과정을 하고나면 중간 노드가 이 노드들의 새로운 루트 노드가 된다.
- 위쪽 노드를 Left Rotation 한다.
- LR의 상황일 때
- LL의 상황으로 만든 후 LL일 때의 작업을 한다.
- 중간 노드를 Left Rotation 한다.
- (= 중간 노드가 왼쪽으로 꺾인다.)
- (= 중간 노드가 아래쪽 노드의 왼쪽 자식 노드가 된다.)
- 아래쪽 노드의 원래 왼쪽 자식 노드를 중간 노드의 오른쪽 자식 노드로 만든다.
- -> 왼쪽으로 편향된 위쪽-아래쪽-중간 노드의 형태가 된다.
- 위쪽 노드를 Right Rotation 한다.
- (= 위쪽 노드가 오른쪽으로 꺾인다.)
- (= 위쪽 노드가 새로운 중간 노드의 오른쪽 자식 노드가 된다.)
- 새로운 중간 노드의 원래 오른쪽 자식 노드를 위쪽 노드의 왼쪽 자식 노드로 만든다.
- RL의 상황일 때
- RR일때의 상황으로 만든 후 RR일 때의 작업을 한다.
- 중간 노드를 Right Rotation 한다.
- (= 중간 노드가 오른쪽으로 꺾인다.)
- (= 중간 노드가 아래쪽 노드의 오른쪽 자식 노드가 된다.)
- 아래쪽 노드의 원래 오른쪽 자식 노드를 중간 노드의 왼쪽 자식 노드로 만든다.
- -> 오른쪽으로 편향된 위쪽-아래쪽-중간 노드의 형태가 된다.
- 위쪽 노드를 Left Rotation 한다.
- (= 위쪽 노드가 왼쪽으로 꺾인다.)
- (= 위쪽 노드가 새로운 중간 노드의 왼쪽 자식 노드가 된다.)
- 새로운 중간 노드의 원래 왼쪽 자식 노드를 위쪽 노드의 오른쪽 자식 노드로 만든다.
3. 구현
데이터의 추가와 삭제는 BST의 방식(이진 탐색 트리(Binary Search Tree, BST) 참고)과 동일하다. 다만, 추가 및 삭제 후 BF가 |1| 이하인 경우가 있는지 확인하고 밸런싱 하는 작업을 추가해주면 된다. BST 포스트에서는 insert와 delete를 재귀를 사용하지 않고 구현했는데, 이렇게되면 BF 이상 지점을 잡아내야 한다. (BF가 2이거나 -2이거나.) 그런데 루트 노드부터 탐색해서 들어가면 BF가 딱 2인 지점을 찾기가 다소 복잡해진다.
BST 삽입과 삭제를 재귀를 사용해서 구현하면 리밸런싱 하기가 용이해진다. height를 새로 계산하면서 BF를 같이 확인할 수 있기 때문이다.
여러 포스트들을 봐도 완벽하게 구현된 것이 없었다. sudocode 정도로 작성해놓은 것으로 보이는데 로직을 분석하다보면 엣지케이스에서 돌아가지 않거나 height 계산, insert 이후 리밸런싱 처리 등이 정상적이지 않았다. 머리에서 트리를 계속 회전시키고, 장고의 디버깅과 수정 끝에 다소 지저분할 수는 있지만 의도를 제대로 반영한 코드를 구현했다. (data class에 메서드로 넣어야 더 적절한 메소드들도 있고, !!나 var 등의 지저분함은 넘어가주시라.)
3-1. Node
data class Node(
var height: Int = 0, // 자신을 루트노드로 가정할 때의 높이
var left: Node? = null,
var right: Node? = null,
val key: Int
)
3-2. Rotation 로직
class AVLTree {
//...
fun rightRotate(node: Node): Node {
val firstNode = node
val secondNode = node.left
val rightSubNodeOfSecondNode = secondNode!!.right
secondNode.right = firstNode
firstNode.left = rightSubNodeOfSecondNode
firstNode.height = calcHeight(firstNode)
secondNode.height = calcHeight(secondNode)
return secondNode
}
fun leftRotate(node: Node): Node {
val firstNode = node
val secondNode = node.right
val leftSubNodeOfSecondNode = secondNode!!.left
secondNode.left = firstNode
firstNode.right = leftSubNodeOfSecondNode
firstNode.height = calcHeight(firstNode)
secondNode.height = calcHeight(secondNode)
return secondNode
}
//...
}
3-3. 리밸런싱 로직
class AVLTree {
//...
fun rebalance(node: Node): Node {
val bf = getBF(node) //BF 계산
var returnNode = node
when {
bf > 1 -> { // 왼쪽 서브 노드의 높이로 인해 불균형 발생
if ((node.left?.left?.height?.plus(1) ?: 0) > (node.left?.right?.height?.plus(1) ?: 0)) { // LL
returnNode = rightRotate(node)
} else { // LR
node.left = node.left?.let { leftRotate(it) }
returnNode = rightRotate(node)
}
}
bf < -1 -> { // 오른쪽 서브 노드의 높이로 인해 불균형 발생
if ((node.right?.right?.height?.plus(1) ?: 0) > (node.right?.left?.height?.plus(1) ?: 0)) { // RR
returnNode = leftRotate(node)
} else { // RL
node.right = node.right?.let {
rightRotate(it)
}
returnNode = leftRotate(node)
}
}
else -> node
}
return returnNode
}
//한 노드의 BF: 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이
fun getBF(node: Node): Int {
val leftChildHeight = node.left?.height?.plus(1) ?: 0
val rightChildHeight = node.right?.height?.plus(1) ?: 0
return leftChildHeight-rightChildHeight
}
//...
}
3-2. 삽입 로직
class AVLTree {
//...
fun insert(key: Int, node: Node?): Node? {
if (root == null) { // 루트 노드조차 생성되어 있지 않으면 생성
root = Node(key = key)
return root
}
if (node == null) return Node(key = key) // 해당 노드 자리에 아무 노드도 없으면 여기에 노드 생성해서 삽입(하도록 리턴)
when {
node.key > key -> node.left = insert(key, node.left)
node.key < key -> node.right = insert(key, node.right)
else -> throw IllegalArgumentException() // AVL 노드는 노드의 값이 유니크해야함
}
node.height = calcHeight(node) // 삽입 후 높이 재측정
val returnNode = rebalance(node) // 리밸런싱 진행 (필요 시)
// node가 루트였는데 리밸런싱이 진행되었으면 root가 가리키고 있는 것이 더이상 루트가 아닐 수 있음
if (findParentNode(node.key) == null) {
root = returnNode
}
return returnNode
}
fun calcHeight(node: Node): Int {
return Math.max(node.left?.height?.plus(1) ?: 0, node.right?.height?.plus(1) ?: 0)
}
//...
}
3-5. 삭제 로직
class AVLTree {
//...
fun delete(key: Int, node: Node?): Node? {
if (node == null) return null
var replacedNode = node
when {
node.key > key -> node.left = delete(key, node.left)
node.key < key -> node.right = delete(key, node.right)
else -> {
when {
node.left != null -> { // 삭제할 노드의 왼쪽 서브노드 존재
val leftNode = node.left!!
val maxNode = findMaxKeyNode(leftNode) // 왼쪽 서브노드의 가장 오른쪽 노드는 서브노드 중 가장 큰 값을 가짐
val maxNodeParentNode = findParentNode(maxNode.key)!! // maxNode의 parentNode는 나중에 maxNode와의 관계를 끊어야 함
maxNode.right = node.right // node 오른쪽 서브노드가 있다면 node를 대체할 maxNode의 오른쪽에 해당 서브노드를 연결
connectToParentNodeOfNode(maxNode, node) // 삭제할 노드의 부모 노드의 새로운 자식 노드로 maxNode를 연결
// node의 왼쪽 노드는 maxNode보다 항상 작기 때문에 maxNode의 왼쪽에 위치
// 그러나 node의 왼쪽 서브노드가 maxNode 하나뿐이였다면 사이클을 만들지 말아야 함
if (maxNode != leftNode) {
maxNode.left = leftNode
disconnectFromParent(maxNode, maxNodeParentNode)
}
// node를 대체하여 반환될 새로운 노드
replacedNode = maxNode
}
node.right != null -> { // 삭제할 노드의 오른쪽 서브노드 존재
val rightNode = node.right!!
val minNode = findMinKeyNode(rightNode) // 오른쪽 서브노드의 가장 왼쪽 노드는 서브노드 중 가장 작은 값을 가짐
val minNodeParentNode = findParentNode(minNode.key)!! // minNode의 parentNode는 나중에 minNode와의 관계를 끊어야 함
minNode.left = node.left // node 왼쪽 서브노드가 있다면 node를 대체할 minNode의 왼쪽에 해당 서브노드를 연결
connectToParentNodeOfNode(minNode, node) // 삭제할 노드의 부모 노드의 새로운 자식 노드로 minNode를 연결
// node의 오른쪽 노드는 minNode보다 항상 크기 때문에 maxNode의 오른쪽에 위치
// 그러나 node의 오른쪽 서브노드가 minNode 하나뿐이였다면 사이클을 만들지 말아야 함
if(minNode != rightNode) {
minNode.right = rightNode
disconnectFromParent(minNode, minNodeParentNode)
}
// node를 대체하여 반환될 새로운 노드
replacedNode = minNode
}
else -> { // 삭제할 노드가 리프노드인 경우
return null
}
}
}
}
replacedNode.height = calcHeight(replacedNode) // 삭제 후 높이 재측정
val returnNode = rebalance(replacedNode) // 리밸런싱 진행 (필요 시)
// returnNode가 새로운 루트노드가 되었을 수 있음
if (findParentNode(returnNode.key) == null) {
root = returnNode
}
return returnNode
}
fun connectToParentNodeOfNode(node: Node, targetNode: Node) {
val parentNode = findParentNode(targetNode.key)
if ((parentNode?.left?.key ?: -1) == targetNode.key) {
parentNode?.left = node
} else if ((parentNode?.right?.key ?: -1) == targetNode.key) {
parentNode?.right = node
}
}
fun disconnectFromParent(targetNode: Node, targetParentNode: Node) {
when(targetNode.key) {
targetParentNode.left?.key -> {
targetParentNode.left = null
}
else -> {
targetParentNode.right = null
}
}
}
fun findMaxKeyNode(node: Node): Node {
return node.right?.let {
findMaxKeyNode(it)
} ?: run {
node
}
}
fun findMinKeyNode(node: Node): Node {
return node.left?.let {
findMinKeyNode(it)
} ?: run {
node
}
}
fun findParentNode(key: Int): Node? {
var currentNode = root
while(true) {
if (currentNode == null) return null
if (currentNode.key > key) {
when (currentNode.left?.key) {
null -> return null
key -> return currentNode
else -> currentNode = currentNode.left
}
} else if (currentNode.key < key) {
when (currentNode.right?.key) {
null -> return null
key -> return currentNode
else -> currentNode = currentNode.right
}
} else {
return null
}
}
}
//...
}
3-6. 검증
class AVLTree {
//...
fun bfs(node: Node?) {
if (node == null) return
val queue: Queue<Pair<Node, Int>> = LinkedList()
queue.offer(node to 0)
var currentLevel = node.height
while(queue.isNotEmpty()) {
val pair = queue.poll()
if (pair.second != currentLevel) {
currentLevel = pair.second
println("")
}
print("${pair.first.key}(${pair.first.height}) ")
pair.first.left?.let {
queue.offer(it to currentLevel+1)
}
pair.first.right?.let {
queue.offer(it to currentLevel+1)
}
}
}
//...
}
fun main(args: Array<String>) {
val avlTree = AVLTree()
avlTree.insert(3, avlTree.root)
avlTree.insert(2, avlTree.root)
avlTree.insert(1, avlTree.root)
avlTree.insert(7, avlTree.root)
avlTree.insert(6, avlTree.root)
avlTree.bfs(avlTree.root)
println("\n-----------------")
avlTree.insert(5, avlTree.root)
avlTree.bfs(avlTree.root)
println("\n-----------------")
avlTree.insert(4, avlTree.root)
avlTree.bfs(avlTree.root)
println("\n-----------------")
avlTree.delete(7, avlTree.root)
avlTree.bfs(avlTree.root)
println("\n-----------------")
avlTree.delete(5, avlTree.root)
avlTree.bfs(avlTree.root)
println("\n-----------------")
avlTree.delete(4, avlTree.root)
avlTree.bfs(avlTree.root)
println("\n-----------------")
avlTree.delete(6, avlTree.root)
avlTree.bfs(avlTree.root)
println("\n-----------------")
}
/*
2(2)
1(0) 6(1)
3(0) 7(0)
-----------------
3(2)
2(1) 6(1)
1(0) 5(0) 7(0)
-----------------
3(3)
2(1) 6(2)
1(0) 5(1) 7(0)
4(0)
-----------------
3(2)
2(1) 5(1)
1(0) 4(0) 6(0)
-----------------
3(2)
2(1) 4(1)
1(0) 6(0)
-----------------
3(2)
2(1) 6(0)
1(0)
-----------------
2(1)
1(0) 3(0)
-----------------
*/
3-7. 전체 코드
4. GPT의 AVLTree
내가 고민했던 부분들을 깔끔하게 정리해서 처리한 부분이 엿보였다. insert와 insertRecursive를 분리해서 root 처리를 한 부분이 그렇고, 노드 삭제 시 왼쪽 혹은 오른쪽 서브트리만 존재 할 때의 처리가 깔끔하다. 그리고 리밸런싱에서도 LR -> LL로 만들고 그것을 LL 처리와 같이 연결시키는 부분에서(RL도 마찬가지) 로직을 간결하게 만들 수 있는 점 또한 엿보였다.