AVL트리

자료구조

AVL트리

NYoun 2021. 1. 17. 13:27

AVL트리

AVL트리는 균형이 갖춰진 이진트리를 의미한다.

완전이진트리는 검색에 있어서 O(logN)의 시간복잡도를 유지할 수 있다.

AVL트리는 간단한 구현과정으로 특정 이진트리가 완전 이진트리에 가까운 형태를 유지하도록 해준다.

AVL트리는 균형인수(Balance Facter)라는 개념을 이용한다.

균형인수는 왼쪽자식높이에서 오른쪽자식높이를 뺀 절대값을 의미한다.

이 균형인수가 ±1 이하인 경우가 AVL트리이다.

균형인수가 범위를 벗어난 경우에는 회전(rotation)을 통해 재구성해야 한다.

AVL트리의 각 노드는 균형인수를 계산하기 위한 목적으로 자신의 높이값을 갖는다.

AVL트리는 4가지 형식에 의해 균형이 깨질 수 있다. 균형인수가 깨지는 노드를 X라고 했을 때

4가지 형식은 다음과 같다.

LL형식 : X의 왼쪽자식노드의 왼쪽에 삽입하는 경우

RR형식 : X의 오른쪽자식노드의 오른쪽에 삽입하는 경우

LR형식 : X의 왼쪽자식노드의 오른쪽에 삽입하는 경우

RL형식 : X의 오른쪽자식노드의 왼쪽에 삽입하는 경우

AVL트리의 균형잡기

AVL트리의 균형잡기는 각 노드가 삽입될 때마다 수행되어야 한다. 삽입과정에 소요되는 시간 복잡도는 O(logN)이다.

따라서 각 트리의 균형잡기는 삽입시에 거치는 모든 노드에 대하여 수행된다는 점에서 O(1)의 시간 복잡도를

만족해야 한다.

AVL트리의 삽입

일반적인 이진탐색트리와 과정이 흡사하다. 다만 삽입시에 거치는 모든 노드에 대하여 균형잡기를 수행해줘야

한다는 특징이 있다.

AVL트리의 출력

삽입되는 과정을 면밀히 살펴보는것이 중요하므로 트리 구졸르 적절히 보여줄 수 있는 방식으로 출력해야 한다.

일반적으로 트리의 너비가 높이보다 크다는 점에서 세로방향으로 출력하는 함수를 구현할 수 있다.

예제코드

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

int getMax(int a, int b){
  if(a > b) return a;
  return b;
}

typedef struct{
  int data;
  int height; //높이를 저장해야 시간 복잡도를 보장할 수 있다.
  struct Node* leftChild;
  struct Node* rightChild;
} Node;

int getHeight(Node* node){ //현재 특정한 루트노드에서의 높이값을 반환
  if(node == NULL) return 0; //노드가 없으니까 0을 반환
  return node->height;
}

void setHeight(Node* node){
  node->height = getMax(getHeight(node->leftChild), getHeight(node->rightChild)) + 1;
  //왼쪽, 오른쪽 중 더 큰 값에 + 1을 해준다.
}

int getDifference(Node* node){ //균형인수를 구하는 함수
  if(node == NULL) return 0;
  Node* leftChild = node->leftChild;
  Node* rightChild = node->rightChild;
  return getHeight(leftChild) - getHeight(rightChild);
}

Node* rotateLL(Node* node){
  Node* leftChild = node->leftChild; 
  //node의 왼쪽 자식노드를 leftChild로 정의
  
  node->leftChild = leftChild->rightChild; 
  //node의 왼쪽 자식노드를 leftChild로 정의한 노드의 오른쪽 자식노드로 변경
  
  leftChild->rightChild = node;
  //leftChild로 정의한 노드의 오른쪽 자식노드를 node로 변경.
  
  setHeight(node); //회전이후에 높이를 다시 계산
  return leftChild;
}

Node* rotateRR(Node* node){
  Node* rightChild = node->rightChild;
  node->rightChild = rightChild->leftChild;
  rightChild->leftChild = node;
  setHeight(node);
  return rightChild;
}

Node* rotateLR(Node* node){
  Node* leftChild = node->leftChild;
  node->leftChild = rotateRR(leftChild);
  setHeight(node->leftChild);
  return rotateLL(node);
}

Node* rotateRL(Node* node){
  Node* rightChild = node->rightChild;
  node->rightChild = rotateLL(rightChild);
  setHeight(node->rightChild);
  return rotateRR(node);
}

Node* balance(Node* node){ //균형잡는 함수
  int difference = getdifference(node); //균형인수
  if(difference >= 2){ //균형인수가 2이상인 경우에는 LL인지 LR인지 확인 후 처리 
    if(getDifference(node->leftChild) >= 1){
      node = rotateLL(node);
    }
    else {
      node = rotateLR(node);
    }
  }
  else if(difference <= -2){ //-2이하인 경우 RR인지 RL인지 확인 후 처리
    if(getDifference(node->rightChild) <= -1){
      node = rotateRR(node);
    }
    else{
      node = rotateRL(node);
    }
  }
  setHeight(node); //회전 이후에 높이를 다시 계산
  return node;
}

Node* insertNode(Node* node, int data){ //삽입함수
  if(!node){
    node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->height = 1; //초기 높이값을 1로 설정
    node->leftChild = node->rightChild = NULL;
  }
  else if(data < node->data){
    node->leftChild = insertNode(node->leftChild, data);
    node = balance(node);
  }
  else if(data > node->data){
    node->rightChild = insertNode(node->rightChild, data);
    node = balance(node);
  }
  else{
    printf("데이터 중복 발생.\n");
  }
  return node;
}

Node* root = NULL;

void display(Node* node, int level) { //출력함수
  if(node != NULL){
    display(node->rightChild, level + 1){ //가장 오른쪽 노드로 이동해서 오른쪽부터 출력하도록
    printf("\n");
    
    if(node == root){ //루트를 발견했을 때
      printf("Root : ");
    }
    
    for(int i = 0; i < level && node != root; i++){
      printf("        ");
      //가장 오른쪽으로 들어간 level값, 해당 노드의 레벨만큼 띄어쓰기를 해줌으로써
      //가장 깊은 노드가 가장 오른쪽에 출력되도록 한다.
    }
    
    printf("%d(%d)", node->data, getHeight(node));//해당값을 출력하고
    display(node->leftChild, level + 1);
    //왼쪽으로 재귀적으로 호출해서 기존 트리구조의 오른쪽 자식노드부터 출력하고
    //나중에 왼쪽자식노드가 출력될 수 있도록 한다.
  }
}

int main(void){
  root = insertNode(root, 7);
  root = insertNode(root, 6);
  root = insertNode(root, 5);
  root = insertNode(root, 3);
  root = insertNode(root, 1);
  root = insertNode(root, 9);
  root = insertNode(root, 8);
  root = insertNode(root, 12);
  root = insertNode(root, 16);
  root = insertNode(root, 18);
  root = insertNode(root, 23);
  root = insertNode(root, 21);
  root = insertNode(root, 14);
  root = insertNode(root, 15);
  root = insertNode(root, 19);
  
  display(root, 1);
  printf("\n");
  system("pause);
}

                                23(1)
                        21(2)
                                19(1)
                18(3)
                                16(1)
                        15(2)
                                14(1)
Root : 12(4)
                                9(1)
                        8(2)
                                7(1)
                6(3)
                                5(1)
                        3(2)
                                1(1)

실행하면 이렇게 출력된다.

처음 강의 들으면서 LL, RR, LR, RL 회전 그림을 보면서도 이해가 하나도 안되서 여기저기 찾아보고 코드 뜯어보면서

이해했다.

LL회전