AVL 트리를 이해해보자

트리의 탐색연산은 O(log밑2 n)의 시간복잡도를 가진다. 하지만 저장순서가 예를 들어 오름차순일 경우 탐색하는 O(n)에 가까운 시간복잡도를 가진다. 이런 트리의 균형을 잡아주는 방법에는 다음과 같은 것이 있다.

AVL 트리
2-3 트리
2-3-4 트리
Red-Black 트리
B 트리

위의 이진 탐색트리가 자동으로 균형을 잡아주는 방법 중 AVL 트리에 대해 알아보자.

균형 인수

AVL 트리는 균형의 정도를 표현하기 위해 균형인수를 사용한다.
균형인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이

균형인수의 절대 값이 클 수록 트리의 균형이 무너진 것이다. 이후에는 균형인수 2이상인 경우 리밸런싱을 하는 과정을 보이겠다.

AVL 트리의 리밸런싱

AVL 트리가 리밸런싱을 하는 경우는 4 가지 이다.

LL (왼쪽으로 서브트리가 늘어난 상태)
RR (오른쪽으로 서브트리가 늘어난 상태)
LR
RL

LR은 왼쪽으로 서브트리가 있고 이 서브트리의 오른쪽에 서브트리가 붙은 것이다. RL 은 반대다. 리밸런싱 기준은 루트노드의 균형인수 이다.

LL

루트노드를 자식노드의 오른쪽 서브트리로 붙이면 된다. 오른쪽으로 회전시키는 모양이다. 자식노드에 오른쪽 서브트리가 있을 수 있으므로 오른쪽 서브트리는 루트노드의 왼쪽 서브트리에 연결시킨다.

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

RR

루트노드를 자식노드의 왼쪽 서브트리로 붙이면 된다. 왼쪽으로 회전시키는 모양이다. 자식노드에 왼쪽 서브트리가 있을 수 있다. 이 왼쪽 서브트리를 루트 노드의 오른쪽 서브트리로 만든다.

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

루트 노드를 먼저 자식 노드에 붙이면 자식 노드의 서브트리의 주소를 잃기 때문에 반대로 한다.

LR

LL 상태로 만든다음 LL 회전 시키면 된다. LL 상태를 만드는 방법은 자식 노드를 RR 상태로 보고 회전시키면 된다. 순서는 자식노드를 RR 회전, 루트 노드를 LL 회전.

RRRotate(cNode);
LLRotate(pRoot);

RL

RR 상태로 만든 다음 RR 회전을 시키면 된다. RR 상태를 만드는 방법은 자식노드를 LL 회전 시키면된다.

LLRotate(cNode);
RRRotate(pRoot);

실제 구현

하나씩 실제로 구현해보자 먼저 트리의 높이를 구해보자

트리의 높이

// 트리의 높이는 가장 깊은 단말노드까지 내려가야 구할 수 있다.
// 왼쪽, 오른쪽 서브 트리를 모두 내려간뒤 더 큰 값을 높이로 정한다.
int GetHeight(BTreeNode* bst)
{
    int leftH = 0;
    int rightH = 0;

    if(bst == nullptr)
        return 0;
    
    leftH = GetHeight(GetLeftSubTree(bst));
    rightH = GetHeight(GetRightSubTree(bst));

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

균형인수

트리의 높이를 이용하여 균형인수를 구하자. 균형인수는 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이.

int GetHeightDiff(BTreeNode* bst)
{
    if(bst == nullptr)
        return 0;
    
    int leftSubTreeHeihgt = GetHeight(GetLeftSubTree(bst));
    int rightSubTreeHeight = GetHeight(GetRightSubTree(bst));

    return leftSubTreeHeight - rightSubTreeHeight;
}

LL 부터 RL 까지 구현

BTreeNode* LLRotate(BTreeNode* bst)
{
    BTreeNode* pNode = bst;
    BTreeNode* cNode = GetLeftSubTree(bst);

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

    // 회전 후, 루트 노드가 변경되는데 추후 로직에서 이를 반영하려면 루트노드를 리턴해야 한다.
    return cNode;
}

BTreeNode* RRRotate(BTreeNode* bst)
{
    BTreeNode* pNode = bst;
    BTreeNode* cNode = GetRightSubTree(bst);

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

    return cNode;
}

BTreeNode* LRRotate(BTreeNode* bst)
{
    BTreeNode* pNode = bst;
    BTreeNode* cNode = GetLeftSubTree(bst);

    ChangeLeftSubTree(pNode, RRRotate(cNode));

    return LLRotate(pNode);
}

BTreeNode* RLRotate(BTreeNode* bst)
{
    BTreeNode* pNode = bst;
    BTreeNode* cNode = GetRightSubTree(bst);

    ChangeRightSubTree(pNode, LLRotate(cNode));

    return RRRotate(pNode);
}

// 이들을 알맞은 순서, 시기에 호출하는 함수
BTreeNode* Rebalance(BTreeNode** pRoot)
{
    BTreeNode* rRoot= nullptr;

    if(GetHeightDiff(*pRoot) > 1)
    {
        if( GetHeightDiff(GetLeftSubTree(*pRoot)) >0 )
            rRoot = LLRotate(*pRoot);
        else
            rRoot = LRRotate(*pRoot);
    }
    else
    {
        if( GetHeightDiff(GetRightSubTree(*pRoot)) < 0 )
            rRoot = RRRotate(*pRoot);
        else
            rRoot = RLRotate(*pRoot);
    }

    return rRoot;
}