AVL 트리

• AVL 트리

AVL 트리는 Adelson - Velskii와 Landis에 의해 제안된 트리로 각 노드에서 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차리가 1 이하인 이진 탐색 트리를 말한다. 이 트리는 트리가 비균형 상태로 되면 스스로 노드들을 재배치하여 균형 상태로 만든다. AVL 틀는 항상 균형 트리를 보장하기 때문에 의 탐색 시간을 보장한다. 삽입과 삭제 연산도 시간 안에 할 수 있다.

AVL 트리도 탐색에서는 일반 이진 탐색 트리의 탐색 연산과 동일하다. 따라서 시간 복잡도는 이다. AVL 트리에서 균형이 깨질 수 있는 연산은 삽입과 삭제 연산이다.

• AVL 트리의 삽입 연산

이진 탐색 트리에서 노드가 삽입되면 삽입되는 위치에서 루트까지의 경로에 있는 모든 조상 노드들의 균형 인수가 영향을 받는다. 따라서 불균형 상태(균형 인수가 2) 로 변한 가장  가까운 조상 노드의 서브트리들에 대하여 다시 균형을 잡아야 한다. 그 외의 다른 노드들은 변경할 필요가 없다.

AVL 트리에서 균형이 깨지는 경우는 다음의 4가지의 타입이 있다. 새로 삽입된 노드 N로 부터 가장 가가우면서 균형 인수가 가 된 조상 도드를 A라고 하자.

• LL 타입 : N이 A의 왼쪽 서브트리의 왼쪽 서브트리에 삽입된다.
• LR 타입 : N이 A의 왼쪽 서브트리의 오른쪽 서브트리에 삽입된다.
• RR 타입 : N이 오른쪽 서브트리의 오른쪽 서브트리에 삽입된다.
• RL 타입 : N이 오른쪽 서브트리의 왼쪽 서브트리에 삽입된다.

LL 과 RR 은 대칭이고 역시 LR 과 RL 도 대칭이다. 이제 트리를 다시 균형시키자. 다음은 각각의 경우에 대하여 균형 트리로 다시 만드는 방법이다.

• LL 회전 : A부터 N까지의 경로상의 노드들을 오른쪽으로 회전시킨다.
• LR 회전 : A부터 N까지의 경로상의 노드들을 왼쪽-오른쪽으로 회전 시킨다.
• RR 회전 : A부터 N까지의 경로상의 노드들을 왼쪽으로 회전시킨다.
• RL 회전 : A부터 N까지의 경로상의 노드들을 오른쪽-왼쪽으로 회전시킨다.

한번만 회전시키는 것을 단순 회전(single rotation)이라고 하는데 LL 회전, RR 회전이 여기에 속한다. 이 경우, 탐색 순서를 유지하면서 부모와 자식의 위치를 교환하면 된다. 두 번의 회전이 필요한 것을 이중 회전(double rotation)이라고 하며 LR 회전, RL 회전이 여기에 속한다. 마찬가지로 LL 회전과 RR 회전은 방향만 반대이고 대칭이며 LR 회전과 RL 회전도 마찬가지이다. 

단순 회전인 LL 회전과 RR 회전을 알고리즘으로 만들어 보면 아래와 같다.

| AVL 트리에서의 단순 회전 알고리즘

---

rotate_LL(A)

B = A의 왼쪽 자식

B의 오른쪽 자식을 A의 왼쪽 자식으로 만든다.

A를 B의 오른쪽 자식 노드로 만든다.

rotate_RR(A)

B = A의 오른쪽 자식

B의 왼쪽 자식을 A의 오른쪽 자식으로 만든다.

A를 B의 왼쪽 자식 노드로 만든다.

---

| AVL 트리에서의 이중 회전 알고리즘

---

rotate_RL(A)

B = A의 오른쪽 자식

rotate_LL(B)가 반환하는 노드를 A의 오른쪽 자식으로 만든다.

rotate_RR(A)

rotate_LR(A)

B = A의 오른쪽 자식

rotate_RR(B)가 반환하는 노드를 A의 오른쪽 자식으로 만든다.

rotate_LL(A)

---

---

#pragma once

#ifndef ___AVLTree

#define ___AVLTree

// AVLTree.h : AVL 트리 클래스 CAVLTree

#include "BinSrchTree.h"

class AVLTree : public BinSrchTree {

public:

// 노드의 균형인수를 반환

int getHeightDiff(BinaryNode* node) {

if (node == NULL) return 0;

int hLeft = getHeight(node->getLeft());

int hRight = getHeight(node->getRight());

return hLeft - hRight;

}

// LL 회전 함수

BinaryNode* rotateLL(BinaryNode* parent) {

BinaryNode* child = parent->getLeft();

parent->setLeft(child->getRight());

child->setRight(parent);

return child;

}

// RR 회전 함수

BinaryNode* rotateRR(BinaryNode* parent) {

BinaryNode* child = parent->getRight();

parent->setRight(child->getLeft());

child->setLeft(parent);

return child;

}

// RL 회전 함수

BinaryNode* rotateRL(BinaryNode* parent) {

BinaryNode* child = parent->getRight();

parent->setRight(rotateLL(child));

return rotateRR(parent);

}

// LR 회전 함수

BinaryNode* rotateLR(BinaryNode* parent) {

BinaryNode* child = parent->getLeft();

parent->setLeft(rotateRR(child));

return rotateLL(parent);

}

// 트리를 균형트리로 만든다

BinaryNode* reBalance(BinaryNode* parent) {

int hDiff = getHeightDiff(parent);

if (hDiff > 1) {

if (getHeightDiff(parent->getLeft()) > 0)

parent = rotateLL(parent);

else parent = rotateLR(parent);

}

else if (hDiff < -1) {

if (getHeightDiff(parent->getRight()) < 0)

parent = rotateRR(parent);

else parent = rotateRL(parent);

}

return parent;

}

//AVL 트리의 삽입 연산

void insert(int data) {

if (isEmpty()) root = new BinaryNode(data);

else root = insertAVL(root, data);

}

BinaryNode* insertAVL(BinaryNode* parent, int data) {

if (data < parent->getData()) {

if (parent->getLeft() != NULL)

parent->setLeft(insertAVL(parent->getLeft(), data));

else

parent->setLeft(new BinaryNode(data));

return reBalance(parent);

}

else if (data > parent->getData()) {

if (parent->getRight() != NULL)

parent->setRight(insertAVL(parent->getRight(), data));

else

parent->setRight(new BinaryNode(data));

return reBalance(parent);

}

else {

printf("중복된 키 에러\n");

return NULL;

}

}

};

#endif // !___AVLTree