AVL树的旋转

一、AVL树的概念

二、AVL树节点的定义

三、AVL树的插入

四、AVL树的旋转

4.1右单旋

4.2左单旋

4.3左右双旋

4.4右左双旋

五、AVL树的验证

六、AVL树的性能

一、AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
因此引入了AVL树：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树，或者是空树，或者是具有以下性质的二叉搜索树：它的左右子树都是AVL树，左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O(logN），搜索时间复杂度O(logN）

二、AVL树节点的定义

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;AVLTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};

三、AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。
AVL树的插入过程可以分为两步： ①按照二叉搜索树的方式插入新节点 ②调整节点的平衡因子

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 (parent->_right == cur){parent->_bf++;}else{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;}

1.插入的情况分为两种：

①在左树插入，父节点的平衡因子-1
②在右子树插入，父节点的平衡因子+1

2.插入后父节点平衡因子的变化有三种情况：

①插入后父节点的平衡因子为0，说明插入的节点填补了该棵子树低的那一端，使得该父节点的左右子树高度差相同，以父节点为根的树告诉不变，祖先不受影响，不用向上调整
②插入后父节点的平衡因子为1或者-1，说明插入前父节点的平衡因子一定为0，插入后被更新成正负1，此时以该父节点为根的树的高度增加，祖先受影响，需要继续向上更新
③ 如果父节点的平衡因子为正负2，则父节点的平衡因子违反平衡树的性质，需要对其进行旋转处理

四、AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

4.1右单旋

新节点插入较高左子树的左侧---左左：右单旋

右单旋的规则：当cur==-1，parent==-2时，cur的右子树给parent的左子树，parent再给cur的右子树，最后cur和parent的平衡因子全部置为0，完成调节

右单旋的可靠性：cur为parent的左子树节点，cur的右子树一定比parent小，parent的左子树一定比parent小，那么移动到parent的左子树是合理的；相反，cur的右子树一定比cur大，parent也一定比cur大，他们一起作为cur的右子树是合理的

下面列举不同高度下右单旋的实际情况：

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;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;
}

这里还要考虑更新完后各节点之间的链接关系：

如果cur的右子树为空，那么给parent的左子树也一定为空；
parent的父节点一定是cur
如果parent是根，那么调整完后cur就是根，cur的父节点就是空
如果parent不是根，那么要先保存parent的父节点，调整完后再让parent的父节点成为cur的父节点

4.2左单旋

新节点插入较高右子树的右侧---右右：左单旋

左单旋的规则：当cur==1，parent==2时，cur的左子树给parent的右子树，parent再给cur的左子树，最后cur和parent的平衡因子全部置为0，完成调节

左单旋的可靠性：cur为parent的右子树节点，cur的左子树一定比parent大，parent的右子树一定比parent小，那么移动到parent的右子树是合理的；相反，cur的左子树一定比cur小，parent也一定比cur小，他们一起作为cur的左子树是合理的

下面列举不同高度下左单旋的实际情况：

void RotateL(Node* parent)
{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->_right == parent){cur->_parent = ppnode;ppnode->_right = cur;}else{cur->_parent = ppnode;ppnode->_left = cur;}}parent->_bf = cur->_bf = 0;}

这里也要考虑更新完后各节点之间的链接关系：

如果cur的左子树树为空，那么给parent的右子树也一定为空；
parent的父节点一定是cur
如果parent是根，那么调整完后cur就是根，cur的父节点就是空
如果parent不是根，那么要先保存parent的父节点，调整完后再让parent的父节点成为cur的父节点

4.3左右双旋

新节点插入较高左子树的右侧---左右：先左单旋再右单旋

左右双旋的规则：

以parent->left（cur）为根进行左单旋，再以parent为根进行右单旋
更新平衡因子：①如果cur->right的平衡因子插入后为0，旋转结束后parent和cur的平衡因子都为0 ②如果cur->right的平衡因子插入后为-1，旋转结束后parent的平衡因子为-1，cur的平衡因子为0 ③如果cur->的平衡因子插入后为1，旋转结束后parent的平衡因子为0，cur的平衡因子为-1
左右单旋的本质：cur->right的左子树给cur的右子树，cur->right的右子树给parent的左子树，cur->right成为这棵树的根

下面列举不同高度下左右双旋的实际情况：

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

4.4右左双旋

新节点插入较高右子树的左侧---右左：先右单旋再左单旋

右左双旋的规则：

以parent->right（cur）为根进行右单旋，再以parent为根进行左单旋
更新平衡因子：①如果cur->left的平衡因子插入后为0，旋转结束后parent和cur的平衡因子都为0 ②如果cur->right的平衡因子插入后为-1，旋转结束后parent的平衡因子为0，cur的平衡因子为1 ③如果cur->的平衡因子插入后为1，旋转结束后parent的平衡因子为-1，cur的平衡因子为0
右左单旋的本质：cur->left的右子树给cur的左子树，cur->right的左子树给parent的右子树，cur->right成为这棵树的根

不同高度下左右双旋的实际情况参考右左单旋

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

单旋和双旋总结：假如以parent为根的子树不平衡，即parent的平衡因子为2或者-2，分以下情况考虑：
1. parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为cur，当cur的平衡因子为1时，执行左单旋；当cur的平衡因子为-1时，执行右左双旋
2. parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为cur，当cur的平衡因子为-1是，执行右单旋；当cur的平衡因子为1时，执行左右双旋
旋转完成后，原parent为根的子树个高度降低，已经平衡，不需要再向上更新。

五、AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

验证其为二叉搜索树，如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
验证其为平衡树，每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)，节点的平衡因子是否计算正确

int Height(Node* root)
{if (root == nullptr)return 0;int left = Height(root->_left);int right = Height(root->_right);return left > right ? left + 1 : right + 1;
}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 << ":" << rightheight-leftheight << "平衡因子异常：" << root->_bf << endl;}return abs(leftheight - rightheight) < 2 && IsBalance(root->_left) && IsBalance(root->_right);
}bool IsBalance()
{return IsBalance(_root);
}

验证是否为AVL树：首先看他的层序遍历是否为一个有序序列；其编写代码计算树的某个节点的左右高度和左右高度差，计算出来的该树的左右高度差再与该树的根节点中存的平衡因子进行比较，如果相同平衡因子的计算就是正确的，如果不同就说明平衡因子异常，逻辑有误。