자료구조 :: 탐색(3) 균형 이진 탐색 트리 - AVL 트리

# 균형 이진 탐색 트리

이진 탐색 트리는 만약 트리가 균형 트리라면 탐색 연산은 O(log₂n)의 시간 복잡도를 가지고 있다.
일반 이진 트리는 이진 트리 상태를 유지하기는 하지만 균형 트리를 보장하지는 않는다. 만약 이진 탐색 트리가
균형 트리가 아닐 경우에는 트리가 경사 트리가 될 경우 시간 복잡도가 O(n)으로 높아지게 된다.
스스로 균형 트리를 만드는 트리의 종류로는 AVL트리 ,2-3트리, 2-3-4트리, 레드블랙트리 등이 있다.


# AVL 트리

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

AVL트리에서 균형인수는 매우 중요하다. 균형인수란 왼쪽서브트리의 높이 - 오른쪽 서브트리의 높이로 정의된다.
모든 노드의 균형인수가 ±1 이하이면 AVL 트리이다. 

삽입 연산

균형을 이룬 이진 탐색 트리에서 균형 상태가 깨지는 것은 삽입과 삭제 연산시이다. 삽입 연산시에는 삽입되는
위치에서 루트까지의 경로에 있는 조상 노드들의 균형 인수에 영향을 줄 수 있다. 따라서 새로운 노드의 삽입 후
불균형 상태로 변한 가장 가까운 조상 노드, 즉 균형인수가 ±2가 된 가장 가까운 조상 노드의 서브 트리들에 대해
다시 균형을 잡아야 한다. 그 외의 다른 노드들은 일체 변경할 필요가 없다.

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

(1) LL타입 : N이 A의 왼쪽 서브트리의 왼쪽에 삽입되는 경우(A노드의 왼쪽노드의 왼쪽에 삽입)
(2) LR타입 : N이 A의 왼쪽 서브트리의 오른쪽에 삽입되는 경우 (A노드의 왼쪽노드의 오른쪽에 삽입)
(3) RR타입 : N이 A의 오른쪽 서브트리의 오른쪽에 삽입되는 경우(A노드의 오른쪽노드의 오른쪽에 삽입)
(4) RL타입 : N이 A의 오른쪽 서브트리의 왼쪽에 삽입되는 경우(A노드의 오른쪽노드의 왼쪽에 삽입)

말이 조금 헷갈리지만 당연한 모든 경우의 수 이다. (왼쪽-왼쪽,왼쪽-오른쪽,오른쪽-오른쪽, 오른쪽-왼쪽)
LL과 RR은 대칭이고 LR과 RL도 대칭이다. 재균형시키는 방법도 각 경우에 따라 달라진다.

※ 불균형트리를 균형트리로 만드는 방법

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

한번만 회전하는 것을단순회전(single rotation)이라고 하며 두번 회전이 필요한것을 이중회전(double rotation)
이라고 한다. LL,RR은 단순회전, LR,RL은 이중 회전이며 회전은 탐색 순서를 유지하면서 부모와 자식 원소의
위치를 교환하면 된다.

그림 참조 : http://blog.naver.com/ryu_seonghan?Redirect=Log&logNo=110087291142


[AVL 트리 예제]

source code : AVL_tree.cpp

#include <stdio.h> 
#include <stdlib.h> 

#define max(a,b)    (((a) > (b)) ? (a) : (b)) 

typedefstruct AvlNode 
{ 
int data; // key 값
    AvlNode *left_child, *right_child; 
}AvlNode; 

AvlNode *root; 


// LL 회전 (오른쪽으로 회전한다)

// ±2를 가지는 A가 부모가 되고 A->left_child인 B가 child가 된다.
// A->left에 B가 가지고 있는 right_child를 대입하고 B의 right_child에 A을 대입한다.

AvlNode* rotate_LL(AvlNode *parent) 
{ 
    AvlNode *child = parent->left_child; 
    parent->left_child = child->right_child; 
    child->right_child = parent; 
return child; 
} 

// RR 회전 (왼쪽으로 회전한다)

// ±2를 가지는 A가 부모가 되고 A->right_child인 B가 child가 된다.
// A->right에 B가 가지고 있는 left_child를 대입하고 B의 left_child에 A을 대입한다.

AvlNode* rotate_RR(AvlNode *parent) 
{ 
    AvlNode *child = parent->right_child; 
    parent->right_child = child->left_child; 
    child->left_child = parent; 
return child; 
} 

// RL 회전 (오른쪽-왼쪽으로 회전한다)

// ±2를 가지는 A가 부모가 되고 A->right_child인 B가 child가 된다.
// A->right_child에 rotate_LL(B)가 반환하는 값을 대입한다. (B,C에 대해 오른쪽 회전)
// rotate_LL(B)호출시 B와 C가 변화가 생기고 다시 rotate_RR(A)을 호출하면 균형트리가 된다. 

AvlNode* rotate_RL(AvlNode *parent) 
{ 
    AvlNode *child = parent->right_child; 
    parent->right_child = rotate_LL(child); 
return rotate_RR(parent); 
} 

// LR 회전 (왼쪽-오른쪽으로 회전한다)

// ±2를 가지는 A가 부모가 되고 A->left_child인 B가 child가 된다.
// A->left_child에 rotate_RR(B)가 반환하는 값을 대입한다. (B,C에 대해 왼쪽 회전)
// rotate_RR(B)호출시 B와 C가 변화가 생기고 다시 rotate_LL(A)을 호출하면 균형트리가 된다. 

AvlNode* rotate_LR(AvlNode *parent) 
{ 
    AvlNode *child = parent->left_child; 
    parent->left_child = rotate_RR(child); 
return rotate_LL(parent); 
} 

// 트리의 높이 측정 함수
// 순환호출로 각각의 높이를 구하고 이들 중에서 더 큰값에 1을 더하면 트리의 높이가 된다.
int get_height(AvlNode *node) 
{ 
int height=0; 
if(node != NULL) 
        height = 1+max(get_height(node->left_child),get_height(node->right_child)); 
return height; 
} 

// 노드의 균형인수 반환 함수
// 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이
int get_balance(AvlNode *node) 
{ 
if(node == NULL) return0; 
return get_height(node->left_child) - get_height(node->right_child); 
} 

// 균형 트리를 만드는 함수
AvlNode* balance_tree(AvlNode **node) 
{ 
int height_diff= get_balance(*node); 

if(height_diff > 1) // 왼쪽 서브트리의 균형을 맞춘다
    { 
if(get_balance((*node)->left_child) > 0) 
            *node = rotate_LL(*node); 
else
            *node = rotate_LR(*node); 
    } 
elseif(height_diff < -1) // 오른쪽 서브트리의 균형을 맞춘다
    { 
if(get_balance((*node)->right_child) < 0) 
            *node = rotate_RR(*node); 
else
            *node = rotate_RL(*node); 
    } 
return *node; 
} 

// AVL 트리의 삽입 연산
// key에 대해 순환호출을 반복하므로써 트리에 삽입 한 후 균형화 함수를 호출한다.
AvlNode* avl_add(AvlNode **root,int key) 
{ 
if(*root == NULL) 
    { 
        *root = (AvlNode*)malloc(sizeof(AvlNode)); 
if(*root == NULL) 
        { 
            printf("메모리 할당 실패\n"); 
            exit(-1); 
        } 

        (*root)->data = key;     
        (*root)->left_child = (*root)->right_child = NULL; 
    } 
elseif(key < (*root)->data) 
    { 
        (*root)->left_child = avl_add(&((*root)->left_child),key); 
        (*root) = balance_tree(root);  
    } 
elseif(key > (*root)->data) 
    { 
        (*root)->right_child = avl_add(&((*root)->right_child), key); 
        (*root) = balance_tree(root); 
    } 
else
    { 
        printf("중복 키로 인한 삽입 실패\n"); 
        exit(-1); 
    } 
return *root; 
} 

// AVL 트리 탐색 함수
// 일반 적인 이진 트리의 탐색 함수와 같다. AVL도 이진 탐색 트리의 일종이다.
AvlNode* avl_search(AvlNode *node, int key) 
{ 
if(node == NULL) returnNULL; 

    printf("%d->",node->data); 

if(key == node->data)  
return node; 
elseif(key < node->data) 
        avl_search(node->left_child,key); 
else
        avl_search(node->right_child,key); 
} 

int main() 
{ 
    avl_add(&root,8); 

    avl_add(&root,9); 
    avl_add(&root,10); 
    avl_add(&root,2); 
    avl_add(&root,1); 
    avl_add(&root,5); 
    avl_add(&root,3); 
    avl_add(&root,6); 
    avl_add(&root,4); 
    avl_add(&root,7); 
    avl_add(&root,11); 
    avl_add(&root,12); 

    avl_search(root,12); 

return0; 
}