手撕AVL树（map和set底层结构）(1)

troop主页
今日鸡汤：Action may out always bring happiness;but there is no happiness without action.
行动不一定能带来快乐，但不行动一定不行
C++之路还很长

手撕AVL树

一 AVL树概念
二模拟实现AVL树
- 2.1 AVL节点的定义
三插入
- 更新平衡因子（重点）
四旋转
- 1.左单旋
- 1.1 左单旋完整代码
- 2 右单旋
- 2.2 右单旋完整代码
- 3 双旋一（左+右）
- 3.2左右双旋完整代码
- 4 双旋二（右+左）
- 4.2 右左双旋完整代码
旋转总结
五验证AVL树的正确性

一 AVL树概念

二叉搜索树虽然可以缩短查找的效率，但是当数接近有序或者二叉搜索数接近单支树，查找的效率就相当于在顺序表中查找。所以为了解决这种极端环境，，两位俄罗斯的数学家G.M.Adelson-Velskii
和E.M.Landis在1962年发明了一种解决上述问题的方法：
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
AVL树的性质

他的左右子树都是AVL树
左右子树的高度差（平衡因子）的绝对值不超过1
注（以下代码中，平衡因子=|右子树高度-左子树高度|）

二模拟实现AVL树

2.1 AVL节点的定义

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf; // balance factorpair<K, V> _kv;AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv){}
};

三插入

我们这里AVL只写插入，插入就可以让我们很好的了解AVL的底层实现了。
AVL树也是二叉搜索树，只是在此基础上增加了平衡因子的调整。所以我们的插入就分成了两部分。

按照二叉搜索树的规则插入
更新平衡因子

	bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;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;

这个就是我们前面已经说过的二叉搜索树的插入规则。现在我们重点看如何更新平衡因子。

更新平衡因子（重点）

平衡因子更新原则：

cur插入在parent的左边平衡因子减减
cur插入在parent的右边平衡因子加加

思考：插入节点后会影响哪些节点的平衡因子？
会影响新插入节点的部分祖先。
是否影响爷爷节点取决于parent的高度是否有变化
首先父亲节点一定会被影响，其次重点考虑的应该是爷爷节点所受的影响。这里比较抽象我们需要借助图像来把每一种可能写出来。
第一种更新后p->_bf0
在这里插入图片描述
这种就是更新之前p的高度为1or-1，新节点插入在了比较矮的那一端，左右平衡。
第二种更新后p->_bf1or-1

更新之前，p的高度平衡，cur插入在一侧，p不平衡了，这里p的高度变化爷爷节点也受到了影响，就需要向上更新。
第三种更新后p->_bf==2or-2
在这里插入图片描述
违反了AVL树的规则要进行旋转。
我们现在总结一下，什么情况下更新就结束了。

1.插入后父亲的平衡因子为0，更新结束
2.向上更新到，cur=root的位置时，更新结束
3.违反规则需要旋转，旋转之后，更新结束

		//调整平衡因子while (parent){if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}//情况一if (parent->_bf == 0){break;}//情况二else if (parent->_bf == 1 || parent->_bf == -1){cur = cur->_parent;parent = parent->_parent;}//情况三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){RotateLR(parent);}else{RotateRL(parent);}break;}//插入树之前这个树就不符合AVL树else{// 插入之前AVL树就有问题assert(false);}

这部分代码还比较简单，下面就是本篇核心（旋转）

四旋转

旋转的目的

保持搜索树规则
当先树由不平衡转变为平衡
降低树的高度

1.左单旋

在这里插入图片描述
根据上面的图我们写出下代码。

Node* subR=panret->_right;
Node* subRL=subR->_left;parent->_right=subRl;
subRL->_parent=parent;subR->_left=parent;
parent->_parent=subR;

这里还有几个细节问题需要注意
第一点：subRL可能为空，那subRL->_parent=parent;就会有问题。我们要加一个条件判断。
第二点：subR的父亲节点还没有被重新指向，这就会导致下图
在这里插入图片描述
我们就要先保存parent的父亲节点，这又有了一个新的问题，就是parent是不是根节点，所以左单旋的完整代码如下

1.1 左单旋完整代码

void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}parent->_bf = 0;subR->_bf = 0;}

2 右单旋

右单旋就是左旋的变形，理解好左旋，右旋就很好理解了。
在这里插入图片描述
看图写出代码，再根据左旋的注意事项，补全代码的逻辑。

2.2 右单旋完整代码

void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}subL->_bf = 0;parent->_bf = 0;}

3 双旋一（左+右）

在这里插入图片描述

注意看图，先对subL进行了左单旋，再对整棵树进行了右单旋。
注意：双旋对比单旋多了旋转结束之后平衡因子不是固定的，我们要风分情况把所有的可能性都写出来。
在这里插入图片描述
观察上图，我们发现subRL的平衡因子不同分别为：-1 1 0，这就是我们的解决方案。我们再画出旋转之后的图片。

分析完之后，就到了最简单的代码环节

3.2左右双旋完整代码

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

4 双旋二（右+左）

在这里插入图片描述

还是先画出一般图观察，对subR进行右旋，再对整体左旋。
下面的分析与上面的分析类似，我就把图片放在下面，供大家参考。
在这里插入图片描述

4.2 右左双旋完整代码

void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;}else{parent->_bf = 0;subR->_bf = 0;}}

现在再去看上面的更新平衡因子的代码就比较清晰了。

旋转总结

左旋：新节点插入了较高右子树的右侧
右旋：新节点插入了较高左子树的左侧
双旋：
左+右：新节点插入了较高左子树的右侧
右+左：新节点插入了较高右子树的左侧

总之一句话：理解旋转我们一定要自己去画图，一定要自己动手，才会理解深刻。

五验证AVL树的正确性

我们要写一个函数来判断这颗树符不符合AVL树。

	bool _IsBalance(Node* root, int& height){if (root == nullptr){height = 0;return true;}int leftHeight = 0, rightHeight = 0;if (!_IsBalance(root->_left, leftHeight)|| !_IsBalance(root->_right, rightHeight)){return false;}if (abs(rightHeight - leftHeight) >= 2){cout << root->_kv.first << "不平衡" << endl;return false;}if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;return true;}