12-1. 균형 잡힌 이진 탐색 트리 : AVL 트리의 이해

이진 탐색 트리의 문제점과 AVL 트리

• 이진 탐색 트리의 탐색 연산 : O(log2(n))
  

이진 탐색 트리는 균형이 맞지 않을수록 O(n)에 가까운 시간 복잡도를 보인다

이진 탐색 트리는 저장 순서에 따라 탐색의 성능에 큰 차이가 있다

균형 잡힌 이진 트리

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

자동으로 균형을 잡는 AVL 트리와 균형 인수(Balance Factor)

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

• 균형 인수의 절댓값이 크면 클수록 트리의 균형이 무너진 상태이다
• 균형 인수에 대해서 알면 트리의 리밸런싱 시기에 대해 알 수 있다
• 균형 인수의 절댓값이 2 이상인 경우 트리를 리밸런싱한다

리밸런싱이 필요한 첫 번째 상태와 LL회전

균형 인수가 +2인 상태 : LL 상태
LL 상태에서 불균형을 해소하기 위해 등장한 리밸런싱 방법 : LL 회전

ChangeLeftSubTree(cNode, pNode);

5가 저장된 노드에 T3를 양보하고 그 자리에 5를 넣는다

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

리밸런싱이 필요한 두 번째 상태와 RR회전

RR상태 : 오른쪽으로 길게 늘어진 모습
RR회전 : RR상태에서 리밸런싱을 위해 등장한 방법

• PN을 CN의 왼쪽 자식 노드가 되게 한다. -> 연산 1
• CN의 왼쪽 서브 트리를 PN의 오른쪽 서브 트리가 되게 한다. -> 연산 2

위 문장을 수행할 때

• ChangeRightSubTree(pNode, GetLeftSubTree(cNode)); -> 연산 2
• ChangeLeftSubTree(cNode, pNode); -> 연산 1

연산 1을 먼저하게 되면 CN의 왼쪽 서브 트리의 주소 값을 잃게 된다

리밸런싱이 필요한 세 번째 상태와 LR회전

LR 상태를 한 번의 회전으로 균형이 잡히는 LL상태나 RR상태로 일단 바꾼다
LR상태는 RR회전을 통해서 LL상태가 되게 한다

RR회전을 통해 부모와 자식 간의 관계를 바꿀 수 있음을 이용한다

일반화

리밸런싱이 필요한 네 번째 상태와 RL회전

• LR회전 부분적 RR회전에 이어서 LL회전을 진행한다
• RL회전 부분적 LL회전에 이어서 RR회전을 진행한다

LL회전도 부모와 자식 간의 관계를 바꿀 수 있다

일반화

12-2. 균형 잡힌 이진 탐색 트리 : AVL 트리의 구현

리밸런싱에 필요한 도구들의 정의: 균형을 이루고 있는가?

높이를 확인해서 그 차를 계산해야 불균형 여부를 확인할 수 있다

// 트리의 높이를 계산하여 반환
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;   //균형 인수 계산결과 반환
}

리밸런싱에 필요한 도구들의 정의 : LL회전, RR회전

• LL회전을 담당하는 함수

BTreeNode * RotateLL(BTreeNode * bst)   //LL회전을 담당하는 함수
{
    BTreeNode * pNode;  //parent node
    BTreeNode * cNode;  //child node
    
    // pNode와 cNode가 LL회전을 위해 적절한 위치를 가리키게 한다
    pNode = bst;
    cNode = GetLeftSubTree(pNode);
    
    //실제 LL회전을 담당하는 두 개의 문장
    ChangeLeftSubTree(pNode, GetRightSubTree(cNode));
    ChangeRightSubTree(cNode, pNode);
    
    //LL회전으로 인해서 변경된 루트 노드의 주소 값 반환
    return cNode;
}

• RR회전을 담당하는 함수

BTreeNode * RotateRR(BTreeNode * bst)   //RR회전을 담당하는 함수
{
    BTreeNode * pNode;  //parent node
    BTreeNode * cNode;  //child node
    
    //pNode와 cNode가 RR회전을 위해 적절한 위치를 가리키게 한다
    pNode = bst;
    cNode = GetRightSubTree(pNode);
    
    //실제 RR회전을 담당하는 두 개의 문장
    ChangeRightSubTree(pNode, GetLeftSubTree(cNode));
    ChangeLeftSubTree(cNode, pNode);
    
    //RR회전으로 인해서 변경된 루트 노드의 주소 값 반환
    return cNode;
}

리밸런싱에 필요한 도구들의 정의: LR회전, RL회전

• LR회전 : 부분적 RR회전에 이어서 LL회전을 진행한다

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회전
}

• RL회전 : 부분적 LL회전에 이어서 RR회전을 진행한다

BTreeNode * RotateRL(BTreeNode * bst)
{
    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); //RR회전
}

리밸런싱에 필요한 도구들의 정의: Rebalance 함수

BTreeNode * Rebalance(BTreeNode ** pRoot)
{
    int hDiff = GetHeightDiff(*pRoot);  //균형 인수 계산
    
    //균형 인수가 +2 이상이면 LL상태 또는 LR상태이다
    if(hDiff > 1)   //왼쪽 서브 트리 방향으로 높이가 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;
}