[Data Structures] AVL Tree (AVL 트리)

AVL Tree

일반적인 이진탐색 트리의 경우 노드가 한 방향으로 쏠릴 경우 연결리스트와 동일해져 이진 탐색 트리의 장점을 잃게 된다. 이를 개선하기 위해 트리의 균형을 유지하는 트리가 AVL 트리이다.

 

Balance Factor

AVL 트리에서는 균형의 정도를 표현하기 위해 Balance Factor라는 것을 사용하는데 이는 왼쪽 서브 트리와 오른쪽 서브 트리의 height의 차이로 계산된다. 

 

LL 회전

Balance Factor가 2인 노드가 있을 때, 그 노드의 왼쪽 자식 노드의 왼쪽 서브트리에 노드가 추가된 경우를 LL 상태라고 한다. 이러한 경우에는 LL 회전을 통해 트리의 균형을 맞춘다.

LL 회전을 일반화 하면 다음과 같다.

서브 트리 x 왼쪽에 노드가 추가된다면 LL회전을 수행하게 된다. 이때 k1 노드가 루트노드가 되고 k2가 k1의 오른쪽 자식 노드가 되어야 한다. 이때 서브 트리 y가 들어가야할 적절한 자리는 자연스럽게 k2의 왼쪽이 된다.

 

RR 회전

RR회전도 LL회전과 방향만 다르기 때문에 설명을 생략한다.

 

LR  회전

Balance Factor가 2인 노드가 있을 때, 그 노드의 왼쪽 자식 노드의 오른쪽 서브트리에 노드가 추가된 경우를 LR 상태라고 한다. 이러한 경우에는 추가된 노드 오른쪽에 null노드를 추가했다고 치고 추가된 노드의 부모 노드에 RR 회전을 먼저 수행하여 LL상태를 만든 후, LL회전 하여 균형을 맞춘다. 그림을 보고 이해하자.

 

RL 회전

RL회전 역시 LR회전과 방향만 다르기 때문에 설명을 생략한다.

 

Implementation

다음은 AVL Tree의 ADT이다. 이전에 올린 BST와 거의 동일하고 Rebalance함수의 정의만 추가하였다.

typedef int Data;

typedef struct _biTreeNode
{
    Data data;
    struct _biTreeNode *left;
    struct _biTreeNode *right;
} BiTreeNode;

BiTreeNode *MakeBiTreeNode(void);
Data GetData(BiTreeNode *bt);
void SetData(BiTreeNode *bt, Data data);

BiTreeNode *GetLeftSubTree(BiTreeNode *bt);
BiTreeNode *GetRightSubTree(BiTreeNode *bt);

void MakeLeftSubTree(BiTreeNode *main, BiTreeNode *sub);
void MakeRightSubTree(BiTreeNode *main, BiTreeNode *sub);

BiTreeNode *RemoveLeftSubTree(BiTreeNode *bt);
BiTreeNode *RemoveRightSubTree(BiTreeNode *bt);
void ChangeLeftSubTree(BiTreeNode *main, BiTreeNode *sub);
void ChangeRightSubTree(BiTreeNode *main, BiTreeNode *sub);

void BSTMakeAndInit(BiTreeNode **pRoot);

Data BSTGetNodeData(BiTreeNode *bst);

void BSTInsert(BiTreeNode **pRoot, Data data);

BiTreeNode *BSTSearch(BiTreeNode *bst, Data target);

BiTreeNode *BSTRemove(BiTreeNode **pRoot, Data target);

void BSTShowAll(BiTreeNode *bst);

BiTreeNode *Rebalance(BiTreeNode **pRoot);

 

다음은 AVL Tree의 구현체이다.

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

BiTreeNode *MakeBiTreeNode(void)
{
    BiTreeNode *nd = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    nd->left = NULL;
    nd->right = NULL;
    return nd;
}

Data GetData(BiTreeNode *bt)
{
    return bt->data;
}

void SetData(BiTreeNode *bt, Data data)
{
    bt->data = data;
}

BiTreeNode *GetLeftSubTree(BiTreeNode *bt)
{
    return bt->left;
}

BiTreeNode *GetRightSubTree(BiTreeNode *bt)
{
    return bt->right;
}

void MakeLeftSubTree(BiTreeNode *main, BiTreeNode *sub)
{
    if (main->left != NULL)
        free(main->left);

    main->left = sub;
}

void MakeRightSubTree(BiTreeNode *main, BiTreeNode *sub)
{
    if (main->right != NULL)
        free(main->right);

    main->right = sub;
}

BiTreeNode *RemoveLeftSubTree(BiTreeNode *bt)
{
    BiTreeNode *delNode;

    if (bt != NULL)
    {
        delNode = bt->left;
        bt->left = NULL;
    }
    return delNode;
}

BiTreeNode *RemoveRightSubTree(BiTreeNode *bt)
{
    BiTreeNode *delNode;

    if (bt != NULL)
    {
        delNode = bt->right;
        bt->right = NULL;
    }
    return delNode;
}

void ChangeLeftSubTree(BiTreeNode *main, BiTreeNode *sub)
{
    main->left = sub;
}

void ChangeRightSubTree(BiTreeNode *main, BiTreeNode *sub)
{
    main->right = sub;
}

void BSTMakeAndInit(BiTreeNode **pRoot)
{
    *pRoot = NULL;
}

Data BSTGetNodeData(BiTreeNode *bst)
{
    return GetData(bst);
}

void BSTInsert(BiTreeNode **pRoot, Data data)
{
    BiTreeNode *pNode = NULL;   // parent node;
    BiTreeNode *cNode = *pRoot; // current node;
    BiTreeNode *nNode = NULL;   // new node;

    // 새로운 노드가 추가될 위치를 찾는다.
    while (cNode != NULL)
    {
        if (data == GetData(cNode))
            return;

        pNode = cNode;

        if (GetData(cNode) > data)
            cNode = GetLeftSubTree(cNode);
        else
            cNode = GetRightSubTree(cNode);
    }

    // 새 노드의 생성
    nNode = MakeBiTreeNode();
    SetData(nNode, data);

    if (pNode != NULL)
    {
        if (data < GetData(pNode))
            MakeLeftSubTree(pNode, nNode);
        else
            MakeRightSubTree(pNode, nNode);
    }
    else
    {
        *pRoot = nNode;
    }

    *pRoot = Rebalance(pRoot);
}

BiTreeNode *BSTSearch(BiTreeNode *bst, Data target)
{
    BiTreeNode *cNode = bst; // current node
    Data cd;                 // current data

    while (cNode != NULL)
    {
        cd = GetData(cNode);

        if (target == cd)
            return cNode;
        else if (target < cd)
            cNode = GetLeftSubTree(cNode);
        else
            cNode = GetRightSubTree(cNode);
    }

    return NULL;
}

BiTreeNode *BSTRemove(BiTreeNode **pRoot, Data target)
{
    BiTreeNode *pVRoot = MakeBiTreeNode(); // 가상 루트 노드
    BiTreeNode *pNode = pVRoot;            // parent node
    BiTreeNode *cNode = *pRoot;            // current node
    BiTreeNode *dNode;

    ChangeRightSubTree(pVRoot, *pRoot);

    while (cNode != NULL && GetData(cNode) != target)
    {
        pNode = cNode;

        if (target < GetData(cNode))
            cNode = GetLeftSubTree(cNode);
        else
            cNode = GetRightSubTree(cNode);
    }

    if (cNode == NULL)
        return NULL;

    dNode = cNode;

    if (GetLeftSubTree(dNode) == NULL && GetRightSubTree(dNode) == NULL)
    {
        if (GetLeftSubTree(pNode) == dNode)
            RemoveLeftSubTree(pNode);
        else
            RemoveRightSubTree(pNode);
    }

    else if (GetLeftSubTree(dNode) == NULL || GetRightSubTree(dNode) == NULL)
    {
        BiTreeNode *dcNode;

        if (GetLeftSubTree(dNode) != NULL)
            dcNode = GetLeftSubTree(dNode);
        else
            dcNode = GetRightSubTree(dNode);

        if (GetLeftSubTree(pNode) == dNode)
            ChangeLeftSubTree(pNode, dcNode);
        else
            ChangeRightSubTree(pNode, dcNode);
    }

    else
    {
        BiTreeNode *mNode = GetRightSubTree(dNode);
        BiTreeNode *mpNode = dNode;
        int delData;

        while (GetLeftSubTree(mNode) != NULL)
        {
            mpNode = mNode;
            mNode = GetLeftSubTree(mNode);
        }

        delData = GetData(dNode);
        SetData(dNode, GetData(mNode));

        if (GetLeftSubTree(mpNode) == mNode)
            ChangeLeftSubTree(mpNode, GetRightSubTree(mNode));
        else
            ChangeRightSubTree(mpNode, GetRightSubTree(mNode));

        dNode = mNode;
        SetData(dNode, delData);
    }

    if (GetRightSubTree(pVRoot) != *pRoot)
        *pRoot = GetRightSubTree(pVRoot);

    free(pVRoot);

    *pRoot = Rebalance(pRoot);
    return dNode;
}

void BSTShowAll(BiTreeNode *bst)
{
    if (bst == NULL)
        return;

    BSTShowAll(bst->left);
    printf("%d ", bst->data);
    BSTShowAll(bst->right);
}

BiTreeNode *RotateLL(BiTreeNode *bst)
{
    BiTreeNode *pNode;
    BiTreeNode *cNode;

    pNode = bst;
    cNode = GetLeftSubTree(pNode);

    ChangeLeftSubTree(pNode, GetRightSubTree(cNode));
    ChangeRightSubTree(cNode, pNode);

    return cNode;
}

BiTreeNode *RotateRR(BiTreeNode *bst)
{
    BiTreeNode *pNode;
    BiTreeNode *cNode;

    pNode = bst;
    cNode = GetRightSubTree(pNode);

    ChangeRightSubTree(pNode, GetLeftSubTree(cNode));
    ChangeLeftSubTree(cNode, pNode);

    return cNode;
}

BiTreeNode *RotateLR(BiTreeNode *bst)
{
    BiTreeNode *pNode;
    BiTreeNode *cNode;

    pNode = bst;
    cNode = GetLeftSubTree(pNode);

    ChangeLeftSubTree(pNode, RotateRR(cNode));
    return RotateLL(pNode);
}

BiTreeNode *RotateRL(BiTreeNode *bst)
{
    BiTreeNode *pNode;
    BiTreeNode *cNode;

    pNode = bst;
    cNode = GetRightSubTree(pNode);

    ChangeRightSubTree(pNode, RotateLL(cNode));
    return RotateRR(pNode);
}

int GetHeight(BiTreeNode *bst)
{
    int leftH;
    int rightH;

    if (bst == NULL)
        return 0;

    leftH = GetHeight(GetLeftSubTree(bst));
    rightH = GetHeight(GetRightSubTree(bst));

    if (leftH > rightH)
        return leftH + 1;
    else
        return rightH + 1;
}

int GetHeightDiff(BiTreeNode *bst)
{
    int lsh;
    int rsh;

    if (bst == NULL)
        return 0;

    lsh = GetHeight(GetLeftSubTree(bst));
    rsh = GetHeight(GetRightSubTree(bst));
    return lsh - rsh;
}

BiTreeNode *Rebalance(BiTreeNode **pRoot)
{
    int hDiff = GetHeightDiff(*pRoot);

    if (hDiff > 1)
    {
        if (GetHeightDiff(GetLeftSubTree(*pRoot)) > 0)
            *pRoot = RotateLL(*pRoot);
        else
            *pRoot = RotateLR(*pRoot);
    }

    if (hDiff < -1)
    {
        if (GetHeightDiff(GetRightSubTree(*pRoot)) < 0)
            *pRoot = RotateRR(*pRoot);
        else
            *pRoot = RotateRL(*pRoot);
    }

    return *pRoot;
}

 

노드를 추가 및 삭제할 때마다 Rebalance 함수의 호출이 필요하여 BSTInsert와 BSTRemove함수 마지막 부분에 이를 추가하였다.

 

- RotateLL

1. pNode의 왼쪽 노드를 cNode의 오른쪽 서브트리로 바꾼다.

2. cNode의 오른쪽 서브트리를 pNode로 바꾼다.

3. cNode를 return

 

- RotateRR

1. pNode의 오른쪽 노드를 cNode의 왼쪽 서브트리로 바꾼다.

2. cNode의 왼쪽 서브트리를 pNode로 바꾼다.

3. cNode를 return

 

- RotateLR

1. pNode의 왼쪽 노드를 cNode를 RR회전하였을 때 return되는 것으로 바꾼다.

2. pNode를 LL회전 한 것을 return한다.

 

- RotateRL

1. pNode의 오른쪽 노드를 cNode를 LL회전하였을 때 return되는 것으로 바꾼다.

2. pNode를 RR회전 한 것을 return한다.

 

- GetHeightDiff

  Balance Factor를 구하는 함수이다. lsh - rsh이므로 양수라면 왼쪽으로 치우친 것, 음수라면 오른쪽으로 치우친 것이다.

 

- Rebalance

  Balance Factor가 1보다 크다면 왼쪽으로 치우친 것이다. 왼쪽 자식 노드의 Balance Factor도 양수라면 LL상태이므로 LL회전, 음수라면 LR상태이므로 LR회전 한다.

  Balance Factor가 -1보다 작다면 오른쪽으로 치우친 것이다. 오른쪽 자식 노드의 Balance Factor도 음수라면 RR상태이므로 RR회전, 양수라면 RL상태이므로 RL회전 한다.