AVL

摘自 https://github.com/weberd6/balancedBinarySearchTrees

AVLTree.hxx:

#ifndef AVL_TREE
#define AVL_TREE

#include <iostream>
#include <algorithm>
#include <queue>

namespace NSAVLTree {

using std::max;
using std::cout;
using std::endl;
using std::queue;

template <typename T>
struct AVLNode {
  AVLNode(T key) : key_(key) {}
  T key_;
  AVLNode* left_child_ = nullptr;
  AVLNode* right_child_ = nullptr;
  int height_ = 1;
};

template <typename T>
class AVLTree {
private:
  AVLNode<T>* root_ = nullptr;

protected:
  int get_balance_factor(AVLNode<T>* N);
  int height(AVLNode<T>* N);
  AVLNode<T>* insert(AVLNode<T>* N, const T key);
  AVLNode<T>* inorder_successor(AVLNode<T>* N);
  AVLNode<T>* remove(AVLNode<T>* N, const T key);
  AVLNode<T>* rotate_right(AVLNode<T>* P);
  AVLNode<T>* rotate_left(AVLNode<T>* P);

  void preorder_print(AVLNode<T>* N);
  void inorder_print(AVLNode<T>* N);
  void postorder_print(AVLNode<T>* N);
  void _bfs_print();

public:
  void insert (const T key);
  void remove (const T key);
  T pop ();

  void preorder_print();
  void inorder_print();
  void postorder_print();
  void bfs_print();
};

#include "AVLTree.tcc"

} // NSAVLTree

#endif // AVL_TREE

AVLTree.tcc:

// Protected
template <typename T>
int AVLTree<T>::height(AVLNode<T>* N) {
  if (N == nullptr) {
    return 0;
  }
  return N->height_;
}

template <typename T>
int AVLTree<T>::get_balance_factor(AVLNode<T>* N) {
  if (N == nullptr) {
    return 0;
  }
  return height(N->left_child_) - height(N->right_child_);
}

template <typename T>
AVLNode<T>* AVLTree<T>::insert(AVLNode<T>* N, const T key) {

  if (N == nullptr) {
    return new AVLNode<T>(key);
  }

  if (key < N->key_) {
    N->left_child_  = insert(N->left_child_, key);
  } else {
    N->right_child_ = insert(N->right_child_, key);
  }

  N->height_ = max(height(N->left_child_), height(N->right_child_)) + 1;

  int balance = get_balance_factor(N);

  // Left Left Case
  if ((balance > 1) && (key < N->left_child_->key_)) {
    return rotate_right(N);
  }

  // Right Right Case
  if ((balance < -1) && (key > N->right_child_->key_)) {
    return rotate_left(N);
  }

  // Left Right Case
  if ((balance > 1) && (key > N->left_child_->key_)) {
    N->left_child_ = rotate_left(N->left_child_);
    return rotate_right(N);
  }

  // Right Left Case
  if ((balance < -1) && (key < N->right_child_->key_)) {
    N->right_child_ = rotate_right(N->right_child_);
    return rotate_left(N);
  }

  return N;
}

template <typename T>
AVLNode<T>* AVLTree<T>::inorder_successor(AVLNode<T>* N) {
  AVLNode<T>* current = N;
  while (current->left_child_ != nullptr) {
    current = current->left_child_;
  }
  return current;
}

template <typename T>
AVLNode<T>* AVLTree<T>::remove(AVLNode<T>* N, const T key) {

  if (N == nullptr) {
    return N;
  }

  if (key < N->key_) {
    N->left_child_ = remove(N->left_child_, key);
  } else if(key > N->key_) {
    N->right_child_ = remove(N->right_child_, key);
  } else {

    // node with only one child or no child
    if( (N->left_child_ == nullptr) || (N->right_child_ == nullptr) ) {

      struct AVLNode<T>* temp = N->left_child_ ? N->left_child_ : N->right_child_;

      // No child case
      if(temp == nullptr) {
        temp = N;
        N = NULL;
      } else {// One child case
        *N = *temp; // Copy the contents of the non-empty child
      }

      delete temp;

    } else {

      AVLNode<T>* temp = inorder_successor(N->right_child_);

      N->key_ = temp->key_;

      // Delete the inorder successor
      N->right_child_ = remove(N->right_child_, temp->key_);
    }
  }

  // If the tree had only one node then return
  if (N == NULL)
    return N;

  N->height_ = max(height(N->left_child_), height(N->right_child_)) + 1;

  int balance = get_balance_factor(N);

  // Left Left Case
  if ((balance > 1) && (get_balance_factor(N->left_child_) >= 0)) {
    return rotate_right(N);
  }

  // Left Right Case
  if ((balance > 1) && (get_balance_factor(N->left_child_) < 0)) {
    N->left_child_ = rotate_left(N->left_child_);
    return rotate_right(N);
  }

  // Right Right Case
  if ((balance < -1) && (get_balance_factor(N->right_child_) <= 0)) {
    return rotate_left(N);
  }

  // Right Left Case
  if ((balance < -1) && (get_balance_factor(N->right_child_) > 0)) {
    N->right_child_ = rotate_right(N->right_child_);
    return rotate_left(N);
  }

  return N;
}

template <typename T>
AVLNode<T>* AVLTree<T>::rotate_right(AVLNode<T>* P) {

  AVLNode<T>* N = P->left_child_;
  AVLNode<T>* B = N->right_child_;

  // Perform rotation
  N->right_child_ = P;
  P->left_child_ = B;

  // Update heights
  P->height_ = max(height(P->left_child_), height(P->right_child_))+1;
  N->height_ = max(height(N->left_child_), height(N->right_child_))+1;

  return N;
}

template <typename T>
AVLNode<T>* AVLTree<T>::rotate_left(AVLNode<T>* P) {

  AVLNode<T>* N = P->right_child_;
  AVLNode<T>* B = N->left_child_;

  // Perform rotation
  N->left_child_ = P;
  P->right_child_ = B;

  // Update heights
  P->height_ = max(height(P->left_child_), height(P->right_child_))+1;
  N->height_ = max(height(N->left_child_), height(N->right_child_))+1;

  return N;
}

template <typename T>
void AVLTree<T>::preorder_print(AVLNode<T>* N) {
  if(N != nullptr) {
    cout << N->key_ << ' ';
    preorder_print(N->left_child_);
    preorder_print(N->right_child_);
  }
}

template <typename T>
void AVLTree<T>::inorder_print(AVLNode<T>* N) {
  if(N != nullptr) {
    inorder_print(N->left_child_);
    cout << N->key_ << ' ';
    inorder_print(N->right_child_);
  }
}

template <typename T>
void AVLTree<T>::postorder_print(AVLNode<T>* N) {
  if(N != nullptr) {
    postorder_print(N->left_child_);
    postorder_print(N->right_child_);

    // for (size_t i = 0; i + N->height_ < root_->height_; i++) cout << ' ';
    cout << N->key_ << ' ';
  }
}

template <typename T>
void AVLTree<T>::_bfs_print() {
  const int HEIGHT = root_->height_;
  queue<AVLNode<T> *> temp_queue;
  temp_queue.push(root_);

  for(AVLNode<T>* N; !temp_queue.empty(); ) {
    N = temp_queue.front();
    temp_queue.pop();

    cout << N->key_ << ' ';

    N->left_child_ ? temp_queue.push(N->left_child_) : void(0);
    N->right_child_ ? temp_queue.push(N->right_child_) : void(0);
  }
}


// Public
template <typename T>
void AVLTree<T>::insert (const T key) {
  root_ = insert(root_, key);
}

template <typename T>
void AVLTree<T>::remove (const T key) {
  root_ = remove(root_, key);
}

template <typename T>
T AVLTree<T>::pop () {
  AVLNode<T>* min_node = inorder_successor(root_);
  T key = min_node->key_;
  remove(key);
  return key;
}

template <typename T>
void AVLTree<T>::preorder_print() {
  preorder_print(root_);
  cout << endl;
}

template <typename T>
void AVLTree<T>::inorder_print() {
  inorder_print(root_);
  cout << endl;
}

template <typename T>
void AVLTree<T>::postorder_print() {
  postorder_print(root_);
  cout << endl;
}

template <typename T>
void AVLTree<T>::bfs_print() {
  _bfs_print();
  cout << endl;
}

参考:

  1. https://github.com/weberd6/balancedBinarySearchTrees
  2. https://en.wikipedia.org/wiki/AVL_tree

作者: V

Web Dev

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s