如何解決AVLTree沒有統一旋轉操作的問題

如何解決AVLTree沒有統一旋轉操作的問題，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。

最近疫情比較嚴重，只能在家里休息，利用休息之余，我用C++把AVL樹實現了一遍

大學老師只講一些比較簡單的數據結構和算法，這些高級數據結構還是需要自己主動學習并且動手來實現的，

從前只聽說過AVLTree，我從看書了解原理到把它一點一點寫出來最后在調試一共花了大概3天的時間。應該已經算很長時間了。

一般情況下AVL樹是不用我么自己寫的，但是為了有一份已經實現的代碼作為我以后再來回顧算法實現的依照，我還是決定對自己狠一些把它實現了一遍

以下代碼均采用C++11 標準

在ubuntu 18.04上經過編譯和調試

/* * BinarySearchTree.h * 1. 添加元素時需自己做判斷元素是否合法 * 2. 除層序遍歷外，本源代碼均采用遞歸遍歷，若要減少棧的消耗，應該實現遞歸遍歷 * 3. 本代碼實現的AVL樹沒有統一旋轉操作，采用分情況討論LL,LR,RR,RL來進行樹的平衡 * Created on: 2020年1月29日 *   Author: LuYonglei */#ifndef SRC_BINARYSEARCHTREE_H_#define SRC_BINARYSEARCHTREE_H_#include <queue>template<typename Element>class BinarySearchTree {public:  BinarySearchTree(int (*cmp)(Element e1, Element e2)); //比較函數指針  virtual ~BinarySearchTree();  int size(); //元素的數量  bool isEmpty(); //是否為空  void clear() {    //清空所有元素    NODE *node = root_;    root_ = nullptr;    using namespace std;    queue<NODE*> q;    q.push(node);    while (!q.empty()) {      NODE *tmp = q.front();      if (tmp->left != nullptr)        q.push(tmp->left);      if (tmp->right != nullptr)        q.push(tmp->right);      delete tmp;      q.pop();    }  }  void add(Element e) {    //添加元素    add(e, cmp_);  }  void remove(Element e) {    //刪除元素    remove(Node(e, cmp_));  }  bool contains(Element e) {    //是否包含某元素    return Node(e, cmp_) != nullptr;  }  void preorderTraversal(bool (*visitor)(Element &e)) {    //前序遍歷    if (visitor == nullptr)      return;    bool stop = false; //停止標志，若stop為true，則停止遍歷    preorderTraversal(root_, stop, visitor);  }  void inorderTraversal(bool (*visitor)(Element &e)) {    //中序遍歷    if (visitor == nullptr)      return;    bool stop = false; //停止標志，若stop為true，則停止遍歷    inorderTraversal(root_, stop, visitor);  }  void postorderTraversal(bool (*visitor)(Element &e)) {    //后序遍歷    if (visitor == nullptr)      return;    bool stop = false; //停止標志，若stop為true，則停止遍歷    postorderTraversal(root_, stop, visitor);  }  void levelOrderTraversal(bool (*visitor)(Element &e)) {    //層序遍歷，迭代實現    if (visitor == nullptr)      return;    levelOrderTraversal(root_, visitor);  }  int height() {    //樹的高度    return height(root_);  }  bool isComplete() {    //判斷是否是完全二叉樹    return isComplete(root_);  }private:  int size_;  typedef struct _Node {    Element e;    _Node *parent;    _Node *left;    _Node *right;    int height; //節點的高度    _Node(Element e_, _Node *parent_) :        e(e_), parent(parent_), left(nullptr), right(nullptr), height(1) {      //節點構造函數    }    inline bool isLeaf() {      return (left == nullptr && right == nullptr);    }    inline bool hasTwoChildren() {      return (left != nullptr && right != nullptr);    }    inline int balanceFactor() {      //獲得節點的平衡因子      int leftHeight = left == nullptr ? 0 : left->height; //獲得左子樹的高度      int rightHeight = right == nullptr ? 0 : right->height; //獲得右子樹的高度      return leftHeight - rightHeight;    }    inline bool isBalanced() {      //判斷node是否平衡      int balanceFactor_ = balanceFactor();      return balanceFactor_ >= -1 && balanceFactor_ <= 1; //平衡因子為-1,0,1則返回true    }    inline void updateHeight() {      //更新節點的高度      int leftHeight = left == nullptr ? 0 : left->height; //獲得左子樹的高度      int rightHeight = right == nullptr ? 0 : right->height; //獲得右子樹的高度      height = 1 + (leftHeight > rightHeight ? leftHeight : rightHeight); //把節點高度更新為左右子樹最大的高度+1    }    inline bool isLeftChild() {      //判斷節點是否是父親節點的左子結點      return parent != nullptr && parent->left == this;    }    inline bool isRightChild() {      //判斷節點是否是父親節點的右子結點      return parent != nullptr && parent->right == this;    }    inline _Node* tallerChild() {      //獲得高度更高的子樹      int leftHeight = left == nullptr ? 0 : left->height; //獲得左子樹的高度      int rightHeight = right == nullptr ? 0 : right->height; //獲得右子樹的高度      if (leftHeight > rightHeight)        return left;      if (leftHeight < rightHeight)        return right;      return isLeftChild() ? left : right;    }  } NODE;  NODE *root_;  int (*cmp_)(Element e1, Element e2); //為實現樹的排序的個性化配置，私有成員保存一個比較函數指針  NODE* Node(Element e, int (*cmp_)(Element e1, Element e2)) {    //返回e元素所在的節點    NODE *node = root_;    while (node != nullptr) {      int cmp = cmp_(e, node->e);      if (cmp == 0) //找到了元素        return node;      if (cmp > 0) { //待尋找元素大于節點存儲的元素        node = node->right;      } else { //待尋找元素小于節點存儲的元素        node = node->left;      }    }    return nullptr;  }  NODE* predecessor(NODE *node) {    //返回node的前驅節點    if (node == nullptr)      return nullptr;    //前驅節點在左子樹    NODE *tmp = node->left;    if (tmp != nullptr) {      while (tmp->right != nullptr)        tmp = tmp->right;      return tmp;    }    //從父節點，祖父節點中尋找前驅節點    while (node->parent != nullptr && node == node->parent->left) {      node = node->parent;    }    return node->parent;  }  NODE* successor(NODE *node) {    //返回node的后繼節點    if (node == nullptr)      return nullptr;    //后繼節點在右子樹    NODE *tmp = node->right;    if (tmp != nullptr) {      while (tmp->left != nullptr)        tmp = tmp->left;      return tmp;    }    //從父節點，祖父節點中尋找后繼節點    while (node->parent != nullptr && node == node->parent->right) {      node = node->parent;    }    return node->parent;  }  void afterRotate(NODE *gNode, NODE *pNode, NODE *child) {    //在左旋轉與右旋轉中統一調用    pNode->parent = gNode->parent;    if (gNode->isLeftChild())      gNode->parent->left = pNode;    else if (gNode->isRightChild())      gNode->parent->right = pNode;    else      //此時gNode->parent 為nullptr，gNode為root節點      root_ = pNode;    if (child != nullptr)      child->parent = gNode;    gNode->parent = pNode;    //左右子樹發生變化，所以要更新高度    gNode->updateHeight();    pNode->updateHeight();  }  void rotateLeft(NODE *gNode) {    //對gNode進行左旋轉    NODE *pNode = gNode->right;    NODE *child = pNode->left;    gNode->right = child;    pNode->left = gNode;    afterRotate(gNode, pNode, child);  }  void rotateRight(NODE *gNode) {    //對gNode進行右旋轉    NODE *pNode = gNode->left;    NODE *child = pNode->right;    gNode->left = child;    pNode->right = gNode;    afterRotate(gNode, pNode, child);  }  void rebalance(NODE *gNode) {    //恢復平衡,grand為高度最低的不平衡節點    NODE *pNode = gNode->tallerChild();    NODE *nNode = pNode->tallerChild();    if (pNode->isLeftChild()) {      if (nNode->isLeftChild()) {        //LL        /*         *    gNode         *   /     對gNode右旋         *   pNode    ====>    pNode         *  /            /   \         *  nNode          nNode  gNode         */        rotateRight(gNode);      } else {        //LR        /*         *    gNode         gNode         *   /    對pNode左旋   /    對gNode右旋         *   pNode   ====>    nNode   ====>    nNode         *   \          /           /   \         *    nNode       pNode         pNode gNode         */        rotateLeft(pNode);        rotateRight(gNode);      }    } else {      if (nNode->isLeftChild()) {        //RL        /*         *  gNode         gNode         *   \    對pNode右旋  \    對gNode左旋         *   pNode   ====>    nNode   ====>    nNode         *   /            \          /   \         *  nNode           pNode       gNode pNode         */        rotateRight(pNode);        rotateLeft(gNode);      } else {        //RR        /*         *  gNode         *  \    對gNode左旋         *   pNode   ====>    pNode         *   \          /   \         *    nNode       gNode nNode         */        rotateLeft(gNode);      }    }  }  void afterAdd(NODE *node) {    //添加node之后的調整    if (node == nullptr)      return;    node = node->parent;    while (node != nullptr) {      if (node->isBalanced()) {        //如果節點平衡，則對其更新高度        node->updateHeight();      } else {        //此時對第一個不平衡節點操作，使其平衡        rebalance(node);        //整棵樹恢復平衡后,跳出循環        break;      }      node = node->parent;    }  }  void add(Element e, int (*cmp_)(Element e1, Element e2)) {    //當樹為空時，添加的節點作為樹的根節點    if (root_ == nullptr) {      root_ = new NODE(e, nullptr);      size_++;      //插入一個根節點之后進行調整      afterAdd(root_);      return;    }    //當添加的節點不是第一個節點    NODE *parent = root_;    NODE *node = root_;    int cmp = 0; //比較結果    while (node != nullptr) {      parent = node; //保存父節點      cmp = cmp_(e, node->e); //由函數指針來比較      if (cmp > 0) {        node = node->right; //添加的元素大于節點中的元素      } else if (cmp < 0) {        node = node->left; //添加的元素小于節點中的元素      } else {        node->e = e; //相等時就覆蓋        return; //添加的元素等于節點中的元素,直接返回      }    }    //判斷要插入父節點的哪個位置    NODE *newNode = new NODE(e, parent); //為新元素創建節點    if (cmp > 0) {      parent->right = newNode; //添加的元素大于節點中的元素    } else {      parent->left = newNode; //添加的元素小于節點中的元素    }    size_++;    //添加一個新節點之后進行調整    afterAdd(newNode);  }  void afterRemove(NODE *node) {    //刪除node之后的調整    if (node == nullptr)      return;    node = node->parent;    while (node != nullptr) {      if (node->isBalanced()) {        //如果節點平衡，則對其更新高度        node->updateHeight();      } else {        //此時對不平衡節點操作，使其平衡        rebalance(node);      }      node = node->parent;    }  }  void remove(NODE *node_) {    //刪除某一節點    if (node_ == nullptr)      return;    size_--;    //優先刪除度為2的節點    if (node_->hasTwoChildren()) {      NODE *pre = successor(node_); //找到node_的后繼節點      node_->e = pre->e; //用后繼節點的值覆蓋度為2的節點的值      //刪除后繼節點(后繼節點的度只能為1或0)      node_ = pre;    }    //此時node_的度必然為0或1    NODE *replacement = node_->left != nullptr ? node_->left : node_->right;    if (replacement != nullptr) {      //node_的度為1      replacement->parent = node_->parent;      if (node_->parent == nullptr)      //度為1的根節點        root_ = replacement;      else if (node_->parent->left == node_)        node_->parent->left = replacement;      else        node_->parent->right = replacement;      //所有刪除操作準備完成，準備釋放節點內存前進行平衡操作      afterRemove(node_);      delete node_;    } else if (node_->parent == nullptr) {      //node_是葉子節點，也是根節點      root_ = nullptr;      //所有刪除操作準備完成，準備釋放節點內存前進行平衡操作      afterRemove(node_);      delete node_;    } else {      //node_是葉子節點，但不是根節點      if (node_->parent->left == node_)        node_->parent->left = nullptr;      else        node_->parent->right = nullptr;      //所有刪除操作準備完成，準備釋放節點內存前進行平衡操作      afterRemove(node_);      delete node_;    }  }  void preorderTraversal(NODE *node, bool &stop,      bool (*visitor)(Element &e)) {    //遞歸實現前序遍歷    if (node == nullptr || stop == true)      return;    stop = visitor(node->e);    preorderTraversal(node->left, stop, visitor);    preorderTraversal(node->right, stop, visitor);  }  void inorderTraversal(NODE *node, bool &stop, bool (*visitor)(Element &e)) {    //遞歸實現中序遍歷    if (node == nullptr || stop == true)      return;    inorderTraversal(node->left, stop, visitor);    if (stop == true)      return;    stop = visitor(node->e);    inorderTraversal(node->right, stop, visitor);  }  void postorderTraversal(NODE *node, bool &stop,      bool (*visitor)(Element &e)) {    //遞歸實現后序遍歷    if (node == nullptr || stop == true)      return;    postorderTraversal(node->left, stop, visitor);    postorderTraversal(node->right, stop, visitor);    if (stop == true)      return;    stop = visitor(node->e);  }  void levelOrderTraversal(NODE *node, bool (*visitor)(Element &e)) {    if (node == nullptr)      return;    using namespace std;    queue<NODE*> q;    q.push(node);    while (!q.empty()) {      NODE *node = q.front();      if (visitor(node->e) == true)        return;      if (node->left != nullptr)        q.push(node->left);      if (node->right != nullptr)        q.push(node->right);      q.pop();    }  }  int height(NODE *node) {    //某一節點的高度    return node->height;  }  bool isComplete(NODE *node) {    if (node == nullptr)      return false;    using namespace std;    queue<NODE*> q;    q.push(node);    bool leaf = false; //判斷接下來的節點是否為葉子節點    while (!q.empty()) {      NODE *node = q.front();      if (leaf && !node->isLeaf()) //判斷葉子節點        return false;      if (node->left != nullptr) {        q.push(node->left);      } else if (node->right != nullptr) { //node->left == nullptr && node->right != nullptr        return false;      }      if (node->right != nullptr) {        q.push(node->right);      } else { //node->right==nullptr        leaf = true;      }      q.pop();    }    return true;  }};template<typename Element>BinarySearchTree<Element>::BinarySearchTree(int (*cmp)(Element e1, Element e2)) :    size_(0), root_(nullptr), cmp_(cmp) {  //樹的構造函數}template<typename Element>BinarySearchTree<Element>::~BinarySearchTree() {  // 析構函數  clear();}template<typename Element>inline int BinarySearchTree<Element>::size() {  //返回元素個數  return size_;}template<typename Element>inline bool BinarySearchTree<Element>::isEmpty() {  //判斷是否為空樹  return size_ == 0;}#endif /* SRC_BINARYSEARCHTREE_H_ */main方法/* * main.cpp * * Created on: 2020年1月29日 *   Author: LuYonglei */#include "BinarySearchTree.h"#include <iostream>#include <time.h>using namespace std;template<typename Element>int compare(Element e1, Element e2) {  //比較函數,相同返回0,e1<e2返回-1,e1>e2返回1  return e1 == e2 ? 0 : (e1 < e2 ? -1 : 1);}template<typename Elemnet>bool visitor(Elemnet &e) {  cout << e << " ";  cout << endl;  return false; //若返回true，則在遍歷時會退出}int main(int argc, char **argv) {  BinarySearchTree<double> a(compare);//  a.add(85);//  a.add(19);//  a.add(69);//  a.add(3);//  a.add(7);//  a.add(99);//  a.add(95);//  a.add(2);//  a.add(1);//  a.add(70);//  a.add(44);//  a.add(58);//  a.add(11);//  a.add(21);//  a.add(14);//  a.add(93);//  a.add(57);//  a.add(4);//  a.add(56);//  a.remove(99);//  a.remove(85);//  a.remove(95);  clock_t start = clock();  for (int i = 0; i < 1000000; i++) {    a.add(i);  }  for (int i = 0; i < 1000000; i++) {    a.remove(i);  }//  a.inorderTraversal(visitor);  clock_t end = clock();  cout << end - start << endl;//  cout <<a.height()<< endl;//  cout << a.isComplete() << endl;//  a.remove(7);//  a.clear();//  a.levelOrderTraversal(visitor);//  cout << endl;//  cout<<a.contains(0)<<endl;}

看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。