[자료구조/C언어] AVL Tree

1. AVL Tree의 정의

• 스스로 균형을 잡는 Binary Search Tree
• Balance(X) = -Height(LeftSubtree(X)) + Height(RightSubTree(X))

 

2. AVL Tree의 예시

AVL Tree 예시

3. Rebalance

Rotation과 더불어 AVL Tree의 핵심 중 하나이다. GetBalancingFa

ctor 함수로 통해 Tree의 높낮이를 계산 후 불균형이라면 어느 부분에서 불균형인지 판단 후 회전을 진행한다.

Tree의 불균형

Rebalance

 

BSTNode* Rebalance(BSTNode* root) {
	int factor = GetBalancingFactor(root);
    if (factor < -1) {
    	if (GetBalancingFactor((root)->left_child < 0)	// Left Subtree의 left child에 노드가 삽입되어 불균형 생긴 경우
        	root = LLrotation(root);
        else root = LRrotation(root);	// Left Subtree의 right child에 노드가 삽입되어 불균형 생긴 경우
    } else if (facotr > 1) {
    	if (GetBalancingFactior((root)->right_child > 0) // Right Subtree의 right child에 노드가 삽입되어 불균형 생긴 경우
        	root = RRrotation(root);
        else root = RLrotation(root);	// Right Subtree의 left child에 노드가 삽입되어 불균형 생긴 경우
    }
    return root;
}

int GetBalancingFactor(BSTNode* root) {
	if (root == NULL) return 0;
    return GetHeight(root->right_child) - GetHeight(root->left_child);
}

3. Rotation

사실상 AVL Tree의 핵심이라고 볼 수 있다. balance 균형을 맞추기 위해 AVL Tree는 Rotation(회전)을 수행한다.

3.1 Single Rotation

3.1.2 LL Rotation

• Left Subtree의 Left Child에 노드가 삽입되어 트리의 균형을 잃어버렸을 때 쓰는 회전
• 시계방향으로 회전한다.
•  

  

  LL Rotation

BSTNode* LLrotation(BSTNode* parent) {
	BSTNode* child = parent->left_child;
    parent->left_child = child->right_child;
    child->right_child = parent;
    return child;
}

 

3.1.2 RR Rotation

• Right Subtree의 Right Child에 노드가 삽입되어 트리의 균형을 잃어버렸을 때 쓰는 회전
• 반시계방향으로 회전한다.

• 

  RR Rotation

BSTNode* RRrotation(BSTNode* parent) {
	BSTNode* child = parent->right_child;
    parent->right_child = child->left_child;
    child->left_child = parent;
    return child;
}

3.2 Double Rotation

3.3 LR Rotation

• Left Subtree의 Right Child에 노드가 삽입되어 트리의 균형을 잃어버렸을 때 쓰는 회전
• Left Subtree 자체를 RR rotation 한 후 전체 Tree를 LL rotation을 하면 된다.
•  

  

  LR Rotation

#include LRrotation(BSTNode* parent) {
	BSTNode* child = parent->left_child;
    parent->left_child = RRrotation(child);
    return LLrotation(parent);
}

3.4 RL Rotation

• Right Subtree의 Left Child에 노드가 삽입되어 트리의 균형을 잃어버렸을 때 쓰는 회전
• Right Subtree 자체를 LL rotation 한 후 전체 Tree를 RR rotation을 하면 된다.
•  

BSTNode* RLrotation(BSTNode* parent) {
	BSTNode* child = parent->right_child;
    parent->right_child = LLrotation(child);
    return RRrotation(parent);
}

 

3. AVL Tree 코드

#include <stdio.h>

typedef int Key;

typedef struct _BSTNode {
  Key key;
  struct _BSTNode *left_child;
  struct _BSTNode *right_child;
} BSTNode;

// Create a new node.
BSTNode *CreateNode(Key key);

// Destroy a node.
void DestoryNode(BSTNode *node);

// Connect the root to a left child node.
void CreateLeftSubtree(BSTNode *root, Key key);

// Connect the root to ta right child node.
void CreateRightSubtree(BSTNode *root, Key key);

// Search an item in BST.
BSTNode *Search(BSTNode *root, Key key);

// Insert an item to BST.
BSTNode *Insert(BSTNode *root, Key key);

// Return the balancing factor.
int GetBalancingFactor(BSTNode *root);

// Return the height.
int GetHeight(BSTNode *root);

// Perform LL rotation.
BSTNode *LLrotation(BSTNode *parent);

// Perform RR rotation.
BSTNode *RRrotation(BSTNode *parent);

// Perform LR rotation.
BSTNode *LRrotation(BSTNode *parent);

// Perform RL rotation.
BSTNode *RLrotation(BSTNode *parent);

// Search : BST와 같음.
BSTNode *Search(BSTNode *root, Key key) {
  if (root == NULL || root->key == key)
    return root;
  else if (root->key > key)
    return Search(root->left_child, key);
  else
    return Search(root->right_child, key);
}

/* Iterative Version
BSTNode* Search(BSTNode* root, Key key) {
  BSTNode* cur = root;
  while (cur != NULL) {
    if (cur->key == key) break;
    else if (root->key > key) cur = cur->left_child;
    else cur = cur->right_child;
  }
  return cur;
}
*/

// Insertion : BST와 유사 (BST Insertion에 Rebalace 추가!)
BSTNode *Insert(BSTNode *root, Key key) {
  if (root == NULL)
    return CreateNode(key);
  if (key < root->key) { // key가 root->key보다 작으면 왼쪽으로 가서 삽입
    root->left_child = Insert(root->left_child, key);
    root = Rebalance(root);
    return root;
  } else if (key > root->key) {
    root->right_child = Insert(root->right_child, key);
    root = Rebalance(root);
    return root;
  } else
    exit(1);
}

BSTNode *Rebalance(BSTNode *root) {
  int factor = GetBalancingFactor(root); // -HL + HR 을 factor에 저장
  if (factor < -1) {                     // Left Subtree로 치우쳐진 경우
    if (GetBalancingFactor((root)->left_child) < 0) // Left Child에 삽입된 경우
      root = LLrotation(root);
    else // Right Child에 삽입된 경우
      root = LRrotation(root);
  } else if (factor > 1) {
    if (GetBalancingFactor((root)->right_child > 0))
      root = RRrotation(root);
    else
      root = RLrotation(root);
  }
  return root;
}

int GetBalancingFactor(BSTNode *root) {
  if (root == NULL)
    return 0;
  return (GetHeight(root->right_child) - GetHeight(root->left_child));
}

// LL rotation : Left Subtree의 left child로 들어가서 밸런스 파괴되었을
// 때(시계방향)
BSTNode *LLrotation(BSTNode *parent) {
  BSTNode *child = parent->left_child;
  parent->left_child = child->right_child;
  child->right_child = parent;
  return child;
}
// RR rotation : Right Subtree의 right child로 들어가서 밸런스 파괴되었을 때
BSTNode *RRrotation(BSTNode *parent) {
  BSTNode *child = parent->right_child;
  parent->right_child = child->left_child;
  child->left_child = parent;
  return child;
}

// LR rotation : Left Subtree의 right child로 들어가서 밸런스 파괴되었을 때
// Left Subtree를 RR회전 후 전체 Tree를 LL 회전하면 된다.
BSTNode *LRrotation(BSTNode *parent) {
  BSTNode *child = parent->left_child;
  parent->left_child = RRrotation(child);
  return LLrotation(parent);
}

// RL rotation : Right Subtree의 Left child로 들어가서 밸런스 파괴되었을 때
// Right Subtree를 LL회전 후 전체 Tree를 RR 회전하면 된다.
BSTNode *RLrotation(BSTNode *parent) {
  BSTNode *child = parent->right_child;
  parent->right_child = LLrotation(child);
  return RRrotation(parent);
}

// Remove : BST와 코드는 같다. 그러나 삭제 후, 트리의 균형이 맞는지 안맞는지
// check해야 한다. Recursive Version
BSTNode *Remove(BSTNode *root, Key key) {
  if (root == NULL)
    return NULL;

  if (key < root->key) // The key is at the left subtree.
    root->left_child = Remove(root->left_child, key);
  else if (key > root->key) // The key is at the right subtree.
    root->right_child = Remove(root->right_child, key);
  else {
    // The root is the node to be removed.
    BSTNode *cur = root;
    // Case 1: No child node
    if (root->left_child == NULL && root->right_child == NULL) {
      DestoryNode(cur);
    } // Case 2: One child node
    else if (root->left_child == NULL || root->right_child == NULL) {
      if (root->left_child != NULL) {
        // Replace the root with its child node.
        root = root->left_child;
        DestoryNode(cur);
      } else {
        root = root->right_child;
        DestoryNode(cur);
      }
    } // Case 3: The root has two child nodes.
    else {
      // Find the inorder successor of the root.(Right Subtree 중 가장 작은 값을
      // 찾는다.)
      cur = cur->right_child;
      while (cur->left_child != NULL)
        cur = cur->left_child;

      // Copy the successor to the root for deleting the root.
      root->key = cur->key; // 트리의 root값과 Right Subtree의 가장 작은 값을
                            // 서로 맞바꾼다.
      root->right_child = Remove(root->right_child, cur->key);
    }
  }
  return root;
}

/*
// Iterative version
BSTNode *Remove(BSTNode *root, Key key) {
  BSTNode *cur = root, *parent = NULL;

  // Find the current node and its parent node.
  while (cur != NULL && cur->key != key) {
    parent = cur; // Find the parent node for update.
    if (cur->key > key)
      cur = cur->left_child;
    else
      cur = cur->right_child;
  }

  if (cur == NULL)
    exit(1);

  // Case1: No child node.
  if (cur->left_child == NULL && cur->right_child == NULL) {
    if (parent != NULL) {
      // Remove the current node depending on its position.
      if (parent->left_child == cur)
        parent->left_child = NULL;
      else
        parent->right_child = NULL;
    } else
      root = NULL; // The current node is the root.
  }

  // Case 2: one child node
  else if (cur->left_child == NULL || cur->right_child == NULL) {
    BSTNode *child;

    // Find the child node.
    if (cur->left_child != NULL)
      child = cur->left_child;
    else
      child = cur->right_child;

    if (parent != NULL) { // Update the parent node.
      if (parent->left_child == cur)
        parent->left_child = child;
      else
        parent->right_child = child;
    } else {
      // Because the root is removed, replace it with its child.
      root = child; // 삭제하려던 애가 root 하나밖에 안남았을 때
    }
  } // Case 3: two child nodes
  else {
    BSTNode *succ_parent = cur, *succ = cur->right_child;
    // Find the successor (left-most node of the current node.)
    while (succ->left_child != NULL) {
      succ_parent = succ;
      succ = succ->left_child;
    }
    // If the successor has a child node, connect the child node to its parent
    // node.
    if (succ_parent->right_child == succ)
      // THe successor is the direct right child nodes.
      succ_parent->right_child = succ->right_child;
    else
      succ_parent->left_child = succ->right_child;
    // Copy the key of the successor to that of the current node.
    cur->key = succ->key;
    cur = succ; // Change the current node to remove the successor.
  }
  DestoryNode(cur);
  return root;
}
*/

4. 시간복잡도

검색, 삽입 및 삭제 작업은 O( ℎ )에 의해 제한된다. 여기서 ℎ는 AVL 트리의 높이인 log_2 ( n )이다. (n은 AVL Tree의 노드 개수)

Algorithm	Average case	Worst case
Searching	O(log n)	O(log n)
Insertion	O(log n)	O(log n)
Deletion	O(log n)	O(log n)