如何解決AVLTree沒有統(tǒng)一旋轉(zhuǎn)操作的問題

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

最近疫情比較嚴(yán)重，只能在家里休息，利用休息之余，我用C++把AVL樹實(shí)現(xiàn)了一遍

大學(xué)老師只講一些比較簡單的數(shù)據(jù)結(jié)構(gòu)和算法，這些高級數(shù)據(jù)結(jié)構(gòu)還是需要自己主動(dòng)學(xué)習(xí)并且動(dòng)手來實(shí)現(xiàn)的，

從前只聽說過AVLTree，我從看書了解原理到把它一點(diǎn)一點(diǎn)寫出來最后在調(diào)試一共花了大概3天的時(shí)間。應(yīng)該已經(jīng)算很長時(shí)間了。

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

以下代碼均采用C++11 標(biāo)準(zhǔn)

在ubuntu 18.04上經(jīng)過編譯和調(diào)試

/* * BinarySearchTree.h * 1. 添加元素時(shí)需自己做判斷元素是否合法 * 2. 除層序遍歷外，本源代碼均采用遞歸遍歷，若要減少棧的消耗，應(yīng)該實(shí)現(xiàn)遞歸遍歷 * 3. 本代碼實(shí)現(xiàn)的AVL樹沒有統(tǒng)一旋轉(zhuǎn)操作，采用分情況討論LL,LR,RR,RL來進(jìn)行樹的平衡 * 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)); //比較函數(shù)指針  virtual ~BinarySearchTree();  int size(); //元素的數(shù)量  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; //停止標(biāo)志，若stop為true，則停止遍歷    preorderTraversal(root_, stop, visitor);  }  void inorderTraversal(bool (*visitor)(Element &e)) {    //中序遍歷    if (visitor == nullptr)      return;    bool stop = false; //停止標(biāo)志，若stop為true，則停止遍歷    inorderTraversal(root_, stop, visitor);  }  void postorderTraversal(bool (*visitor)(Element &e)) {    //后序遍歷    if (visitor == nullptr)      return;    bool stop = false; //停止標(biāo)志，若stop為true，則停止遍歷    postorderTraversal(root_, stop, visitor);  }  void levelOrderTraversal(bool (*visitor)(Element &e)) {    //層序遍歷，迭代實(shí)現(xiàn)    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; //節(jié)點(diǎn)的高度    _Node(Element e_, _Node *parent_) :        e(e_), parent(parent_), left(nullptr), right(nullptr), height(1) {      //節(jié)點(diǎn)構(gòu)造函數(shù)    }    inline bool isLeaf() {      return (left == nullptr && right == nullptr);    }    inline bool hasTwoChildren() {      return (left != nullptr && right != nullptr);    }    inline int balanceFactor() {      //獲得節(jié)點(diǎn)的平衡因子      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() {      //更新節(jié)點(diǎn)的高度      int leftHeight = left == nullptr ? 0 : left->height; //獲得左子樹的高度      int rightHeight = right == nullptr ? 0 : right->height; //獲得右子樹的高度      height = 1 + (leftHeight > rightHeight ? leftHeight : rightHeight); //把節(jié)點(diǎn)高度更新為左右子樹最大的高度+1    }    inline bool isLeftChild() {      //判斷節(jié)點(diǎn)是否是父親節(jié)點(diǎn)的左子結(jié)點(diǎn)      return parent != nullptr && parent->left == this;    }    inline bool isRightChild() {      //判斷節(jié)點(diǎn)是否是父親節(jié)點(diǎn)的右子結(jié)點(diǎn)      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); //為實(shí)現(xiàn)樹的排序的個(gè)性化配置，私有成員保存一個(gè)比較函數(shù)指針  NODE* Node(Element e, int (*cmp_)(Element e1, Element e2)) {    //返回e元素所在的節(jié)點(diǎn)    NODE *node = root_;    while (node != nullptr) {      int cmp = cmp_(e, node->e);      if (cmp == 0) //找到了元素        return node;      if (cmp > 0) { //待尋找元素大于節(jié)點(diǎn)存儲的元素        node = node->right;      } else { //待尋找元素小于節(jié)點(diǎn)存儲的元素        node = node->left;      }    }    return nullptr;  }  NODE* predecessor(NODE *node) {    //返回node的前驅(qū)節(jié)點(diǎn)    if (node == nullptr)      return nullptr;    //前驅(qū)節(jié)點(diǎn)在左子樹    NODE *tmp = node->left;    if (tmp != nullptr) {      while (tmp->right != nullptr)        tmp = tmp->right;      return tmp;    }    //從父節(jié)點(diǎn)，祖父節(jié)點(diǎn)中尋找前驅(qū)節(jié)點(diǎn)    while (node->parent != nullptr && node == node->parent->left) {      node = node->parent;    }    return node->parent;  }  NODE* successor(NODE *node) {    //返回node的后繼節(jié)點(diǎn)    if (node == nullptr)      return nullptr;    //后繼節(jié)點(diǎn)在右子樹    NODE *tmp = node->right;    if (tmp != nullptr) {      while (tmp->left != nullptr)        tmp = tmp->left;      return tmp;    }    //從父節(jié)點(diǎn)，祖父節(jié)點(diǎn)中尋找后繼節(jié)點(diǎn)    while (node->parent != nullptr && node == node->parent->right) {      node = node->parent;    }    return node->parent;  }  void afterRotate(NODE *gNode, NODE *pNode, NODE *child) {    //在左旋轉(zhuǎn)與右旋轉(zhuǎn)中統(tǒng)一調(diào)用    pNode->parent = gNode->parent;    if (gNode->isLeftChild())      gNode->parent->left = pNode;    else if (gNode->isRightChild())      gNode->parent->right = pNode;    else      //此時(shí)gNode->parent 為nullptr，gNode為root節(jié)點(diǎn)      root_ = pNode;    if (child != nullptr)      child->parent = gNode;    gNode->parent = pNode;    //左右子樹發(fā)生變化，所以要更新高度    gNode->updateHeight();    pNode->updateHeight();  }  void rotateLeft(NODE *gNode) {    //對gNode進(jìn)行左旋轉(zhuǎn)    NODE *pNode = gNode->right;    NODE *child = pNode->left;    gNode->right = child;    pNode->left = gNode;    afterRotate(gNode, pNode, child);  }  void rotateRight(NODE *gNode) {    //對gNode進(jìn)行右旋轉(zhuǎn)    NODE *pNode = gNode->left;    NODE *child = pNode->right;    gNode->left = child;    pNode->right = gNode;    afterRotate(gNode, pNode, child);  }  void rebalance(NODE *gNode) {    //恢復(fù)平衡,grand為高度最低的不平衡節(jié)點(diǎn)    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之后的調(diào)整    if (node == nullptr)      return;    node = node->parent;    while (node != nullptr) {      if (node->isBalanced()) {        //如果節(jié)點(diǎn)平衡，則對其更新高度        node->updateHeight();      } else {        //此時(shí)對第一個(gè)不平衡節(jié)點(diǎn)操作，使其平衡        rebalance(node);        //整棵樹恢復(fù)平衡后,跳出循環(huán)        break;      }      node = node->parent;    }  }  void add(Element e, int (*cmp_)(Element e1, Element e2)) {    //當(dāng)樹為空時(shí)，添加的節(jié)點(diǎn)作為樹的根節(jié)點(diǎn)    if (root_ == nullptr) {      root_ = new NODE(e, nullptr);      size_++;      //插入一個(gè)根節(jié)點(diǎn)之后進(jìn)行調(diào)整      afterAdd(root_);      return;    }    //當(dāng)添加的節(jié)點(diǎn)不是第一個(gè)節(jié)點(diǎn)    NODE *parent = root_;    NODE *node = root_;    int cmp = 0; //比較結(jié)果    while (node != nullptr) {      parent = node; //保存父節(jié)點(diǎn)      cmp = cmp_(e, node->e); //由函數(shù)指針來比較      if (cmp > 0) {        node = node->right; //添加的元素大于節(jié)點(diǎn)中的元素      } else if (cmp < 0) {        node = node->left; //添加的元素小于節(jié)點(diǎn)中的元素      } else {        node->e = e; //相等時(shí)就覆蓋        return; //添加的元素等于節(jié)點(diǎn)中的元素,直接返回      }    }    //判斷要插入父節(jié)點(diǎn)的哪個(gè)位置    NODE *newNode = new NODE(e, parent); //為新元素創(chuàng)建節(jié)點(diǎn)    if (cmp > 0) {      parent->right = newNode; //添加的元素大于節(jié)點(diǎn)中的元素    } else {      parent->left = newNode; //添加的元素小于節(jié)點(diǎn)中的元素    }    size_++;    //添加一個(gè)新節(jié)點(diǎn)之后進(jìn)行調(diào)整    afterAdd(newNode);  }  void afterRemove(NODE *node) {    //刪除node之后的調(diào)整    if (node == nullptr)      return;    node = node->parent;    while (node != nullptr) {      if (node->isBalanced()) {        //如果節(jié)點(diǎn)平衡，則對其更新高度        node->updateHeight();      } else {        //此時(shí)對不平衡節(jié)點(diǎn)操作，使其平衡        rebalance(node);      }      node = node->parent;    }  }  void remove(NODE *node_) {    //刪除某一節(jié)點(diǎn)    if (node_ == nullptr)      return;    size_--;    //優(yōu)先刪除度為2的節(jié)點(diǎn)    if (node_->hasTwoChildren()) {      NODE *pre = successor(node_); //找到node_的后繼節(jié)點(diǎn)      node_->e = pre->e; //用后繼節(jié)點(diǎn)的值覆蓋度為2的節(jié)點(diǎn)的值      //刪除后繼節(jié)點(diǎn)(后繼節(jié)點(diǎn)的度只能為1或0)      node_ = pre;    }    //此時(shí)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的根節(jié)點(diǎn)        root_ = replacement;      else if (node_->parent->left == node_)        node_->parent->left = replacement;      else        node_->parent->right = replacement;      //所有刪除操作準(zhǔn)備完成，準(zhǔn)備釋放節(jié)點(diǎn)內(nèi)存前進(jìn)行平衡操作      afterRemove(node_);      delete node_;    } else if (node_->parent == nullptr) {      //node_是葉子節(jié)點(diǎn)，也是根節(jié)點(diǎn)      root_ = nullptr;      //所有刪除操作準(zhǔn)備完成，準(zhǔn)備釋放節(jié)點(diǎn)內(nèi)存前進(jìn)行平衡操作      afterRemove(node_);      delete node_;    } else {      //node_是葉子節(jié)點(diǎn)，但不是根節(jié)點(diǎn)      if (node_->parent->left == node_)        node_->parent->left = nullptr;      else        node_->parent->right = nullptr;      //所有刪除操作準(zhǔn)備完成，準(zhǔn)備釋放節(jié)點(diǎn)內(nèi)存前進(jìn)行平衡操作      afterRemove(node_);      delete node_;    }  }  void preorderTraversal(NODE *node, bool &stop,      bool (*visitor)(Element &e)) {    //遞歸實(shí)現(xiàn)前序遍歷    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)) {    //遞歸實(shí)現(xiàn)中序遍歷    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)) {    //遞歸實(shí)現(xiàn)后序遍歷    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) {    //某一節(jié)點(diǎn)的高度    return node->height;  }  bool isComplete(NODE *node) {    if (node == nullptr)      return false;    using namespace std;    queue<NODE*> q;    q.push(node);    bool leaf = false; //判斷接下來的節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)    while (!q.empty()) {      NODE *node = q.front();      if (leaf && !node->isLeaf()) //判斷葉子節(jié)點(diǎn)        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) {  //樹的構(gòu)造函數(shù)}template<typename Element>BinarySearchTree<Element>::~BinarySearchTree() {  // 析構(gòu)函數(shù)  clear();}template<typename Element>inline int BinarySearchTree<Element>::size() {  //返回元素個(gè)數(shù)  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) {  //比較函數(shù),相同返回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，則在遍歷時(shí)會(huì)退出}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;}

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