AVL Tree

AVL트리는 발명자의 이름인 Geory Adelson-Velsky and Evgeii LanDis을 따서 지어졌습니다.

 

스스로 균형을 맞추는 이진 탐색 트리여서 self-balancing binary search tree 라고 부르기도 합니다.

 

 

이진 트리에서, 데이터가 마치 연결리스트처럼 한줄로 쭉 나열되는 최악의 경우 트리의 이점을 살리지 못한다는 단점이 있었습니다

바로 아래의 그림처럼 말이죠.

 

 

이런 일이 발생하지 않기 위해서는 데이터를 추가할 때 한쪽으로 몰리지 않게 조절해주는 기능이 필요합니다.

 

이것을 가능하게 한 것이 바로 AVL 트리 입니다.

 

먼저 이진탐색트리의 코드부터 보겠습니다.

 

이진탐색트리 클래스)

연습을 위해 동일한 기능을 하는 함수를 재귀를 사용한 것과 사용하지 않은 것 둘다 구현했습니다.

template <typename K, typename V>
class BinarySearchTree {
 public:
  struct Item {
    K key = K();
    V value = V();
  };
  struct Node {
    Item item;

    Node* left = nullptr;
    Node* right = nullptr;
  };

  Item* RecurGet(const K& key) { return RecurGet(root_, key); }
  Item* RecurGet(Node* node, const K& key) {
    if (!node) return nullptr;

    if (key < node->item.key) return RecurGet(node->left, key);

    if (key > node->item.key) return RecurGet(node->right, key);

    return &node->item;
  }

  Item* IterGet(const K& key) { return IterGet(root_, key); }
  Item* IterGet(Node* node, const K& key) {
    if (!node) return nullptr;

    Node* temp = node;
    while (temp) {
      if (key < temp->item.key)
        temp = temp->left;
      else if (key > temp->item.key)
        temp = temp->right;
      else
        break;
    }
    return &temp->item;
  }

  void Insert(const Item& item) {
    std::cout << "Insert " << item.key << item.value << '\n';
    root_ = Insert(root_, item);
  }
  Node* Insert(Node* node, const Item& item) {
    if (!node) return new Node{item, nullptr, nullptr};

    if (node->item.key > item.key)
      node->left = Insert(node->left, item);
    else if (node->item.key < item.key)
      node->right = Insert(node->right, item);
    else
      node->item = item;

    return node;
  }
  
  void IterInsert(const Item& item) {
    std::cout << "IterInsert " << item.key << item.value << '\n';
    root_ = IterInsert(root_, item);
  }
  Node* IterInsert(Node* node, const Item& item) {
    if (!node) return new Node{item, nullptr, nullptr};

    Node* temp = node;
    Node* prev = node;
    int check = -1;
    while (temp) {
      if (item.key > temp->item.key) {
        prev = temp;
        temp = temp->right;
        check = 0;
      } else if (item.key < temp->item.key) {
        prev = temp;
        temp = temp->left;
        check = 1;
      }
    }

    if (check == 0) {
      prev->right = new Node{item, nullptr, nullptr};
    } else if (check == 1) {
      prev->left = new Node{item, nullptr, nullptr};
    }
    return node;
  }

  Node* MinKeyLeft(Node* node) {
    assert(node);
    while (node->left) {
      node = node->left;
    }
    return node;
  }

  void Remove(const K& key) {
    std::cout << "Remove  " << key << '\n';
    root_ = Remove(root_, key);
  }
  Node* Remove(Node* node, const K& key) {
    if (!node) return nullptr;

    if (key < node->item.key)
      node->left = Remove(node->left, key);
    else if (key > node->item.key)
      node->right = Remove(node->right, key);
    else {
      if (!node->left) {
        Node* temp = node->right;
        delete node;
        return temp;
      } else if (!node->right) {
        Node* temp = node->left;
        delete node;
        return temp;
      }

      Node* temp = MinKeyLeft(node->right);
      node->item = temp->item;
      node->right = Remove(node->right, temp->item.key);
    }
    return node;
  }

  int Height() { return Height(root_); }
  int Height(Node* node) {
    if (!node) return 0;
    return 1 + std::max(Height(node->left), Height(node->right));
  }

 protected:
  Node* root_ = nullptr;
};

 

코드의 삽입 부분인 Insert 함수를 보면 알 수 있듯이 균형을 맞추지 않고 데이터를 삽입하는 것을 확인할 수 있습니다.

 

이를 방지하는 AVL트리에 대해 알아봅시다.

 

 

AVL트리의 특징 ( 이진 탐색 트리에서 달라진 점 )

---

1. Balance라는 함수를 이용하여 균형을 맞춥니다.

 

- Balance = 왼쪽 트리의 높이 (height(node->left))  - 오른쪽 트리의 높이 (height(node->right))

int Balance(Node* node){
  if(node) return Height(node->left) - Height(node->right);
  eles return 0;
}

 

 

2. 균형이 맞지 않으면 균형을 맞춰줍니다. ( RotateRight , RotateLeft 함수 이용 )

 

-RotateRight 예시와 코드

 

부모 노드 (여기서는 Z) 의 왼쪽 자식을 temp로 지정.

오른쪽으로 회전한 뒤 temp를 새로운 부모노드로 return.

  Node* RotateRight(Node* parent) {
    Node* temp = parent->left;
    parent->left = temp->right;
    temp->right = parent;
    return temp;
  }

 

 

3. 균형이 맞추어져 있기에 삽입, 삭제, 탐색의 평균/최악 시간복잡도 모두 O(log N)입니다.

 

 

AVL Tree 코드)

 

이진탐색트리에 균형을 맞추는 기능만 추가된 것이므로 위의 BinarySearchTree.h 를 include 하고

 

이진탐색트리 클래스를 상속받아 그대로 사용. (균형 맞추는 기능만 추가)

#include "BinarySearchTree.h"

template <typename K, typename V>
class AVL : public BinarySearchTree<K, V> {
 public:
  using Base = BinarySearchTree<K, V>;
  using typename BinarySearchTree<K, V>::Item;
  using typename BinarySearchTree<K, V>::Node;

  int Height(Node* node) { return Base::Height(node); }

  int Balance(Node* node) {
    if (node)
      return Base::Height(node->left) - Base::Height(node->right);
    else
      return 0;
  }

  Node* RotateRight(Node* parent) {
    Node* temp = parent->left;
    parent->left = temp->right;
    temp->right = parent;
    return temp;
  }

  Node* RotateLeft(Node* parent) {
    Node* temp = parent->right;
    parent->right = temp->left;
    temp->left = parent;
    return temp;
  }

  void Insert(const Item& item) { root_ = Insert(root_, item); }
  Node* Insert(Node* node, const Item& item) {
    if (!node) return new Node{item, nullptr, nullptr};

    const auto& key = item.key;

    if (key < node->item.key)
      node->left = Insert(node->left, item);
    else if (key > node->item.key)
      node->right = Insert(node->right, item);
    else {
      node->item = item;
      return node;
    }

    int balance = Balance(node);

    if (balance == 0 || balance == 1 || balance == -1) return node;

    if (balance > 1 && Balance(node->left) >= 0) {
      return RotateRight(node);
    } else if (balance < -1 && Balance(node->right) <= 0) {
      return RotateLeft(node);
    } else if (balance > 1 && Balance(node->left) <= -1) {
      node->left = RotateLeft(node->left);
      return RotateRight(node);
    } else if (balance < -1 && Balance(node->right) >= 1) {
      node->right = RotateRight(node->right);
      return RotateLeft(node);
    }

    return node;
  }

  Node* MinKeyNode(Node* node) {
    while (node->left) node = node->left;
    return node;
  }

  void Remove(const K& key) { root_ = Remove(root_, key); }
  Node* Remove(Node* node, const K& key) {
    if (!node) return node;

    if (key < node->item.key) {
      node->left = Remove(node->left, key);
    } else if (key > node->item.key) {
      node->right = Remove(node->right, key);
    } else {
      if (!node->right) {
        Node* temp = node->left;
        delete node;
        return temp;
      } else if (!node->left) {
        Node* temp = node->right;
        delete node;
        return temp;
      }

      Node* temp = MinKeyNode(node->right);
      node->item = temp->item;
      node->right = Remove(node->right, temp->item.key);
    }

    int balance = Balance(node);
    if (balance == 0 || balance == 1 || balance == -1) return node;

    if (balance > 1 && Balance(node->left) >= 0)
      return RotateRight(node);
    else if (balance > -1 && Balance(node->right) <= 0)
      return RotateLeft(node);
    else if (balance > 1 && Balance(node->left) <= -1) {
      node->left = RotateLeft(node->left);
      return RotateRight(node);
    } else if (balance < -1 && Balance(node->right) >= 1) {
      node->right = RotateLeft(node->right);
      return RotateRight(node);
    }

    return node;
  }

 private:
  Node*& root_ = BinarySearchTree<K, V>::root_;
};

 

코드를 보시고 이해가 안되신다면 아래 사이트에 들어가 어떻게 회전하는지, 어떻게 삭제되는지 시각적으로 확인하실 수 있으니

꼭 한번 들어가보시는 것을 추천드립니다.

https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

AVL Tree Visualzation