자료구조 12강 AVL 트리의 소스 코드

 

이진 탐색 트리 문제점

이진 탐색 트리의 탐색 연산은 O(log₂n)의 시간 복잡도 - 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드도 두 배씩 증가.

저장 순서에 따라 탐색의 성능에 큰 차이를 보이는 것이 이진 탐색 트리의 단점.

이러한 단점을 해결한 트리 - 균형 잡힌 이진 트리

1. AVL 트리

2. 2-3 트리

3. 2-3-4 트리

4. Red - Black 트리

5. B 트리

AVL 트리

노드가 추가될 때, 그리고 삭제될 때 트리의 균형상태를 파악해서 스스로 그 구조를 변경하여 균형을 잡는 트리.

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

코드 구현

//
//  AVLRebalance.h
//  AVLTree
//

#ifndef AVLRebalance_h
#define AVLRebalance_h

#include "BinaryTree3.h"

// 트리의 균형을 잡는다.
BTreeNode * Rebalance(BTreeNode ** pRoot);

#endif /* AVLRebalance_h */

//  AVLRebalance.c

#include <stdio.h>
#include "BinaryTree3.h"

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;
}

// AVLTreeMain.c
#include <stdio.h>
#include "BinaryTree3.h" // 트리구조 확인을 위해
#include "BinarySearchTree3.h"

int main(void)
{
    BTreeNode * avlRoot;
    BTreeNode * clNode; // current left Node
    BTreeNode * crNode; // current right Node
    
    BTreeNode * clNode2;
    BTreeNode * crNode2;

    BTreeNode * clNode3;
    BTreeNode * crNode3;
    
    BSTMakeAndInit(&avlRoot);
    
    BSTInsert(&avlRoot, 1);
    BSTInsert(&avlRoot, 2);
    BSTInsert(&avlRoot, 3);
    BSTInsert(&avlRoot, 4);
    BSTInsert(&avlRoot, 5);
    BSTInsert(&avlRoot, 6);
    BSTInsert(&avlRoot, 7);
    BSTInsert(&avlRoot, 8);
    BSTInsert(&avlRoot, 9);
    
    printf("루트 노드 : %d \n",GetData(avlRoot)); //4
    
    clNode = GetLeftSubTree(avlRoot); // 2
    crNode = GetRightSubTree(avlRoot); // 6
    printf("왼쪽 1 : %d, 오른쪽 1 : %d \n",GetData(clNode),GetData(crNode));
    
    clNode2 = GetLeftSubTree(clNode); // 1, 2의 왼쪽 노드
    crNode2 = GetRightSubTree(clNode);// 3, 2의 오른쪽 노드
    printf("왼쪽 2 : %d, 오른쪽 2 : %d \n",GetData(clNode2),GetData(crNode2));
    
    clNode2 = GetLeftSubTree(crNode); // 5, 6의 왼쪽 노드
    crNode2 = GetRightSubTree(crNode); // 8, 6의 오른쪽 노드
    printf("왼쪽 3 : %d, 오른쪽 3 : %d \n",GetData(clNode2),GetData(crNode2));
    
    clNode3 = GetLeftSubTree(crNode2); //7, 8의 왼쪽 노드
    crNode3 = GetRightSubTree(crNode2); // 9, 8의 오른쪽 노드
    printf("왼쪽 4 : %d, 오른쪽 4 : %d \n",GetData(clNode3),GetData(crNode3));
    
    return 0;
}

출력 결과