【数据结构】AVLTree实现详解

目录

一.什么是AVLTree

二.AVLTree的实现 

1.树结点的定义 

2.类的定义

3.插入结点 

①按二叉搜索树规则插入结点

②更新平衡因子

更新平衡因子情况分析 

③判断是否要旋转 

左单旋 

右单旋 

左右单旋

右左双旋

4.删除、查找和修改函数 

查找结点

三.测试 

1.判断是否是搜索树

2.判断每一个结点的左右子树高度差是否不大于1

四.所有源代码

AVLTree.h

Test.c

在本篇博客中，作者将会使用C++来带领你理解和实现AVLTree，同时，在学习AVLTree之

前，你可以先看看下面这篇二叉搜索树的博客，因为AVTree也是一种二叉搜索树，它们有一些规则是一样的。

【C++】二叉搜索树-CSDN博客

一.什么是AVLTree

在二叉搜索树的博客中，我们提到了，当插入的数据有序或者接近有序的时候，二叉搜索树会退化成单支树，导致其效率变低，所以为了解决这种情况，于是我们提出了AVLTree，即二叉平衡搜索树。 

---

如下图就是一棵二叉搜索树退化成的单支树。 

---

那么AVLTree又是如何实现使二叉树搜索树不会退化成单支树的呢，它又是如何保证效率的呢？

因为AVLTree严格的要求左右子树的高度差不能大于1，且每一棵子树也一样。 如下图所示。

通过这样严格的高度差要求，该树就可以达到一个非常平衡的状态，以致于它的插入、删除、查找等操作的效率非常的高，其时间复杂度就是O（logN）,N为结点的个数。 

---

那么它又是如何实现这样的要求的？

前面说了，AVLTree保证了每个结点的左右子树的高度差不大于1，那是因为当有一个结点的左右子树高度差为2时，它会进行旋转，使其保证平衡，至于怎么旋转，我们接着往下看。 

二.AVLTree的实现 

知道了AVLTree的规则，那么我们就可以来实现一下AVLTree了。 

1.树结点的定义 

在树结点的定义中，对比平常的二叉树，多了两个变量，一个是父结点的指针_parent，一个是_bf平衡因子。

其中_parent指针是方便我们在后续的操作中，去倒着往上去找父结点。

_bf平衡因子是存储该结点的左右子树的高度差，这里默认为右子树的高度减去左子树的高度，通过_bf平衡因子，我们可以很快的知道该结点下的树是否平衡。

	template<class T>struct TreeNode{//成员变量T _data;//树结点存储的数据类型TreeNode<T>* _left;//左孩子指针TreeNode<T>* _right;//右孩子指针TreeNode<T>* _parent;//父结点指针int _bf;//平衡因子//成员函数TreeNode(cosnt T& tmp)//构造函数:_data(tmp), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}};

对于平衡因子来说，如下图所示。

_bf平衡因子=右子树的高度 - 左子树的高度 

当_bf平衡因子的绝对值大于1时，说明该结点的左右子树高度差大于1，这个时候需要进行旋转处理。如下图所示。 

2.类的定义

对于类的定义，就比较简单，就是一个_root指针指向根节点。 

	template<class T>class AVLTree{typedef TreeNode<T> Node;public://构造函数AVLTree():_root(nullptr){}private:Node* _root;//根节点的指针};

3.插入结点 

对于AVLTree来说，最重要的就是插入结点，同时，这也是比较难的一部分，代码也比较长，但是不要怕，我们把AVLTree的插入分成如下几个部分。 

1.先按二叉搜索树的规则插入结点，就是先不管三七二十一，先把结点插入进去再说。

        至于二叉搜索树的插入，可以看开头的博客链接。

2.更新平衡因子，插入新结点后会影响平衡因子，所以插入新结点后，要更新平衡因子。

3.判断是否要旋转，更新完平衡因子后，要判断直接结束了还是要进行旋转调整。

---

接下来我们要把上面的三个过程转换成代码，这里代码会有点长，我们把这个insert函数分成三部分来说。如下是这个函数的函数名和参数。tmp为要插入的值。

		bool insert(const T& tmp)

①按二叉搜索树规则插入结点

对于这一部分来说，没那么难，整个插入过程如下图所示。

就是用tmp从根结点开始进行比较，一直往下找空位，找到空位后，再把结点插入进去。

---

			//如果根节点为空，则直接插入if (_root == nullptr){_root = new Node(tmp);return true;}//如果根节点不为空，则先按二叉搜索树的规则进行插入Node* cur = _root;Node* cur_parent = nullptr;while (cur != nullptr)//往下找空位{if (tmp > cur->_data){cur_parent = cur;cur = cur->_right;}else if (tmp < cur->_data){cur_parent = cur;cur = cur->_left;}else{return false;}}//找到空位后，给空位一个新结点cur = new Node(tmp);if (cur->_data > cur_parent->_data){cur_parent->_right = cur;cur->_parent = cur_parent;}else{cur_parent->_left = cur;cur->_parent = cur_parent;}

②更新平衡因子

插入完结点后， 我们要更新平衡因子，那么怎么更新呢，我们往下看。

首先，当插入一个新结点的时候，只会影响新结点一路往上的_parent结点。如下图所示。

所以当我们更新平衡因子的时候，只需要通过_parent指针，一路向上更新即可，但是也不一定一直更新到根节点，为什么呢？我继续往下看。 

---

既然是更新平衡因子，那么怎么个更新呢？

在开头，我们提到_bf平衡因子 = 右子树的高度 - 左子树的高度。

那么看上图，cur为新结点，cur_parent为cur的父结点，对于cur_parent来说，它的左子树新增了一个结点，也就是说左子树的高度+1，所以对于_bf = 右子树高度 - 左子树高度这个公式来说，左子树高度+1，即_bf-1，如果cur是cur_parent的右子树反之+1。这里可能会很乱，没事，我们来看下图。

当更新完一个结点的平衡因子的时候，这个时候会有三种情况：

1.更新完该结点后，会影响向上的父结点，继续更新。

2.更新完该结点后，不会影响向上的父结点，更新结束。

3.更新完该结点后，该结点的平衡因子==2或==-2，此时需要进行旋转处理。

整个过程的代码如下。  

			//插入完结点后，要更新平衡因子while (cur_parent != nullptr){if (cur_parent->_right == cur)//说明新增结点是cur_parent的右子树，即右子树高度增加1{cur_parent->_bf++;}else{cur_parent->_bf--;}if (cur_parent->_bf == 0)//如果cur_parent的平衡因子为0，结束更新{break;}else if (cur_parent->_bf == 1 || cur_parent-> == -1)//如果cur_parent的平衡因子为1或者-1，则继续向上更新{cur = cur_parent;cur_parent = cur_parent->_parent;}else if (cur_parent->_bf == 2 || cur_parent->_bf == -2){//进行旋转处理}

更新平衡因子情况分析 

更新完后，为什么平衡因子==0就停止更新，==1或者==-1要继续向上更新？

我们来分析一下。首先来看==0情况。如下图所示

我们插入20，插入后结点15的平衡因子要更新为0，

 

从图中，我们可以轻易的看出对于结点10来说，它的平衡因子是不受影响的，那么是为什么呢？

因为树的高度是由高的子树来决定的，对于结点10来说，它的高的子树是（15~12）这个两个结点构成的子树，而新增的结点20没有增加到高的子树上去，所以对于结点10来说，高度没变。如下图所示。

 

接下来看看==1或者==-1的情况，

首先是一棵正常的树，我们插入新结点20，插入后，结点18的平衡因子要变为1，

 

因为结点18的平衡因子为1，所以要继续向上更新，为什么呢？

解释与上面那种情况类似，当一个结点的平衡因子由0变为1或者-1的时候，说明该结点的高度增加了1，说明该结点的子树高度增加了1，这个时候会影响上面结点的高度，所以平衡因子要一直向上更新。 

③判断是否要旋转 

至于当平衡因子==2或者==-2的时候，要进行旋转处理就没什么好说的了，因为AVLTree就是严格的要求平衡因子的绝对值不能大于2。 

---

那么旋转又是怎么旋转的呢？

旋转又可以分为四种情况：左单旋，右单旋，左右双旋，右左双旋。

我们来分析一下。 

左单旋 

当一个结点的_bf为2，且它的右孩子的_bf为1时，要进行左单旋。 如下图所示 

 旋转完后，如下图所示。

对于左单旋的所有情况，我们可以用下面这两个抽象图来表示所有情况。

 

进行旋转处理后，如下图所示。

 

对于整个旋转过程来说，就是去改变cur_parent和cur结点的指针关系。

cur_parent的右指针，去指向cur的左子树，

cur的左指针，去指向cur_parent，

注意，这里还要改变cur_parent和cur结点的_parent指针。

---

但是这里注意的时，cur_parent不一定如上图所示为根结点，它有可能是某个结点的子树，如下图所示。 

  

所以旋转完成后还要进行一次判断，是否需要将cur结点链接到上一个结点。

		//左单旋	void RotateL(Node* cur_parent){Node* cur = cur_parent->_right;Node* cur_left = cur->_left;//改变指针的链接关系cur_parent->_right = cur_left;if (cur_left != nullptr){cur_left->_parent = cur_parent;}cur->_left = cur_parent;Node* cur_parent_parent = cur_parent->_parent;//提前保存cur_parent的父结点cur_parent->_parent = cur;//旋转完成后要判断cur_parent是否为根if (cur_parent_parent != nullptr)//说明cur_parent不是根{if (cur_parent_parent->_data < cur_parent->_data){cur_parent_parent->_right = cur;cur->_parent = cur_parent_parent;}else{cur_parent_parent->_left = cur;cur->_parent = cur_parent_parent;}}else//说明cur_parent是根{_root = cur;cur->_parent = nullptr;}//旋转完成后，平衡因子调整为0cur_parent->_bf = cur->_bf = 0;}

右单旋 

同样的右单旋与左单旋类似，只不过是反过来而已，这里不再做过多的解释，只给出抽象图出来。 

经过右单旋后，变成如下图所示。

		//右单旋void RotateR(Node* cur_parent){Node* cur = cur_parent->_left;Node* cur_right = cur->_right;cur_parent->_left = cur_right;if (cur_right != nullptr){cur_right->_parent = cur_parent;}cur->_right = cur_parent;Node* cur_parent_parent = cur_parent->_parent;cur_parent->_parent = cur;if (cur_parent_parent != nullptr){if (cur_parent_parent->_data > cur_parent->_data){cur_parent_parent->_left = cur;cur->_parent = cur_parent_parent;}else{cur_parent_parent->_right = cur;cur->_parent = cur_parent_parent;}}else{_root = cur;cur->_parent = nullptr;}cur_parent->_bf = cur->_bf = 0;}

左右单旋

左单旋和右单旋解释完成后，接下来要将双旋了，那么什么情况下要用双旋呢？

我们来看一下抽象图 

当新插入结点时，如果符合上图中的情况，则要进行左右双旋操作，注意！！！新增的红色结点也有可能插入在结点15的右树，其旋转过程就是先对结点10进行一个左单旋，再对结点20进行一个右单旋。如下图所示。

先对结点10进行一个左单旋，再对结点20进行一个右单旋。 

---

但是上面这个抽象图不能代表双旋的所有情况，因为双旋有一种特殊的情况，如下图所示。

对于这种特殊情况，我们只需要先前保存cur_right的平衡因子，双旋完成后，如果平衡因子为0，说明就是这种特殊情况，再进行特殊处理即可。 

		//左右双旋void RotateLR(Node* cur_parent){Node* cur = cur_parent->_left;Node* cur_right = cur->_right;int bf = cur_right->_bf;//这里保存平衡因子的原因是，新增的结点有可能插入在左树，也有可能插入在右树，通过保存平衡因子来进行判断是哪一种情况//先对cur进行一个左单旋RotateL(cur);//再对cur_parent进行一个右单旋RotateR(cur_parent);//旋转完成后，要更新平衡因子if (bf == -1)//说明新增的结点是插入在左树{cur->_bf = 0;cur_parent->_bf = 1;cur_right->_bf = 0;}else if (bf == 1)//说明新增的结点是插入在右树{cur->_bf = -1;cur_parent->_bf = 0;cur_right->_bf = 0;}else if (bf == 0)//特殊情况{cur->_bf = 0;cur_parent->_bf = 0;cur_right->_bf = 0;}}

右左双旋

对于右左双旋来说，与左右单旋类似，就是换了个方向而已，这里不再过多的解释，直接给出抽象图和代码。

先进行一个右单旋，再进行一个左单旋，旋转如下图所示。 

 同样的，这里也要处理特殊情况，就不在过多的解释。

		//右左双旋void RotateRL(Node* cur_parent){Node* cur = cur_parent->_right;Node* cur_left = cur->_left;int bf = cur_left->_bf;//先对cur进行一个右单旋RotateR(cur);//再对cur_parent进行一个左单旋RotateL(cur_parent);//更新平衡因子if (bf == -1){cur->_bf = 1;cur_parent->_bf = 0;cur_left->_bf = 0;}else if (bf == 1){cur->_bf = 0;cur_parent->_bf = -1;cur_left->_bf = 0;}else if (bf == 0){cur->_bf = 0;cur_parent->_bf = 0;cur_left->_bf = 0;}}

走到这一步，我们的旋转代码就已经全部写好了，接下来可以接着补充我们的插入函数的旋转部分。 

		bool insert(const T& tmp){//如果根节点为空，则直接插入if (_root == nullptr){_root = new Node(tmp);return true;}//如果根节点不为空，则先按二叉搜索树的规则进行插入Node* cur = _root;Node* cur_parent = nullptr;while (cur != nullptr)//往下找空位{if (tmp > cur->_data){cur_parent = cur;cur = cur->_right;}else if (tmp < cur->_data){cur_parent = cur;cur = cur->_left;}else{return false;}}//找到空位后，给空位一个新结点cur = new Node(tmp);if (cur->_data > cur_parent->_data){cur_parent->_right = cur;cur->_parent = cur_parent;}else{cur_parent->_left = cur;cur->_parent = cur_parent;}//插入完结点后，要更新平衡因子while (cur_parent != nullptr){if (cur_parent->_right == cur){cur_parent->_bf++;}else{cur_parent->_bf--;}if (cur_parent->_bf == 0){break;}else if (cur_parent->_bf == 1 || cur_parent->_bf == -1){cur = cur_parent;cur_parent = cur_parent->_parent;}else if (cur_parent->_bf == 2 || cur_parent->_bf == -2){//进行旋转处理if (cur_parent->_bf == 2){if (cur->_bf == 1)//左单旋{RotateL(cur_parent);}else if(cur->_bf == -1)//右左双旋{RotateRL(cur_parent);}}else if (cur_parent->_bf == -2){if (cur->_bf == 1)//左右单旋{RotateLR(cur_parent);}else if (cur->_bf == -1)//右单旋{RotateR(cur_parent);}}break;}}return true;}

写到这里，我们的插入代码就完成了，这也是AVLTree实现的最核心的部分。

4.删除、查找和修改函数 

对于一个数据结构来说，最基本的操作是增删改查，现在增已经实现了，那么还有剩下的三个函数。 

删除：

        对于AVLTree的删除来说，情况比插入还稍许复杂，又由于博主的能力和精力有限，在这里就不讲了。

查找：

        对于AVLTree的查找来说，就显得很简单，跟二叉搜索树的查找一样，就不过多的解释，等下下面直接给出代码。

修改：

        对于AVLTree的修改来说，一般来说，是不允许修改的，因为AVLTree是一种搜索树，它的中序遍历是绝对的有序的，如果进行修改，就会破坏整棵树的性质，导致不再是搜索树，但是也有允许修改的情况，当树中存的是一个pair键值对，我们可以对pair键值对的val进行修改，具体解释，参考这篇博客中的kv模型【C++】二叉搜索树-CSDN博客

查找结点

		//查找结点Node* find(const T& tmp){Node* cur = _root;while (cur != nullptr){if (tmp > cur->_data){cur = cur->_right;}else if (tmp < cur->_data){cur = cur->_left;}else{return cur;}}return nullptr;}

三.测试 

既然我们的插入已经完成了，那么我们又如何判断我们写的代码是对的呢，接下来讲一下如何测试我们写的AVLTree。 

1.判断是否是搜索树

既然是AVLTree，那么它一定是一棵搜索树，所以它的中序遍历一定是有序的，所以我们可以写一个中序遍历来看看是否是搜索树。

		//中序遍历void InOrder(){Node* cur = _root;_InOrder(cur);}//中序遍历的子函数void _InOrder(Node* cur){if (cur == nullptr)return;_InOrder(cur->_left);cout << cur->_data << " ";_InOrder(cur->_right);}

2.判断每一个结点的左右子树高度差是否不大于1

判断完了确定是搜索树，接下来就要判断是否是AVLTree树，即每一个结点的左右子树高度差都不大于1。

---

首先，我们可以先写一个求树的高度的函数。 

		//求树的高度int height(Node* cur){if (cur == nullptr)return 0;//返回左右子树高的那一个子树+1，fmax是库函数，求两个参数的较大值return fmax(height(cur->_left), height(cur->_right)) + 1;}

然后就可以写一个判断是否平衡的函数。 

		//判断是否平衡bool JudgeBanlance(){Node* cur = _root;return _JudgeBanlance(cur);}//判断是否平衡的子函数bool _JudgeBanlance(Node* cur){if (cur == nullptr)return true;int left_height = height(cur->_left);//求cur左子树的高度int right_height = height(cur->_right);//求cur右子树的高度//abs是求左右子树高度差的绝对值return abs(left_height - right_height) < 2&& _JudgeBanlance(cur->_left)&& _JudgeBanlance(cur->_right);}

---

 写到这里，我们的判断是否是AVLTree也完成了，AVLTree也基本实现了。

四.所有源代码

AVLTree.h

#pragma once
#include<iostream>
#include<time.h>
using namespace std;
//编写一篇博客
namespace blog_AVLTree
{template<class T>struct TreeNode{//成员变量T _data;//树结点存储的数据类型TreeNode<T>* _left;//左孩子指针TreeNode<T>* _right;//右孩子指针TreeNode<T>* _parent;//父结点指针int _bf;//平衡因子//成员函数TreeNode(const T& tmp)//构造函数:_data(tmp), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}};template<class T>class AVLTree{typedef TreeNode<T> Node;public:AVLTree():_root(nullptr){}//插入bool insert(const T& tmp){//如果根节点为空，则直接插入if (_root == nullptr){_root = new Node(tmp);return true;}//如果根节点不为空，则先按二叉搜索树的规则进行插入Node* cur = _root;Node* cur_parent = nullptr;while (cur != nullptr)//往下找空位{if (tmp > cur->_data){cur_parent = cur;cur = cur->_right;}else if (tmp < cur->_data){cur_parent = cur;cur = cur->_left;}else{return false;}}//找到空位后，给空位一个新结点cur = new Node(tmp);if (cur->_data > cur_parent->_data){cur_parent->_right = cur;cur->_parent = cur_parent;}else{cur_parent->_left = cur;cur->_parent = cur_parent;}//插入完结点后，要更新平衡因子while (cur_parent != nullptr){if (cur_parent->_right == cur){cur_parent->_bf++;}else{cur_parent->_bf--;}if (cur_parent->_bf == 0){break;}else if (cur_parent->_bf == 1 || cur_parent->_bf == -1){cur = cur_parent;cur_parent = cur_parent->_parent;}else if (cur_parent->_bf == 2 || cur_parent->_bf == -2){//进行旋转处理if (cur_parent->_bf == 2){if (cur->_bf == 1)//左单旋{RotateL(cur_parent);}else if(cur->_bf == -1)//右左双旋{RotateRL(cur_parent);}}else if (cur_parent->_bf == -2){if (cur->_bf == 1)//左右单旋{RotateLR(cur_parent);}else if (cur->_bf == -1)//右单旋{RotateR(cur_parent);}}break;}}return true;}//查找结点Node* find(const T& tmp){Node* cur = _root;while (cur != nullptr){if (tmp > cur->_data){cur = cur->_right;}else if (tmp < cur->_data){cur = cur->_left;}else{return cur;}}return nullptr;}//中序遍历void InOrder(){Node* cur = _root;_InOrder(cur);}//求树的高度int height(Node* cur){if (cur == nullptr)return 0;return fmax(height(cur->_left), height(cur->_right)) + 1;}//判断是否平衡bool JudgeBanlance(){Node* cur = _root;return _JudgeBanlance(cur);}private://左单旋	void RotateL(Node* cur_parent){Node* cur = cur_parent->_right;Node* cur_left = cur->_left;//改变指针的链接关系cur_parent->_right = cur_left;if (cur_left != nullptr){cur_left->_parent = cur_parent;}cur->_left = cur_parent;Node* cur_parent_parent = cur_parent->_parent;cur_parent->_parent = cur;//旋转完成后要判断cur_parent是否为根if (cur_parent_parent != nullptr)//说明cur_parent不是根{if (cur_parent_parent->_data < cur_parent->_data){cur_parent_parent->_right = cur;cur->_parent = cur_parent_parent;}else{cur_parent_parent->_left = cur;cur->_parent = cur_parent_parent;}}else//说明cur_parent是根{_root = cur;cur->_parent = nullptr;}//旋转完成后，平衡因子调整为0cur_parent->_bf = cur->_bf = 0;}//右单旋void RotateR(Node* cur_parent){Node* cur = cur_parent->_left;Node* cur_right = cur->_right;cur_parent->_left = cur_right;if (cur_right != nullptr){cur_right->_parent = cur_parent;}cur->_right = cur_parent;Node* cur_parent_parent = cur_parent->_parent;cur_parent->_parent = cur;if (cur_parent_parent != nullptr){if (cur_parent_parent->_data > cur_parent->_data){cur_parent_parent->_left = cur;cur->_parent = cur_parent_parent;}else{cur_parent_parent->_right = cur;cur->_parent = cur_parent_parent;}}else{_root = cur;cur->_parent = nullptr;}cur_parent->_bf = cur->_bf = 0;}//左右双旋void RotateLR(Node* cur_parent){Node* cur = cur_parent->_left;Node* cur_right = cur->_right;int bf = cur_right->_bf;//先对cur进行一个左单旋RotateL(cur);//再对cur_parent进行一个右单旋RotateR(cur_parent);//旋转完成后，要更新平衡因子if (bf == -1){cur->_bf = 0;cur_parent->_bf = 1;cur_right->_bf = 0;}else if (bf == 1){cur->_bf = -1;cur_parent->_bf = 0;cur_right->_bf = 0;}else if (bf == 0)//特殊情况{cur->_bf = 0;cur_parent->_bf = 0;cur_right->_bf = 0;}}//右左双旋void RotateRL(Node* cur_parent){Node* cur = cur_parent->_right;Node* cur_left = cur->_left;int bf = cur_left->_bf;//先对cur进行一个右单旋RotateR(cur);//再对cur_parent进行一个左单旋RotateL(cur_parent);//更新平衡因子if (bf == -1){cur->_bf = 1;cur_parent->_bf = 0;cur_left->_bf = 0;}else if (bf == 1){cur->_bf = 0;cur_parent->_bf = -1;cur_left->_bf = 0;}else if (bf == 0){cur->_bf = 0;cur_parent->_bf = 0;cur_left->_bf = 0;}}//中序遍历的子函数void _InOrder(Node* cur){if (cur == nullptr)return;_InOrder(cur->_left);cout << cur->_data << " ";_InOrder(cur->_right);}//判断是否平衡的子函数bool _JudgeBanlance(Node* cur){if (cur == nullptr)return true;int left_height = height(cur->_left);//求cur左子树的高度int right_height = height(cur->_right);//求cur右子树的高度return abs(left_height - right_height) < 2&& _JudgeBanlance(cur->_left)&& _JudgeBanlance(cur->_right);}private:Node* _root;};void Test1(){AVLTree<int> root;//int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){root.insert(arr[i]);}root.InOrder();cout << root.JudgeBanlance() << endl;}void Test2(){srand(time(0));AVLTree<int> root;const int n = 100;for (int i = 0; i < n; i++){root.insert(rand());}root.InOrder();cout << root.JudgeBanlance() << endl;}
}

Test.c 

#include"AVLTree.h"int main()
{blog_AVLTree::Test1();//blog_AVLTree::Test2();return 0;
}