자료구조 프로그래밍 Lab07) AVL Tree 만들기

자료구조 프로그래밍 Lab07) AVL Tree 만들기 

AVL Tree란 balanced Tree 중에서 가장 초기에 나온 tree이다.

BST의 효율성을 증대시키기 위해서 level을 최대한 낮춰야하는데, 이 중 한 방법으로

AVL tree가 등장하였다.(AVL인 이유는 이 tree를 고안한 G.M. Adelson-Velskii와 E.M. Landis의 이름들을 따서 지었다)

AVL tree는 다음과 같이 왼쪽 subtree의 높이와 오른쪽 subtree의 높이 차를 bf에 저장하여 bf의 절댓값이 1 이하인 경우를 계속 유지해야한다.

그래서 재귀적으로 삽입을 수행한 후, 루트까지 오면서 bf를 체크하고 bf의 절댓값이 2인 경우에는 회전을 통하여 균형을 수정한다.

그리고 이러한 회전에는 총 4가지가 있는데 다음과 같다.

1) LL rotation

2) RR rotation

3) LR rotation

4) RL rotation

문제

해결

// 자료형
typedef struct node* nodePointer;
typedef struct node {
    int data;
    nodePointer lch, rch;
    int bf;
}node;
nodePointer * queue;
 
// 호출 함수들
void avlInsert(nodePointer*, int, int*);
void leftRotation(nodePointer*, int*);
void rightRotation(nodePointer*, int*);
 
// avl 삽입 함수
void 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
    }
 
    // root가 더 크면 lch 삽입
    else if ((*ptr)->data > data) {
        avlInsert(&(*ptr)->lch, data, ub); // lch 삽입
 
        // unbalance true 되면
        if (*ub) {
            switch ((*ptr)->bf) {
                // -1 일 경우
                case -1:
                    (*ptr)->bf = 0;
                    *ub = 0; // unbalance false
                    break;
 
                // 0 일 경우
                case 0:
                    (*ptr)->bf = 1;
                    break;
 
                // 1일 경우 LeftRotation
                case 1:
                    leftRotation(ptr, ub); // 회전
            }
        }
 
    }
    
    // data가 더 크면 rch 삽입
    else {
        avlInsert(&(*ptr)->rch, data, ub); // rch 삽입
 
        // unbalance true 되면
        if (*ub) {
            switch ((*ptr)->bf){
                // 1일 경우
                case 1:
                    (*ptr)->bf = 0;
                    *ub = 0; // unbalance false
                    break;
                
                // 0 일 경우
                case 0:
                    (*ptr)->bf = -1;
                    break;
                
                // -1일 경우 RightRotation
                case -1:
                    rightRotation(ptr, ub); // 회전
            }
        }
    }
}
 
// LeftRotation
void 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; // bf 변경
        (*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) {
            // 0 일경우 셋다 0
            case 0:
                ch->bf = (*ptr)->bf = 0;
                break;
 
            // 1 일 경우 (lch만 있다)
            case 1:
                ch->bf = 0; // 자식노드는 lch 받았으므로 균형
                (*ptr)->bf = -1; // 부모노드는 lch에 rch 받아야 하는데 못받았으므로 rch만 있음
                break;
 
            // -1 일 경우(rch만 있다)
            case -1:
                ch->bf = 1; // 자식 노드는 rch에 lch 받아야하는데 lch 못받았으므로 lch만 있음
                (*ptr)->bf = 0; // 부모노드는 rch 받았으므로
        }
        (*ptr) = gch; // 중심 변경
    }
 
    (*ptr)->bf = 0;
    *ub = 0; // unbalance false
}
 
void 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;
 
            // 1일 경우 (lch만 있는 경우)
            case 1:
                (*ptr)->bf = 0; // 부모노드는 lch를 받아서 균형
                ch->bf = -1; // 자식 노드는 lch에 rch를 받아야하는데 없어서 rch만 있음
                break;
 
            // -1일 경우 (rch만 있는 경우)
            case -1:
                (*ptr)->bf = 1; // 부모노드는 rch에 lch를 받아야하는데 없어서 lch만 있음
                ch->bf = 0; // 자식 노드는 rch 받아서 균형
        }
        (*ptr) = gch; // 중심 변경
 
    }
    (*ptr)->bf = 0;
    *ub = 0; // unbalance false
}

참고)

삭제 알고리즘은 삽입과 동일하게 계속 재귀적으로 탐색해서 내려가고

찾았다면 해당 구간에서 bst를 통해 삭제한 뒤 balance에 false를 주고 올라가면서 재귀적으로 체크하여 회전처리해준다

이 때 회전은 balance factor는 삽입과 반대로 처리해주는것 주의!