C++ Avl_Tree

AVL树本质上是在搜索二叉树的情况下改造的

搜索二叉树的缺点是 最坏的时候效率太低

容易演变成链表

AVL树对搜索二叉树的这个痛点进行了改造

解决方案就是旋转

通过旋转AVL树可以做到左右每个子树高度可以不超过1

要了解旋转 我们首先要了解平衡因子

(1)平衡因子（balance factor）

后面都简称bf

平衡因子=右子树高度减去左子树高度

AVL树要求左右每个子树高度不超过1

也就意味着AVL树节点的平衡因子只有三种情况

0  -1  1

不可能是其他值

(2)插入的时平衡因子的变化

(1)插入的时候可能影响哪些节点的平衡因子？

会影响插入这个节点的所有祖先

(2)这些平衡因子怎么变化的？

插入左节点它的parent的平衡因子就要-1 

插入右节点它的parent的平衡因子就要＋1

(3)平衡因子怎么改变树的高度

parent这样 那么parent的parent 也就是grandparent平衡因子怎么办呢？

这个时候我们就要考虑parent的高度有没有变化了？

我们思考parent平衡因子以下这几种变化情况

平衡因子为1 意味着parent的右子树比左子树高度高1

平衡因子为-1 意味着parent的左子树比右子树高度高1

平衡因子为0意味着左子树和右子树高度相同

1. 1->0

2.0->1

3.0->-1

4.-1->0

我们发现上面这四种情况

只有2 3会改变树的高度而1 4不会改变树的高度 只会让树变得更平衡

也就意味着我们更新平衡因子 不一定要顺着往上把所有的祖先平衡因子更新

只用更新到 2 3两种情况就可以停止了 因为遇到2 3两种情况高度就不会改变

也就不会改变更上面的祖先  就可以停止了！！！

(3)平衡因子为2和-2怎么办？

这个时候就已经破坏了AVL树的结构了

我们就需要旋转了

旋转分为单旋和双旋

（1）单旋

单旋分为左单旋和右单旋 

我们先来看左单选是什么情况下

  

节点30平衡因子为2 也就意味着 

左树比右数要高2

那么如果我把左树高度-1 右树高度＋1 不就平衡了吗？

那这个时候我们旋转 

我们把平衡因子为2的节点设为parent 简称par(也就是上图的30)

那么它的 插入节点那侧  的子树的根设为current简称cur（也就是上图的60）

我们旋转要保证两件事

1.旋转后平衡因子绝对值小于等于1

2.旋转后依然符合搜索二叉树 右节点>根>左节点

左旋本质上是

把原本的cur变成了根

par以及它的左子树  变成了cur的左子树

cur的左子树（也就是较短的子树）变成了parent的右子树

而且单旋后cur和par 节点的平衡因子都为0

但是这个地方要注意的是什么？

我们这个AVL树是三叉链 分别为 left节点 right节点 parent三个节点

也就是我们实现代码的时候要去考虑parent的变化

root的parent节点为NULL

旋转首先如图可见 是不是平衡了

那么是否满足搜索二叉树呢？

旋转前 c>cur(60)>b>par(30)>a

旋转后   c>cur(60)>b>par(30)>a

旋转前后 这两个树 放到搜索二叉树那里 本质上原因就是我们插入的先后顺序不一样

这其实也侧面说明了

为啥搜索二叉树我们实现拷贝构造 是左子树右子树开空间构造

而不是说insert去构造 因为如果insert构造 你不同遍历方式结果是完全不一样的

我们说明了左旋和原理

既可以平衡

同时也可以不违背搜索二叉树

右单旋同理 这里就不详细介绍了

（2）双旋

双旋分为右左旋和左右旋 

我们先来看这种情况

我们可不可以只左旋？

够不够？

我们发现旋转后我们可以保持平衡但是破坏了搜索二叉树的性质！

这个地方需要的操作是双旋

我们以实际例子来示范 （右左旋）

当h==0的时候

我们第一步是 右旋 右旋结束后 就变成左旋可以解决的样子了 

h==1也是同理

 也就是

我们对这种情况b和c两个位置插入都解决了

是不是也意味着

下面这种情况在b和插入同理

不过是从左旋 和右左旋

变成了右旋 和左右旋 对嘛！！！ 

但是这个地方我们要考虑

单旋旋转结束cur和par的平衡因子都变成了0

但是双旋呢？

(4)双旋平衡因子变化

双旋就要复杂很多

涉及到三种情况

(1)第一种情况

此时par是30 cur是90 这个时候  60节点我们设为curleft

当curleft为-1时 旋转结束后

cur 的平衡因子变成了1

curleft的平衡因子变成了0

 par的平衡因子变成了0

(2)第二种情况

curleft为1时旋转后 cur的平衡因子为0 curleft的平衡因子为 0 par的平衡因子为-1

(3)第三种情况

curleft为0 旋转后 cur par curleft的平衡因子都是0 

对于左右旋同理 只不是考虑的不是curleft而是currightl了

最后思考一个问题

平衡因子可能是3吗？

如果你代码逻辑是对的 是不可能出现三的

为什么？

因为你每插入一次节点的平衡因子最多＋1

平衡因子要变成3 就意味着上一次插入结束的时候你的平衡因子就有2 

这个时候就说明你代码逻辑有问题

正常的AVL树调整后 节点的绝对值是小于2的

同样的AVL树也有它的缺点

就是旋转太频繁了

我们没必要要求这么严格的平衡 

如果说平衡因子我们可以允许是2 3 4等等 也许树的高度会增加

但是却可以大幅度减少旋转次数

提高时间复杂度

我们后面学的红黑树就是利用这种思路去改善搜索二叉树的！！！

最后代码奉上

#pragma once#include<iostream>
#include<assert.h>
using namespace std;template<class K, class V>
struct AVLTreeNode
{pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf;  // balance factorAVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public: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;// ... 控制平衡// 更新平衡因子while (parent){if (cur == parent->_left){parent->_bf--;}else // if (cur == parent->_right){parent->_bf++;}if (parent->_bf == 0){// 更新结束break;}else if (parent->_bf == 1 || parent->_bf == -1){// 继续往上更新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){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}break;}else{assert(false);}}return true;}void RotateL(Node* parent){++_rotateCount;Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;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 RotateR(Node* parent){++_rotateCount;Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright)curright->_parent = parent;Node* ppnode = parent->_parent;cur->_right = parent;parent->_parent = cur;if (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;}void RotateRL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){cur->_bf = 0;curleft->_bf = 0;parent->_bf = 0;}else if (bf == 1){cur->_bf = 0;curleft->_bf = 0;parent->_bf = -1;}else if (bf == -1){cur->_bf = 1;curleft->_bf = 0;parent->_bf = 0;}else{assert(false);}}void RotateLR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){parent->_bf = 0;cur->_bf = 0;curright->_bf = 0;}else if (bf == -1){parent->_bf = 1;cur->_bf = 0;curright->_bf = 0;}else if (bf == 1){parent->_bf = 0;cur->_bf = -1;curright->_bf = 0;}}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 leftHight = Height(root->_left);int rightHight = Height(root->_right);if (rightHight - leftHight != root->_bf){cout << "平衡因子异常:" <<root->_kv.first<<"->"<< root->_bf << endl;return false;}return abs(rightHight - leftHight) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);}private:Node* _root = nullptr;public:int _rotateCount = 0;
};