C++——AVL平衡树-海口c网

我们之前已经讲解过了二叉搜索树了。知道它的基本特性后，这次，我们来认识一下AVL平衡树。

在此之前，我们先来想想目前为止，我们可以通过哪些方式来寻找一个数？（有些我们还没有学，大概率后面会更新，包括B树（如果我有时间学到的话，可作为拓展补充学习））

1.暴力搜索（pass掉，时间复杂度太大了）

2.二分查找：（但是有个问题：要求有序，而且伴随着插入删除，它的维护成本比较大）

3.二叉搜索树：（因为有些极端情况下会变成类似链表结构，也会导致它的效率极低，这也是为什么会出现平衡树的原因之一）

4.平衡树（包括AVL平衡树、红黑树）

5.多叉平衡树（B树系列）

6.哈希表

那么，我们现在就来了解一下关于本次的相关内容——AVL平衡树。

了解为什么出现AVL？

我们可以用下面的图来就可以明白：

我们可以看到，当作为极端情况的时候：这是不是就相当于类似链表的结构了，这也就相当于从有序的二叉搜索树退化为单支树了，而且查找元素相当于在顺序表中搜索元素了，效率大大降低。因此为了解决这种极端问题，俄国的两位数学家发明了这么一种方法：

当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

它的左右子树都是AVL树

左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在$O(log_2 n)$，搜索时间复杂度O($log_2 n$)

这么记录它的平衡因子呢？看下图：

一般都是按照：

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

现在，我们来计算一下时间复杂度：

满二叉树 2^h-1=N

AVL树 2^h-x=N

因为高度差的绝对值不超过1，所以：

x的范围是：[1,2^(h-1)-1]

那么2^h-1=N, 两边都除以2---->2^(h-1)=(N-1)/2

因此算得它们的时间复杂度都约等于logN。

那么，可能有人会有疑问：为什么它的高度的绝对值是不超过1呢？

事实上，最佳的平衡条件是每个节点左右子树有着相同的高度，但是，现实很残酷，这会对树的要求太苛刻了，现实我们生活中，很难能够保持插入新元素后，仍保持它们的高度保持平衡的条件，因此，通常会将它的条件退一步：即高度差绝对值不为1.

插入的问题：

现在我们来分析一下它插入过程中的几种情况：

ps：我们的平衡因子主要以这样的运算规则：

平衡因子=右子树-左子树；

上图说到平衡因子==2/-2时需要旋转的情况：

这里根据它的位置分为左旋转与右旋转：

左单旋：

（下面动图来自于网上浏览器）

上面是具体的数，那么当我们化为抽象的，看作一个整体的话是不是也是这样的一个规律呢？现在我们就来具体看看：

我们可以看到：它是一样可以适用的。

可能第一次看到上面的组合有点懵，确实这个是比较抽象的，我们我们不妨去画出具体的图来理解它：

像上面的话，你可以想想，a和b是三种情况都是可以的，并且都是不影响它们之间的。而c的话只能是z情况那种。如果它可以是x和y其中一种的话：就会出现平衡因子是3的情况了。

因此就得出了：插入之前的组合：3*3*1

插入情况是有4种的：两个都有左子树与右子树，一共是4.

所以一共的组合是：3*3*1*4=36种。

所以说这些情况组合是非常多的，我们不可能是完全一一列举出来的，只能通过抽象图来统一计算。

右单旋：

右单旋的情况：跟左单旋的本质是差不多的，只不过逻辑相反而已。

同样，我们来关于它们的组合：也是36种（左单旋那里已经很清楚了）。

接着更加复杂的情况：

双旋转：

我们经过上面的图分析：当插入的位置不同时，它得出的结果有时符合我们的预期，有时却不符合我们的预期。说明有些情况我们并不适合仅仅用单一的单旋来解决。那么我们该如何去解决呢？我们接着来分析：

好了，有了上面的分析，我们现在来模拟实现一下：

创建结点：

template<class K,class V>
struct AVTreeNode
{pair<K, V> _kv;AVTreeNode<K, V>* _left;AVTreeNode<K, V>* _right;AVTreeNode<K, V>* _parent;int bf;AVTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),bf(0){ }
};

1.这里我们使用KV键值模型。

2.通过上面的介绍，我们需要的成员有：键值对_kv，左指针_left,右指针_right，父亲_parent，平衡因子_bf.

3.对于为什么我们直接使用struct？我们之前就已经讲过了，因为后面我们会在它的类外使用到它们的成员，与其把它弄成public,不如直接利用struct默认是public的特性。来满足我们的需求。

4.构造函数进行初始化。把_kv置成kv，指针初始化成空，bf置0.

构造函数这块比较常规就不多讲解了。

AVLTree部分

构造类的成员变量
template<class K,class V>
class AVLTree
{typedef AVTreeNode<K, V> Node;
public:
private:Node* _root;
}
1.这里typedef一下，避免写得太长。

2.它的成员是_root根节点

构造函数

AVLTree():_root(nullptr){}

插入部分

bool insert(const pair<K, V>& kv)
{//找到插入的位置if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}//找到了插入cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//控制平衡因子while (parent){//新增节点在左子树，平衡因子就减减if (cur == parent->_left){parent->bf--;}//新增节点在右子树，平衡因子就加加else //if (cur == parent->_right){parent->bf++;}//如果当前父亲节点的平衡因子变成了0，说明它不会再影响到它祖先的节点了if (parent->bf == 0){break;}//当前父亲节点的平衡因子变为-1/1时，说明它是由原本的0变成的，这说明了，它必将                //会影响到它的祖先，所以需要向上更新它的平衡因子else if (parent->bf == 1 || parent->bf == -1){cur = parent;parent = parent->_parent;}//平衡因子变成了2后，说明需要旋转了。else if (parent->bf == 2 || parent->bf == -2){//需要旋转//左旋if (parent->bf == 2 && cur->bf == 1){RotateL(parent);  }//右旋else if (parent->bf == -2 && cur->bf == -1){RotateR(parent);}//先右旋再左旋else if (parent->bf == 2 && cur->bf == -1){RotateRL(parent);}//先左旋再右旋else if (parent->bf == -2 && cur->bf == 1){RotateLR(parent);}break;}else{assert(false);}}}

至于什么时候左旋？右旋？先左旋后右旋？先右旋再左旋？

我们可以看到最开始那里，按照图里的情况：来得出它的条件：

即：

左旋右旋

先右后左

先左再右

旋转部分：

左旋转

对着图写代码：不然特别容易错误！！！！

void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;	parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;//记录当前父亲的父亲节点，方便旋转后，cur的链接Node* ppnode = parent->_parent;parent->_parent = cur;// 1是prent，3是cur// //  1                    3//    3     ----->    1     5//       5//if (parent == _root)//出错点1if(ppnode==nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}//更新平衡因子parent->bf = cur->bf = 0;}

右旋转：

ps:看这图来写！！！！不然容易出错！！！！1

void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright){curright->_parent = parent;}cur->_right = parent;Node* ppnode = parent->_parent;parent->_parent = cur;// 1是prent，3是cur// //       1                  3//     3     ----->       5    1//  5if(ppnode==nullptr)//错误点1//if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->bf = cur->bf = 0;}

上面分析图里已经很详细了，这里就不多讲解了。

双旋转

先右再左

void RotateRL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->bf;RotateR(parent->_right);//写错了//RotateR(parent);RotateL(parent);if (bf == 0){cur->bf = 0;parent->bf = 0;curleft->bf = 0;}else if (bf == -1){cur->bf = 1;curleft->bf = 0;parent->bf = 0;}else if (bf == 1){parent->bf = -1;cur->bf = 0;curleft->bf = 0;}else{assert(false);}}

1.这里要看清楚你要旋转的是那个节点！！！

2.这里的旋转部分不是很大问题。反而更新平衡因子那里有难度问题。而我们这里直接通过观察法，直接强制更新了。

先左再右

void RotateLR(Node* parent){Node* cur = parent->_left;Node* ccurright = cur->_right;int bf = ccurright->bf;RotateL(parent->_left);RotateR( parent);if (bf == -1){parent->bf = 1;cur->bf = 0;ccurright->bf = 0;}else if (bf == 0){parent->bf = 0;cur->bf = 0;ccurright->bf = 0;}else if (bf == 1){cur->bf = -1;parent->bf = 0;ccurright->bf = 0;}else{assert(false);}}

同上解法。

其他情况自己推就可以知道了

那么，我们怎么知道，我们写的AVL树是否正确呢？有什么方法检验它的正确性呢？

这儿提供了一种方法来检验：

检验它的高度差：
    int Height(){return Height(_root);}int Height(Node* root){if (root == nullptr)return 0;int LeftHeight = Height(root->_left);int RightHeight = Height(root->_right);return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;}
检验是否平衡的方法：
bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;int leftheight = Height(root->_left);int rightheight = Height(root->_right);if (rightheight - leftheight != root->bf){cout << "平衡因子异常" << root->_kv.first << "->" << root->bf << " ";return false;}return abs(rightheight - leftheight) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);}
这里使用：我们使用的公式：平衡因子=右树高度-左树高度

若这个等式并不相等，说明错误了。即造成平衡因子异常。返回错误。

就这样层层递归检查。一旦发现错误立即返回false。

测试：

//int main()
//{
//	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
//	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
//	AVLTree<int, int> t;
//	for (auto& e : a)
//	{
//		//ֶϵ
//		if (e == 14)
//		{
//			int a = 0;
//		}
//		t.insert(make_pair(e,e));
//		cout << e << "->" << t.IsBalance() << endl;
//	}
//	return 0;
//}

上面还是有很大的偶然性的，所以我们这里使用大量的随机数来检验，减少误差：

int main()
{const int N = 10000;vector<int> v;v.reserve(N);srand(time(0));for (int i = 0; i < N; i++){v.push_back(i);}AVLTree<int, int> t;for (auto e : v){t.insert(make_pair(e, e));//cout << e << "->" << t.IsBalance() << endl;}cout << t.IsBalance() << endl;cout << t.Height() << endl;return 0;
}

好了，关于AVL平衡树就分析到这里了，希望大家都有所收获！