AVL Tree 구현

AVL Tree를 구현해보자.

 

AVL Tree는 이진 트리의 균형이 맞지 않을 때 탐색연산의 시간 복잡도가 O(log2n)아닌 O(n)에 가까운 시간 복잡도를 보이는데

이런 단점을 해결위한 트리중 하나이다.

 

균형이 무너진 이진트리와 균형이 잡힌 이진트리

위 그림을 봤을 때 왼쪽은 균형이 무너진 이진트리이고 오른쪽은 균형이 잡힌 이진트리이다.

5를 탐색한다고 했을 때 한눈에 봐도 성능차이가 난다는 것을 알 수 있다.

 

AVL Tree는 균형이 무너졌는지 확인 후 균형을 맞추는 작업을 한다.

 

여기서 균형이 무너졌는지 확인 하는 방법은 균형 인수(Balance Factor)를 구하여 확인한다.

 

균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이

 

서브트리의 높이를 구하는 방법은 자식 노드를 가지고 있는 부모노드 의 갯수를 체크하여 높이를 확인한다.

 

ex)

 

왼쪽 트리를 계산하면 root Node를 기준으로 하였을 때 왼쪽 높이는 0, 오른쪽 높이는 3이 된다.

따라서 균형 인수는 3이 되고, 반면 오른쪽 트리의 왼쪽 높이는 1, 오른쪽 높이도 1이기 때문에 균형 인수는 0이 된다.

 

높이를 구하는 코드는 다음과 같다.

 

AVL_CheckDepth()

static int AVL_CheckDepth(BTreeNode *rootNode)
{
    int depth = 1;

    if (!rootNode)
        return 0;
    else if (rootNode->left == NULL && rootNode->right == NULL)
        return 0;
    else if (rootNode->left != NULL)
        depth += AVL_CheckDepth(rootNode->left);
    else if (rootNode->right != NULL)
        depth += AVL_CheckDepth(rootNode->right);

    return depth;
}

노드의 자식노드가 없다면 return 0을 하고 만약 자식 노드가 있으면 다시 자신의 함수로 들어가서 높이를 구한다.

 

AVL_CheckRotation()

static int AVL_CheckRotation(BTreeNode *rootNode)
{
    TR_FUNC(TRACE);

    int left_val = 0;
    int right_val = 0;
    int diff_val = 0;

    BTreeNode *leftNode = rootNode->left;
    BTreeNode *rightNode = rootNode->right;

    left_val = AVL_CheckDepth(leftNode);
    printf("left depth is %d \r\n", left_val);

    right_val = AVL_CheckDepth(rightNode);
    printf("right depth is %d \r\n", right_val);

    diff_val = abs(left_val - right_val);

    if (diff_val < 2)
        return NOT_ROTATION;
    else if (right_val > left_val)
        return NEED_RX_ROTAION;
    else
        return NEED_LX_ROTAION;

    return ERROR_RETURN;

}

Rotation함수를 만들어 균형인수(diff_val) 가 2 이상 차이 나면 어떻게 균형을 맞출지에 대해 return한다.

 

AVL 트리의 Rotation은 크게 4가지가 있다.

 

1. RR Rotation

 

2. LL Rotation

 

3. RL Rotation

 

4. LR Rotation

 

RR, LL Rotation

1번노드와 2번노드 연결을 끊은 후, 2번 노드의 자식노드로 보내고 2번 노드를 부모노드로 바꾸면 된다. 

 

RL, LR Rotation

RL, LR 역시 RR, LL로 바꿔주면 된다.

 

1, 2번 같은 경우 AVL_CheckRotation() 함수로 판단이 되지만 3, 4번 경우는 LR, RL을 판단할 함수가 추가로 필요 하다.

 

AVL_CheckSecondRotation()

static int AVL_CheckSecondRotation(BTreeNode *rootNode)
{
    TR_FUNC(TRACE);

    if (AVL_CheckDepth(rootNode->left))
        return NEED_XL_ROTATION;
    else if (AVL_CheckDepth(rootNode->right))
        return NEED_XR_ROTATION;

    return NOT_ROTATION;
}

두번째 노드를 판단하는 함수이다 이 함수는 첫번째 노드가 L인지, R인지 중요하지 않다.

따라서 return 값이 NEED_XL_ROTATION 또는 NEED_XR_ROTATION 으로 RETURN 한다.

 

이제  Balance()를 함수를 구현 해보자

 

우선 Balance()함수에서는 RR, RL, LR, LL 인지 구분해야 한다.

 

Balance()

static int AVL_Balance(BTreeNode **root)
{
    TR_FUNC(TRACE);

    int result_1 = AVL_CheckRotation(*root);

    if (result_1 == NEED_RX_ROTATION) {
        printf("RX ROTATION \r\n");
        AVL_ChangeRR(root, AVL_CheckSecondRotation((*root)->right));
    } else if (result_1 == NEED_LX_ROTATION) {
        printf("LX ROTATION \r\n");
        AVL_ChangeLL(root, AVL_CheckSecondRotation((*root)->left));
    } else {
        printf("NOT ROTATION \r\n");
    }

    return 0;
}

우선 result_1 변수를 통해 RX 인지, LX 인지 판단한다. 그리고 이 값을 통해 두번째가 XR, XL 인지 판단한다.

 

그리고 AVL_ChangeXX() 함수의 2번재 Arg에 두번째 판단 값을 넣는다.

 

AVL_ChangeXX()에서 XX는 RR 또는 LL 값을 같는다. (RL 또는 LR 은 최종적으로 RR, LL 로 값이 바뀌기 때문)

 

AVL_ChangeRR() 만 보자

static int AVL_ChangeRR(BTreeNode **root, int second_result)
{

    BTreeNode **returnRoot = root;
    BTreeNode *checkRoot = (*root)->right;
    BTreeNode *originRoot = *root;

    if (!(checkRoot)) {
        return -1;
    } else if (second_result == NEED_XR_ROTATION) {
        /* == Change ReBalance == */
        BTreeNode *newRoot = (*root)->right;
        originRoot->right = newRoot->left;
        newRoot->left = originRoot;
        *returnRoot = newRoot;
        
    } else if (second_result == NEED_XL_ROTATION) {
        /* == Change R -> L == */
        BTreeNode *originPNode = originRoot->right;
        BTreeNode *originCNode = originPNode->left;
        BTreeNode *mvNode = originCNode->right;

        originRoot->right = originCNode;
        originCNode->right = originPNode;
        originPNode->left = mvNode;

        /* == Change ReBalance == */
        BTreeNode *newRoot = (*root)->right;

        originRoot->right = newRoot->left;
        newRoot->left = originRoot;
        *returnRoot = newRoot;
    }

    return 0;
}

second_result 가 XR 인 경우를 보자 이 경우 RR 회전이므로 그냥 돌리면 된다.

2번 노드 = originRoot->right = newRoot

1번 노드 = originRoot 

RR 회전을 할려면 2번 노드가 부모노드가 되고 2번 노드의 왼쪽에 1번 노드를 붙이면 된다. (newRoot->left = originRoot) 

 

second_result 가 XL 인 경우를 보자 이 경우 RL 회전이므로 우선 RR로 변경한다.

 

3번 노드 = originRoot->right = originPNode

2번 노드 = originPNode->left = originCNode

 

1번 노드에 2번 노드를 연결 해주고 (originRoot->right = originCNode)

2번 노드에 3번노드를 연결해준다. (originCNode->right = originPNode)

 

코드 링크: https://github.com/KJT9109/Data_Structure/tree/master/AVL_Tree