经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » C++ » 查看文章
数据结构学习-AVL平衡树
来源：cnblogs　　作者：cyrio　　时间：2018/12/17 9:47:37　　对本文有异议

环境：C++11 + win10

IDE：Clion 2018.3

AVL平衡树是在BST二叉查找树的基础上添加了平衡机制。

我们把平衡的BST认为是任一节点的左子树和右子树的高度差为-1,0,1中的一种情况，即不存在相差两层及以上。

所谓平衡机制就是BST在理想情况下搜索复杂度是o(logn)

但是如果在（存在某一节点，该节点的左子树的高度与右子树的高度差>1）这种状况下，复杂度会超过o(logn)

举个极端的例子如加入1,2,3,4，BST就退化为一个线性的链表，复杂度变成了o(n)

为了避免这种情况，我们在BST中引入平衡操作（旋转操作），使得BST始终不存在左右子树超过1高度差的节点。

本次代码基于我的另一篇博客的基础之上，有需要可以翻看 https://www.cnblogs.com/cyrio/p/10118132.html

平衡机制主要通过反转完成，经过归纳，可能出现以下四种不平衡的情况：LL、LR、RL、RR

L=left     R=right

我们将不平衡点设为X点，以LR为例，第一个L表示X点的左子树比右子树层数多（>1），第二个R表示多出的那部分在X点的左子树的右子树。（不管他是在X的左子树的右子树的左右哪边，都称为LR）

 

如图：

 

 接下来我们以LL、LR、RR、RL四种情况讨论。

1、LL：

通俗的讲就是把K2从K1那扯下来，然后把Y移到K2的左子树，最后把K2移到K1的右子树。

2、RR：

与LL同理，把K1先扯下来，再把Y接到K1的右侧，再把K1作为左子树接到K2。

 3、LR：

LR需要先做一次RR再做一次LL：

先把K1从K2那扯下来，让K2和K3连，然后把B作为K1的右子树，再把K1连到K2的左子树上。

然后再做LL，把K3从K2上面扯下来，让C作为K3的左子树，再把K3连到K2的右子树。

4、RL：

先LL再RR，与LR同理。

以上是主要思想的分析，除了旋转操作，我们还需要添加新的方法：

1、求树的高度：height方法

2、求某节点的左子树和右子树的高度差 ：Diff方法      

3、一个对整个树进行判断，对里面的X节点进行对应操作：Balance方法

同时AVL中的Insert（插入某一节点）的方法与BST中也略有不同，需要注意的是AVL种的__Insert（PS：带"__"的表示私有内部接口）的参数中第一个为bstNode<T> * & root （需要&引用）

具体代码如下：（此代码为完整代码，可以直接复制进自己的项目查看效果）

myBST.h

  1. #ifndef TEST1_MYBST_H#define TEST1_MYBST_H#include <iomanip>#include "bstNode.h"#include <vector>#include <deque>#include <iostream>#include <algorithm>using namespace std;
  2.  
  3. template <typename T>class myBST{private:
  4.     bstNode<T> * root = nullptr;
  5.     bstNode<T> * __search(bstNode<T> * root , const T &key){if (nullptr == root)return nullptr;if (key == root->data)return root;else if (key < root->data)return __search(root->left, key);elsereturn __search(root->right, key);
  6.     } //查找关键字是否存在bstNode<T> * __treeMin(bstNode<T> * root , bstNode<T> * &parent){
  7.         bstNode<T> * curr = root;while(curr->left!= nullptr){
  8.             parent = curr;
  9.             curr = curr->left;
  10.         }return  curr;
  11.     } //返回最小节点（一路向左）bstNode<T> * __Insert(bstNode<T> * &root, const T &key){if (nullptr == root)
  12.         {
  13.             root = new bstNode<T>(key);return root;
  14.         }//递归返回条件else if (key < root->data)
  15.         {
  16.             root->left = __Insert(root->left,key);//递归左子树//balance operationroot = __Balance(root);//平衡操作包含了四种旋转        }else if (key>root->data)
  17.         {
  18.             root->right = __Insert(root->right,key);//递归右子树//balance operationroot = __Balance(root);//平衡操作包含了四种旋转        }return root;
  19.     } //插入指定值bool __Delete(const T &key){bool found = false;//存储有没有找到key的变量if(isEmpty()){
  20.             cerr<<"BST为空"<<endl;return false;
  21.         }
  22.         bstNode<T> * curr = root;
  23.         bstNode<T> * parrent = nullptr;while(curr!= nullptr) {if (key == curr->data) {
  24.                 found = true;break;
  25.             } else {
  26.                 parrent = curr;if (key < curr->data) curr = curr->left;else curr = curr->right;
  27.             }
  28.         }if(!found){
  29.             cerr<<"未找到key！"<<endl;return false;
  30.         }if (parrent == nullptr){//删除根节点root = nullptr;delete(curr);return true;
  31.         }/* 删除的节点有三种可能：
  32.          1、叶子结点
  33.          2、一个孩子的节点
  34.          3、两个孩子的节点         */if (__isLeaf(curr)){ //删除的点是叶子结点if(parrent->left==curr) parrent->left= nullptr;else parrent->right= nullptr;delete(curr);return true;
  35.         }else if(__isNodeWithTwoChild(curr)){ //是两个孩子的节点//以当前右子树中的最小值取代他bstNode<T> * parrent = curr;
  36.             bstNode<T> * tmp = __treeMin(curr->right,parrent);
  37.             curr->data = tmp->data;if(parrent->right==tmp)
  38.                 parrent->right== nullptr;else parrent->left== nullptr;delete(tmp);return true;
  39.         }else{ //只有一个孩子的节点if(curr->left!= nullptr){if(curr->left == curr){
  40.                     parrent->left=curr->left;delete(curr);return true;
  41.                 }else{
  42.                     parrent->right=curr->right;delete(curr);return true;
  43.                 }
  44.             }if(curr->right!= nullptr){if(curr->left == curr){
  45.                     parrent->left=curr->left;delete(curr);return true;
  46.                 }else{
  47.                     parrent->right=curr->right;delete(curr);return true;
  48.                 }
  49.             }
  50.         }return false;
  51.     } //删除指定值bool __isLeaf(bstNode<T> * const & root){if(root->left== nullptr && root->right== nullptr) return true;else return false;
  52.     }//判断是否是叶子节点bool __isNodeWithTwoChild(bstNode<T> * const & root){if(root->left!= nullptr && root->right!= nullptr) return true;else return false;
  53.     }//判断是否有两个孩子void __InorderTraversal(bstNode<T> *root,std::vector<int>&result){if(nullptr == root) return;
  54.         __InorderTraversal(root->left,result);
  55.         cout<<root->data<<" ";
  56.         result.push_back(root->data);
  57.         __InorderTraversal(root->right,result);
  58.     }//中序遍历void __PreorderTraversal(bstNode<T> *root,std::vector<int>&result){if(nullptr == root) return;
  59.         cout<<root->data<<" ";
  60.         result.push_back(root->data);
  61.         __InorderTraversal(root->left,result);
  62.         __InorderTraversal(root->right,result);
  63.     }//前序遍历void __PostorderTraversal(bstNode<T> *root,std::vector<int>&result){if(nullptr == root) return;
  64.         __InorderTraversal(root->left,result);
  65.         __InorderTraversal(root->right,result);
  66.         cout<<root->data<<" ";
  67.         result.push_back(root->data);
  68.     }//后序遍历void __DeleteAllNodes(bstNode<T> *root){if (root == nullptr) return;
  69.         __DeleteAllNodes(root->left);
  70.         __DeleteAllNodes(root->right);
  71.         __Delete(root->data);
  72.     }//删除所有节点void __BFTraversal(vector<T>&result) {
  73.         deque<bstNode<T> *> TQueue;
  74.         bstNode<T> *pointer = root;if (pointer != nullptr) {
  75.             TQueue.push_back(pointer);
  76.         }while (!TQueue.empty()) {
  77.             pointer = TQueue.front();
  78.             TQueue.pop_front();
  79.             cout << pointer->data << " ";
  80.             result.push_back(pointer->data);if (pointer->left != nullptr) TQueue.push_back(pointer->left);if (pointer->right != nullptr) TQueue.push_back(pointer->right);
  81.         }
  82.     } //广度搜索来进行周游void __Graph(int indent,bstNode<T>* root){if(root != 0){
  83.             __Graph(indent + 8, root->right);
  84.             cout<<setw(indent)<<" "<<root->data<<endl;
  85.             __Graph(indent + 8, root->left);
  86.         }
  87.     } //横着画图的内部接口bstNode<T> * __GetRoot(){return root;
  88.     } //返回根节点的内部接口//以下为AVL平衡树新加的方法int __height(const bstNode<T>* root){if(root == nullptr){return 0;
  89.         }return max(__height(root->left),__height(root->right))+1;
  90.     } //求树的高度int __diff(const bstNode<T>* root){return __height(root->left)-__height(root->right);
  91.     } //求节点的高度差（平衡因子）bstNode<T> * __ll__Rotation(bstNode<T> * root){
  92.         bstNode<T> * tmp;
  93.         tmp = root->left;
  94.         root->left = tmp->right;
  95.         tmp->right = root;return tmp;
  96.     } //单旋转-左左bstNode<T> * __rr__Rotation(bstNode<T> * root){
  97.         bstNode<T> * tmp;
  98.         tmp = root->right;
  99.         root->right = tmp->left;
  100.         tmp->left = root;return tmp;
  101.     } //单旋转-右右bstNode<T> * __lr__Rotation(bstNode<T> * root){
  102.         bstNode<T> * tmp;
  103.         tmp = root->left;
  104.         root->left = __rr__Rotation(tmp);return __ll__Rotation(root);
  105.     } //双旋转-左右型，先右后左转（注意此处相反）bstNode<T> * __rl__Rotation(bstNode<T> * root){
  106.         bstNode<T> * tmp;
  107.         tmp = root->right;
  108.         root->right = __ll__Rotation(tmp);return __rr__Rotation(root);
  109.     } //双旋转-右左型，先左后右转bstNode<T> * __Balance(bstNode<T> * root){int balanceFactor = __diff(root);//__diff用来计算平衡因子（左右子树高度差）if (balanceFactor > 1)//左子树高于右子树        {if (__diff(root->left) > 0)//左左外侧root=__ll__Rotation(root);else//左右内侧root=__lr__Rotation(root);
  110.         }else if (balanceFactor < -1)//右子树高于左子树        {if (__diff(root->right) > 0)//右左内侧root=__rl__Rotation(root);else//右右外侧root=__rr__Rotation(root);
  111.         }return root;
  112.     } //平衡的内部操作public:
  113.     myBST(){
  114.         root = nullptr;
  115.     } //默认构造myBST(vector<T> arr){
  116.         root = nullptr;for(int i =0;i<(T)arr.size();i++){
  117.             Insert(arr[i]);
  118.         }
  119.     }
  120.     myBST(T * arr,int len){
  121.         root = nullptr;for(int i =0;i<len;i++){
  122.             __Insert(*(arr+i));
  123.         }
  124.     }~myBST(){
  125.         bstNode<T> * curr = root;
  126.         __DeleteAllNodes(curr);
  127.     }//析构bool isEmpty() const{return root == nullptr;
  128.     }//判断树空bool search(const T &key){
  129.         bstNode<T> * temp = __search(root, key);return (temp == nullptr) ? false : true;
  130.     }//查找关键字是否存在的对外接口bool Insert(const T &key){return __Insert(root,key);
  131.     }//插入节点的外部接口bool Delete(const T &key){return __Delete(key);
  132.     }//删除节点的外部接口void InorderTraversal(vector<T>&result){
  133.         __InorderTraversal(root, result);
  134.     }//中序遍历的外部接口void PreorderTraversal(vector<T>&result){
  135.         __PreorderTraversal(root, result);
  136.     }//前序遍历的外部接口void PostorderTraversal(vector<T>&result){
  137.         __PostorderTraversal(root, result);
  138.     }//后序遍历的外部接口void BFTraversal(vector<T>&result){return __BFTraversal(result);
  139.     } //广度搜索外部接口void Graph(int indent,bstNode<T>* root){return __Graph(indent,root);
  140.     } //横着画图的外部接口bstNode<T> * GetRoot(){return __GetRoot();
  141.     } //返回根节点的外部接口};#endif //TEST1_MYBST_H

bstNode.h

  1. #ifndef TEST1_BSTNODE_H#define TEST1_BSTNODE_Htemplate <typename T>class bstNode{public:
  2.     T data;
  3.     bstNode* left;
  4.     bstNode* right;
  5.     bstNode(){
  6.         data = 0;
  7.         left = nullptr;
  8.         right = nullptr;
  9.     }
  10.     bstNode(T val){
  11.         data = val;
  12.         left = nullptr;
  13.         right = nullptr;
  14.     }
  15. };#endif //TEST1_BSTNODE_H

main.cpp

  1. #include <iostream>#include <vector>#include "myBST.h"#include "bstNode.h"using namespace std;int main() {
  2.     vector<int> in = {7,6,5,13,17,22,10,3,2,1};
  3.     myBST<int> bst(in);
  4.     bst.Delete(5);
  5.     bst.Insert(4);bool found = bst.search(4);if(!found)
  6.         cout<<"not found!"<<endl;elsecout<<"found!"<<endl;
  7.     vector<int> result;
  8.     cout<<"InorderTravelsal:  ";
  9.     bst.InorderTraversal(result);
  10.     cout<<endl<<"PreorderTravelsal:  ";
  11.     bst.PreorderTraversal(result);
  12.     cout<<endl<<"PostorderTraversal:  ";
  13.     bst.PostorderTraversal(result);
  14.     cout<<endl<<"BFTraversal:  ";
  15.     bst.BFTraversal(result);
  16.     cout<<endl<<"Graph:"<<endl;
  17.     bstNode<int>* pointer = bst.GetRoot();
  18.     bst.Graph(0,pointer);return 0;
  19. }

 

参考：https://blog.csdn.net/zhangxiao93/article/details/51459743

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

C++热门文章

  • C/C++编程笔记：编写不会在C ++中编译的C程序，我教你呀！
  • 洛谷 P2085 最小函数值
  • 使用C++界面框架ImGUI开发一个简单程序
  • C++ Json解析CJsonObject的详细使用
  • C++编译错误杂记
  • 二分法（二）：采用二分法解决“最小化最大值问题”
  • C++实现json字符串与map的转换
  • C++借助curses库实现俄罗斯方块
  • 长乐培训Day5
  • 【OpenFOAM】——OpenFOAM入门算例学习

    • C++推荐文章

  • #8. 「模板」树链剖分
  • 预设型 DP
  • Standard Template Libary or C++ Standard Library
  • 一种优秀的虚拟机内存架构 - AQ
  • 如何让 MGR 不从 Primary 节点克隆数据？
  • TLScanary：Pwn中的利器
  • c++临时对象导致的生命周期问题
  • C++(Qt)-GIS开发-简易瓦片地图下载器
  • 逆向通达信 x 逆向微信 x 逆向Qt
  • C++面向对象

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号