AVL Tree(변형 이진탐색트리)

AVL Tree

이진탐색트리(BST, Binary Search Tree)의 효율성은 최대한의 높이(height)를 낮추는 것에 있다.

탐색, 삽입, 삭제와 같은 연산 시의 시간복잡도는 O(h)일 만큼 height에 달려있기에 height를 낮추는 것이 이진탐색트리의 효율성을 높이는 방법이 될 수 있다.

 

그래서 이진탐색트리(이하 BST)의 효율성을 최대로 살리기 위해 height를 낮추는 방법 중 가장 대표적인 방법으로 AVL 트리를 들 수 있다. 초기에 제안되었던 방식으로 G.M. Adelson-Velskii와 E.M. Landis가 자신들의 이름을 따서 AVL Tree로 명하였다.

 

핵심은 높이를 낮추는 것으로 Balanced Factor(bf, 또는 높이)를 비교하여 좌측 서브트리와 우측 서브트리의 높이가 2 이상 차이날 경우 이를 조정해주는 방법을 통해 높이를 낮춘다.

 

출처 https://en.wikipedia.org/wiki/AVL_tree

위의 사진처럼 bf(높이 차이)가 2이상이 될 경우 이를 조정을 통해 BST의 높이를 낮추는 방식이다.

 

• 기본적인 삽입과 삭제의 과정은 이진탐색트리와 동일하다.
• 이진탐색트리의 삽입과 삭제과정을 구현한 다음 높이의 조정이 필요할 경우 조정해준다.
• 트리 내부의 조정이 필요한 경우는 4가지다.

 

LL: 왼쪽-왼쪽

---

LR: 왼쪽-오른쪽

---

RR: 오른쪽-오른쪽

---

RL : 오른쪽 왼쪽

---

AVL Tree 구현

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

// 자료형
typedef struct node* nodePointer;
typedef struct node {
    int data;
    nodePointer lch, rch;
    int bf;
}node;

// 호출 함수들
nodePointer avlInsert(nodePointer, int, int*);
nodePointer avlDelete(nodePointer, int, int*, int*);
nodePointer findMinNode(nodePointer root);
nodePointer leftRotation(nodePointer, int*);
nodePointer rightRotation(nodePointer, int*);
void printTree(nodePointer root);

// avl 삽입 함수
nodePointer avlInsert(nodePointer ptr, int data, int* ub) {

    // 위치가 null 이면 삽입
    if (ptr == NULL ) {
        (ptr) = (nodePointer)malloc(sizeof(node));
        (ptr)->data = data;
        (ptr)->bf = 0;
        (ptr)->lch = (ptr)->rch = NULL;
        *ub = 1; // unbalance true
        return ptr;
    }

    // lch 삽입
    else if ((ptr)->data > data) {
        ptr->lch = avlInsert(ptr->lch, data, ub); // lch 삽입

        // unbalance true 되면
        if (*ub) {
            switch (ptr->bf) {
            
                // lch X rch O 경우
            case -1:
                ptr->bf = 0;
                *ub = 0; // unbalance false
                break;

                // 밸런스 경우
            case 0:
                ptr->bf = 1;
                break;

                // lch O , rch X 경우 (LL, LR 상태)
            case 1:
                ptr = leftRotation(ptr, ub); // 회전
            }
        }
        return ptr;
    }

    // rch 삽입
    else {
        ptr->rch = avlInsert(ptr->rch, data, ub); // rch 삽입

        // unbalance true 되면
        if (*ub) {
            switch (ptr->bf) {

                // lch O rch X 경우
            case 1:
                ptr->bf = 0;
                *ub = 0; // unbalance false
                break;

                // 밸런스 경우
            case 0:
                ptr->bf = -1;
                break;

                // lch X rch O 경우 (RR, RL 상태)
            case -1:
                ptr = rightRotation(ptr, ub); // 회전
            }
        }
        return ptr;
    }
}

// avl 삭제 함수
nodePointer avlDelete(nodePointer ptr, int data, int* ub, int* left) {
    nodePointer t_np = NULL;

    // null 처리
    if (ptr == NULL) {
        return NULL;
    }

    //ㅣ초
    if ((ptr)->data > data) {
        ptr->lch = avlDelete(ptr->lch, data, ub, left); // lch 삭제
    }

    // rch 
    else if (ptr->data < data){
        ptr->rch = avlDelete(ptr->rch, data, ub, left); // rch 삭제
    }

    // 찾았을 경우 삭제 처리
    else {
        // 자식노드가 두개 있을경우(바로 다음값 가져와서 교환)
        if (ptr->lch != NULL && ptr->rch != NULL) {
            t_np = findMinNode(ptr->rch);
            // lch 삭제
            if (ptr->rch->data != t_np->data) {
                *left = 1;
            }
            ptr->data= t_np->data;
            ptr->rch = avlDelete(ptr->rch, t_np->data, ub, left); // 오른쪽 트리 끝값 삭제
        }

        // 실제 삭제
        // 자식노드가 하나 이하일 경우
        else {
            t_np = (ptr->lch == NULL) ? ptr->rch : ptr->lch;
            free(ptr); // 삭제
            *ub = 1;
            return t_np; // 자식트리를 반환한다
        }
    }

    // unbalance true
    if ((*ub)) {
        // lch 삭제
        if((*left)){
            switch (ptr->bf) {
                // lch O, rch X 경우
                ptr->bf = 0;
                break;

                // 밸런스 경우
            case 0:
                ptr->bf = -1;
                break;

                // lch X , rch O 경우 (RR, RL 조정 필요)
            case -1:
                ptr = rightRotation(ptr, ub); // 회전
            }
        }

        // rch 삭제
        else{
            switch (ptr->bf) {

                // lch X, rch O 경우
            case -1:
                ptr->bf = 0;
                break;

                // 밸런스 경우 
            case 0:
                ptr->bf = 1;
                break;

                // lch O , rch X 경우 (LL, LR 조정 필요)
            case 1:
                ptr = leftRotation(ptr, ub); // 회전
            }
        }
    }

    return ptr;
}

// LeftRotation
nodePointer leftRotation(nodePointer ptr, int* ub) {

    nodePointer ch, gch;
    ch = ptr->lch;

    // LL 의경우
    if (ch->bf == 1) {
        ptr->lch = ch->rch; // ptr의 lch에 자식의 rch 연결
        ch->rch = ptr; // 자식의 rch에 ptr 연결 (중심 변경)
        ptr->bf = 0; 
        ptr = ch; 
    }

    // LR의 경우
    else {
        gch = ch->rch; // 손자 노드는 자식의 rch
        ch->rch = gch->lch; // 자식 노드의 rch는 손자노드의 lch
        gch->lch = ch; // 손자 노드의 lch는 자식
        ptr->lch = gch->rch; // 부모 노드의 lch는 손자노드의 rch
        gch->rch = ptr; // 손자 노드의 rch는 부모

        // 손자노도의 bf에 따라
        switch (gch->bf) {
            // bf 초기화
        case 0:
            ch->bf = ptr->bf = 0;
            break;

            // 교환하지 않은 자식포인터에는 이미 값 존재
            // lch O rch X
        case 1:
            ch->bf = 0; // 자식노드는 lch 받았으므로 균형
            ptr->bf = -1; // 부모노드는 lch에 rch 받아야 하는데 못받았으므로 rch만 있음
            break;

            // lch X rch O
        case -1:
            ch->bf = 1; // 자식 노드는 rch에 lch 받아야하는데 lch 못받았으므로 lch만 있음
            ptr->bf = 0; // 부모노드는 rch 받았으므로
        }
        ptr = gch; // 중심 변경
    }

    ptr->bf = 0;
    *ub = 0; // unbalance false
    return ptr;
}

nodePointer rightRotation(nodePointer ptr, int* ub) {

    nodePointer ch, gch;
    ch = ptr->rch;

    // RR일 경우
    if (ch->bf == -1) {
        ptr->rch = ch->lch; // 부모 노드의 rch에 자식 노드의 lch
        ch->lch = ptr; // 자식 노드의 lch에 부모노드 (중심 변경)
        ptr->bf = 0;
        ptr = ch; 
    }

    // RL일 경우
    else {
        gch = ch->lch; // 손자 노드는 자식의 lch
        ch->lch = gch->rch; // 자식 노드의 lch에 손자노드의 rch
        gch->rch = ch; // 손자 노드의 rch에 자식노드
        ptr->rch = gch->lch; // 부모 노드의 rch에 손자 노드의 lch
        gch->lch = ptr; // 손자 노드의 lch에 부모노드

        // 손자 노드의 bf에 따라
        switch (gch->bf) {

            // 0일 경우
        case 0:
            ptr->bf = ch->bf = 0;
            break;

            // 교환하지 않은 자식포인터에는 이미 값 존재
            // lch O rch X
        case 1:
            ptr->bf = 0; // 부모노드는 lch를 받아서 균형
            ch->bf = -1; // 자식 노드는 lch에 rch를 받아야하는데 없어서 rch만 있음
            break;

            // lch X rch O
        case -1:
            ptr->bf = 1; // 부모노드는 rch에 lch를 받아야하는데 없어서 lch만 있음
            ch->bf = 0; // 자식 노드는 rch 받아서 균형
        }
        ptr = gch; // 중심 변경

    }
    ptr->bf = 0;
    *ub = 0; // unbalance false
    return ptr;
}

// 최소노드 찾기
nodePointer findMinNode(nodePointer root) {
    nodePointer search_np = root;
    while (search_np->lch != NULL) {
        search_np = search_np->lch;
    }
    return search_np;
}

// 전위 순회 방식 
void printTree(nodePointer root) {
    if (root == NULL) {
        return;
    }

    printTree(root->lch);
    printf("%d ", root->data);
    printTree(root->rch);
}

void main() {
    nodePointer root = NULL;
    int ub = 0;
    int left = 0;

    root = avlInsert(root, 8, &ub);
    root = avlInsert(root, 12, &ub);
    root = avlInsert(root, 19, &ub);
    root = avlInsert(root, 6, &ub);
    root = avlInsert(root, 2, &ub);
    root = avlInsert(root, 25, &ub);
    root = avlInsert(root, 3, &ub);
    root = avlInsert(root, 5, &ub);

    printTree(root);

    root = avlDelete(root, 6, &ub, &left);
    root = avlDelete(root, 12, &ub, &left);
    root = avlDelete(root, 5, &ub, &left);

    printf("\n");
    printTree(root);

}