[자료구조] 자가균형이진탐색트리(AVL_tree)

사실 개쓸데없는 것이다

진짜 컴공이라서 하는거임

 

avl은 만든 사람이름임.

 

AVLTree가 이름만 이렇지 실제로는 그냥 (일반적인 이진탐색트리) + (rebalancing) 기능 이다.

이진탐색트리에서 좀 더 나아가 "균형잡힌" 이진트리를 만들기 위해 나온 것이다.

 

따라서 BinarySearchTree을 이해했으면 rebalancing하는 부분만 이해해주면 된다.

 

우선 AVLTree가 나온 이유는
그냥 BST일때는 다음과 같이 최악의 경우일때 탐색시간복잡도가 N으로 나오기 때문이다.

 

 

하지만 AVL은 이런 최악의 경우도 logN으로 만들 수 있다.

 

 

 

---

[LL RR LR RL]

 

리밸런싱 해야하는 경우의 수는 4가지가 있는데 여기서 설명하긴 귀찮아서 출처를 남겨둔다

윤성우 열혈 자료구조 470부터 읽어보면 됨.

LL RR LR RL이 있는데

LR RL은 LL RR을 재사용해서 구현하면 되서 그때 상황을 이해만 하면 된다.

 

아래는 LL RR 예시

 

 

---

[ AVL_tree.c ]

 

코드는 길지만 실제 봐야할 부분은 Rebalancing을 사용하는 부분이다.

어차피 일반 BinarySearchTree에서 Rebalancing하는 기능만 추가한 것이기 때문에

BSTInsert BSTRemove 작업은 일반 이진탐색트리와 다를게 없다!

 

Insert 할때마다 균형인수 구해서 rebalancing 해주고

Remove할때도 rebalancing을 해주면 된다

 

#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>

// === BinaryTree.c === //

typedef int BSTData;

typedef struct _bTreeNode
{
    BSTData data;
    struct _bTreeNode* left;
    struct _bTreeNode* right;
} BTreeNode;

BTreeNode* MakeBTreeNode(void)
{
    BTreeNode* nd = (BTreeNode*)malloc(sizeof(BTreeNode));

    nd->left = NULL;
    nd->right = NULL;
    return nd;
}

BSTData GetData(BTreeNode* bt) {return bt->data; }
void SetData(BTreeNode* bt, BSTData data) { bt->data = data;  }

BTreeNode* GetLeftSubTree(BTreeNode* bt) { return bt->left; }
BTreeNode* GetRightSubTree(BTreeNode* bt) { return bt->right; }

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

    main->left = sub;
}

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

    main->right = sub;
}

void RemoveLeftSubTree(BTreeNode* bt)
{
    BTreeNode* delNode = NULL;

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

void RemoveRightSubTree(BTreeNode* bt)
{
    BTreeNode* delNode = NULL;

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

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

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

// === AVLRebalance.c === //

BTreeNode* RotateLL(BTreeNode* bst)
{
    BTreeNode* pNode; // parent node
    BTreeNode* cNode; // child Node

    // pNode, cNode 가리키기
    pNode = bst;
    cNode = GetLeftSubTree(pNode);

    // real LL rotate
    ChangeLeftSubTree(pNode, GetRightSubTree(cNode));
    ChangeRightSubTree(cNode, pNode);

    //LL회전으로 cNode가 루트 노드가 됨! 그러므로 변경된 루트노드 주소값 반환
    return cNode;
}

BTreeNode* RotateRR(BTreeNode* bst)
{
    BTreeNode* pNode; // parent node
    BTreeNode* cNode; // child Node

    // pNode, cNode 가리키기
    pNode = bst;
    cNode = GetRightSubTree(pNode);

    // real RR rotate
    ChangeRightSubTree(pNode, GetLeftSubTree(cNode));
    ChangeLeftSubTree(cNode, pNode);

    //RR회전으로 cNode가 루트 노드가 됨! 그러므로 변경된 루트노드 주소값 반환
    return cNode;
}

BTreeNode* RotateLR(BTreeNode* bst) // LR회전을 담당하는 함수
{
    BTreeNode* pNode; // parent Node
    BTreeNode* cNode; // child Node

    //pNode, cNode 가 LR회전을 위해 적절한 위치를 가리키게한다.
    pNode = bst;
    cNode = GetLeftSubTree(pNode);

    //실제 LR회전을 담당하는 두 개의 문장
    ChangeLeftSubTree(pNode, RotateRR(cNode)); // 부분적 RR회전
    return RotateLL(pNode); // LL회전
}

BTreeNode* RotateRL(BTreeNode* bst) // LR회전을 담당하는 함수
{
    BTreeNode* pNode; // parent Node
    BTreeNode* cNode; // child Node

    //pNode, cNode 가 RL회전을 위해 적절한 위치를 가리키게한다.
    pNode = bst;
    cNode = GetRightSubTree(pNode);

    //실제 RL회전을 담당하는 두 개의 문장
    ChangeRightSubTree(pNode, RotateLL(cNode)); // 부분적 LL회전
    return RotateRR(pNode); // LL회전
}

int GetHeight(BTreeNode* bst)
{
    int leftH; // left Height
    int rightH; // right Height

    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(BTreeNode* bst)
{
    int lsh; // left sub tree Height
    int rsh; // right sub tree height

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

BTreeNode* Rebalance(BTreeNode** pRoot)
{
    int hDiff = GetHeightDiff(*pRoot); // 균형 인수 계산

    //균형 인수가 +2 이상이면 LL/LR 상태이다.
    if (hDiff > 1) // +2이상이면(왼쪽 서브 트리 방향으로 높이가 2 이상 크다면)
    {
        if (GetHeightDiff(GetLeftSubTree(*pRoot)) > 0)
            *pRoot = RotateLL(*pRoot);
        else
            *pRoot = RotateLR(*pRoot);
    }
    //균형 인수가 -2 이하이면 RR/RL 상태이다.
    if (hDiff < -1) // 오른쪽 서브 트리 방향으로 2 이상 크다면,
    {
        if (GetHeightDiff(GetRightSubTree(*pRoot)) < 0)
            *pRoot = RotateRR(*pRoot);
        else
            *pRoot = RotateRL(*pRoot);
    }

    return *pRoot;
}

// BinarySearchTree3

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

BTreeNode* BSTInsert(BTreeNode** pRoot, BSTData data)
{
    if (*pRoot == NULL)
    {
        *pRoot = MakeBTreeNode();
        SetData(*pRoot, data);
    }
    else if (data < GetData(*pRoot))
    {
        BSTInsert(&((*pRoot)->left), data);
        *pRoot = Rebalance(pRoot);
    }
    else if (data > GetData(*pRoot))
    {
        BSTInsert(&((*pRoot)->right), data);
        *pRoot = Rebalance(pRoot);
    }
    else
    {
        return NULL; // 키의 중복은 허락하지 않는다( data == GetData(*pRoot)
    }
    return *pRoot;
}

BTreeNode* BSTSearch(BTreeNode* bst, BSTData target)
{
    BTreeNode* cNode = bst;    // current node
    BSTData 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;
}

BTreeNode* BSTRemove(BTreeNode** pRoot, BSTData target)
{

    // 얘가 ㅈㄴ 중요한 놈임
    // rootNode가 삭제되면 굉장히 골치아파지므로 rootNode의 DummyNode를 임시로 만들어놓는다.
    BTreeNode* pVRoot = MakeBTreeNode();

    BTreeNode* pNode = pVRoot;    // parent node
    BTreeNode* cNode = *pRoot;    // current node
    BTreeNode* dNode;    // delete node

    // 임시 DummyNode로 바꿔놓는다
    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;

    // leaf node
    if (GetLeftSubTree(dNode) == NULL && GetRightSubTree(dNode) == NULL)
    {
        if (GetLeftSubTree(pNode) == dNode)
            RemoveLeftSubTree(pNode);
        else
            RemoveRightSubTree(pNode);
    }
    // only one child
    else if (GetLeftSubTree(dNode) == NULL || GetRightSubTree(dNode) == NULL)
    {
        BTreeNode* dcNode;    // delete node

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

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

    // two child
    else
    {
        /*
        // 왼쪽 자식 중 제일 오른쪽에 있는 놈으로 대체
        BTreeNode* mNode = GetLeftSubTree(dNode);
        BTreeNode* mpNode = dNode;
        int delData;

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

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

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

        dNode = mNode;
        SetData(dNode, delData);
        */
        
        //오른쪽 자식 중 제일 왼쪽에 있는 놈으로 대체
        BTreeNode* mNode = GetRightSubTree(dNode);    // mininum node
        BTreeNode* mpNode = dNode;    // mininum node
        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 InorderTraverse(BTreeNode* bst) {
    if (bst == NULL) return;

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

int main()
{
    // ROOT NODE
    BTreeNode* avlRoot;
    BSTMakeAndInit(&avlRoot);

    char ch;
    int data;

    scanf("%c", &ch);

    while (ch != 'q') {

        if (ch == 'i') {
            scanf("%d", &data);
            BSTInsert(&avlRoot, data);
        }
        else if (ch == 'd') {
            scanf("%d", &data);
            if (BSTSearch(avlRoot, data)!=NULL) {
                BSTRemove(&avlRoot, data);
                printf("%d", data);
            }
            else { printf("X"); }
        }
        else if (ch == 's') {
            scanf("%d", &data);

            if (BSTSearch(avlRoot, data)) printf("%d", data);
            else printf("X");
        }
        else if (ch == 'p') {
            InorderTraverse(avlRoot);
        }

        printf("\n");

        scanf("%c", &ch);
    }

    return 0;
}