AVL 트리(높이 균형 이진 탐색 트리) 개념과 삽입 연산

이진 트리, 이진 탐색 트리 개념 참고

 

: hyunah-home.tistory.com/entry/%EC%9D%B4%EC%A7%84%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%84%B1%EC%A7%88-%EC%9A%B4%ED%96%89%EA%B3%BC-%EC%9D%91%EC%9A%A9-%EC%88%98%EC%8B%9D%ED%91%9C%ED%98%84-%ED%8A%B8%EB%A6%AC-%EC%9D%B4%EC%A7%84%ED%8A%B8%EB%A6%AC%EB%A1%9C%EC%9D%98-%EB%B3%80%ED%99%98%EB%B2%95-%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89%ED%8A%B8%EB%A6%AC

이진트리의 성질, 운행과 응용; 수식표현 트리, 이진트리로의 변환법, 이진탐색트리

 

이진 탐색 트리

: key(왼쪽 부분 트리) < key(루트) < key(오른쪽 부분 트리)를 만족하는 이진 트리. 중순위 운행하면 오름차순으로 정렬된 값을 얻을 수 있다.

 

 

 

AVL 트리(높이 균형 이진 탐색 트리)

: 모든 노드의 왼쪽과 오른쪽 부분트리의 높이 차이가 1 이하인 이진탐색 트리. 삽입, 삭제 연산을 하여 트리 높이가 불균형 상태가 된다면 노드들을 재배치하여 높이 균형 상태로 만들어야 한다. 이진트리의 원소가 한쪽으로 몰려 연산의 속도가 늦어지는 단점을 보완할 수 있다.

 

균형 인수 = ( 왼쪽 부분 트리의 높이 - 오른쪽 부분트리의 높이 )

 

즉, 높이 균형 이진 탐색 트리는 모든 노드의 균형인수의 절댓값이 1 이하여야 함.

 

 

높이 균형 이진 탐색트리의 예시와 각 노드별 균형 인수

 

 

AVL 트리 노드의 구현 코드는 다음과 같다.

 

typedef struct Avl_node{
    struct Avl_node *left_child, *right_child;
    int data;
} Avl_node;

Avl_node *root;

 

 

 

 

 

 

AVL 트리의 연산

 

탐색 연산

: 이진 탐색 트리와 동일. 노드 구성의 변화가 일어나는 연산이 아니므로 ( 노드가 새로 생기거나 삭제되는 것이 아님 ) 높이 균형을 유지하기 위한 별도의 균형 조정 연산이 필요하지 않다.

 

 

 

삽입 연산

: 삽입 후에 불균형 상태가 되었다면, 불균형 상태가 된 ( 균형 인수의 절댓값이 2 이상이 된 ) 노드 중에서, 삽입 위치에서 가장 가까운 조상 노드(A)의 부분트리를 조정하는 재균형 연산이 별도로 필요하다. 재균형 연산은 A를 중심으로 회전함으로써 진행한다.

 

 

예시를 보면서 더 자세히 설명해보겠다.

 

삽입 시행 전

 

삽입 연산을 시행하기 전에 트리 구성이 위의 그림과 같았다고 하자.

 

 

저 트리에서 1이라는 값을 가진 노드를 새로 삽입하면, 3의 왼쪽 부분 트리에 위치하여, 5와 7의 균형 인수값을 초과되게 만든다. 따라서 삽입 위치에서 가장 가까운 조상 노드인 5를 기준으로 회전(rotation)을 시행해야 한다.

 

 

삽입 시행 후

5를 기준으로 오른쪽으로 회전시킨 결과 3이 5의 부모노드가 되고, 모든 노드의 균형 인수 값이 1 이하인 상태로 변화하였다. 이러한 회전 연산을 재균형 연산이라고 하며, 회전의 종류에는 총 4가지가 존재한다.

 

 

 

 

삽입된 노드(위의 예시에서는 1)를 N이라고 하고, 삽입 노드로부터 가장 가까우면서 균형 인수가 초과된 조상 노드(위의 예시에서는 5)를 A라고 하겠다.

 

 

 

LL 회전 예시

 

- LL 회전 (단회전)

: N이 A의 왼쪽 자식 노드의 왼쪽 부분트리에 삽입된 경우에 시행. 위에서 소개한 예시 역시 이 경우에 해당한다. A부터 N까지의 노드를 오른쪽으로 회전시킨다. 위 그림에서 N은  2, A는 6이다. 6을 기준으로 2부터 6까지의 노드를 오른쪽으로 회전시켰다. 자식노드였던 5가 부모노드였던 6을 오른쪽 자식으로 가지는 것이다. 이때 5가 가지고 있던 기존의 오른쪽 부분트리는 부모노드였던 6의 왼쪽 부분트리로 이동한다.

 

 

그림으로 표시하면 이렇게 된다. 위 그림에서의 5가 이 그림에서 B에 해당하고, 균형 인수가 초과한 노드인 6이 A에 해당한다. 자식노드였던 B가 부모노드였던 A를 오른쪽 자식으로 가지게 되고, B의 오른쪽 부분트리(파란색)은 부모노드였던 A의 왼쪽 부분트리로 이동하였다.

 

 

이러한 과정을 코드로 나타내면 다음과 같다.

 

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

 

 

 

 

RR 회전 예시

 

- RR 회전 (단회전)

: N이 A의 오른쪽 자식 노드의 오른쪽 부분트리에 삽입된 경우에 시행. LL 회전의 정반대 경우로, A부터 N까지의 노드를 왼쪽으로 회전시킨다. 위 그림에서 N은 9, A는 6이며 6을 기준으로 9부터 6까지의 노드를 왼쪽으로 회전시켰다. 자식 노드였던 8이 부모노드였던 6을 왼쪽 자식으로 가지게 된다. 8이 가지고 있던 기존의 왼쪽 부분트리는 부모노드였던 6의 오른쪽 부분트리로 이동한다.

 

 

그림으로 표시하면 이렇게 된다. 위 그림에서의 8가 이 그림에서 B에 해당하고, 균형 인수가 초과한 노드인 6이 A에 해당한다. 자식노드였던 B가 부모노드였던 A를 왼쪽 자식으로 가지게 되고, B의 왼쪽 부분트리(파란색)는 부모노드였던 A의 오른쪽 부분트리로 이동하였다.

 

코드로 표현하면 이렇다.

 

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

 

 

 

 

다음으로 소개하는 회전은 두 번의 회전이 이루어지는 복회전이다. 그러나 그 사실보다 중요한 것은 결과적인 A와 N의 위치관계이다. 따라서 과정이 이해가 가지 않는다면, 그림을 보고 A,B,C의 위치 관계가 어떻게 변화하는지를 중점으로 이해하려고 노력하길 권한다.

 

 

 

LR 회전 예시

- LR 회전 (복회전)

: N이 A의 왼쪽 자식 노드의 오른쪽 부분트리에 삽입된 경우에 시행. 왼쪽으로 한 번 회전(RR 회전)한 후, 오른쪽으로 한 번 회전(LL회전)하여 N이 A의 자식 노드와 A 노드 사이에 위치하도록 만든다. 위 그림에서 N은 파란색으로 표시된 C의 왼쪽 부분트리에 속한 노드이고, A는 A이다. B를 기준으로 RR 회전하여 A의 왼쪽 자식노드가 C가 되도록 하고, C가 왼쪽 자식노드로 B를 가지도록 만든 후, A를 기준으로 LL 회전하여 C가 B와 A의 중간에 위치하는 부모노드가 되도록 만든다. 기존 C의 왼쪽 부분트리와 오른쪽 부분트리는 각각 B의 오른쪽 부분트리와 A의 왼쪽 부분트리로 이동한다.

 

이러한 과정을 코드로 표현하면 다음과 같다.

 

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

 

 

 

 

RL 회전 예시

- RL 회전 (복회전)

: N이 A의 오른쪽 자식 노드의 왼쪽 부분트리에 삽입된 경우에 시행. 오른쪽으로 한 번 회전(LL회전)한 후, 왼쪽으로 한 번 회전(RR회전)하여 N이 A와 A의 자식 노드 사이에 위치하도록 만든다. 위 그림에서 N은 파란색으로 표시된 C의 왼쪽 부분트리에 속한 노드이고 A는 A이다. B를 기준으로 LL 회전하여 A의 오른쪽 자식노드가 C가 되도록 하고, C가 오른쪽 자식노드로 B를 가지도록 만든 후, A를 기준으로 RR회전하여 C가 A와 B의 중간에 위치하는 부모노드가 되도록 만든다.

C가 가지고 있던 기존의 왼쪽, 오른쪽 부분트리는 각각 A의 오른쪽 부분트리와 B의 왼쪽 부분트리로 이동한다.

 

이 과정을 코드로 표현하면 다음과 같다.

 

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

 

 

 

 

이러한 재균형 연산을 사용하는 AVL 트리 삽입 연산의 전체 코드는 아래와 같다.

 

// 균형 인수 구하기
int get_height_diff(Avl_node *node){
    if (node == NULL) return 0;
    return get_height(node->left) - get_height(node->right);

// 삽입 후 재균형
Avl_node *rebalance(Avl_node **node){
    int height_diff = get_height_diff(*node);
    if (height_diff > 1){
        if (get_height_diff((*node)->left_child) > 0)
            *node = rotate_LL(*node);
        else
            *node = rotate_LR(*node);
    }
    else if (height_diff < -1){
        if (get_height_diff((*node)->right_child) < 0)
            *node = rotate_RR(*node);
        else
            *node = rotate_RL(*node);
    }
    return *node;
}

void insert_node_Avl(Avl_node **root, int key){
    insert_node(root, key);
    rebalance(root);
}

 

시간 복잡도 : 높이가 h인 AVL 트리에서 삽입연산을 시행할 때, 최대 1번의 회전이 필요하다. 따라서 삽입 연산의 시간복잡도는 일반 이진트리에서의 삽입 연산 시간 복잡도와 동일한 O(h)(=O(logn))이다.