【C++】AVL树的4中旋转调整

---

前提

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查 找元素相当于在顺序表中搜索元素，效率低下。

因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决上述问题的方法：

当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(-1、0、1)，即可降低树的高度，从而减少平均搜索长度。
由此，该树被称为AVL树，即两位科学家名字的第一个字母。

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

• 它的左右子树都是AVL树
  
• 左右子树的高度差(简称平衡因子)的绝对值不超过1
  
  
  如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(logN)，搜索时间复杂度O(logN)。

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、AVL树的结构定义

树节点的结构创建：

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _kv;  //键值对来存储 K AND Vint _bf;//平衡因子//AVL树并没有规定必须要选择设计平衡因子，只是一个实现的选择，方便控制//构造函数AVLTreeNode(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;  //结点typedef 
public:
//......
private:Node* _root = nullptr;
};

二、AVL的插入（重点）

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。AVL树的插入过程可以分为两步：

• 按照二叉搜索树的方式插入新节点
• 调整节点的平衡因子
  （寻找位置->创建结点->插入节点->更新平衡因子->调整子树->形成AVL树）

---

1. 插入的结点在较高左子树的左侧（右单旋）

这样会造成parent的平衡因子变成-2， 当前节点（不是新增节点）的平衡因子变成-1

//右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}Node* pParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (pParent == nullptr){_root = subL;_root->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subL;}else pParent->_right = subL;subL->_parent = pParent;}// 更新平衡因子parent->_bf = subL->_bf = 0;}

2. 新节点插入较高右子树的右侧（左单旋）

这样会造成parent的平衡因子变成2，当前节点（不是新增节点）的平衡因子变成1

//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}Node* pParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (pParent == nullptr){_root = subR;_root->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subR;}else pParent->_right = subR;subR->_parent = pParent;}//更新平衡因子subR->_bf = parent->_bf = 0;}

3.新结点插入较高右子树的左侧（先右单旋再左单旋）

会造成parent的平衡因子变成2， 当前节点（不是新增节点）平衡因子变成-1

void RotateRL(Node* parent){Node* subR = parent->_right;  //左子树60Node* subRL = subR->_left;// 右子树的左子树90int bf = subRL->_bf;// 记录SubRLd 平衡因子// 先以SubR为轴进行右单旋RotateR(parent->_right);// 再进行左单旋RotateL(parent);if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else if (bf == 0){parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}else if (bf == 1){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else assert(0);}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else if (bf == -1){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 1){subL->_bf = -1;parent->_bf = 0;subLR->_bf = 0;}else assert(0);}

4. 新节点插入较高左子树的右侧（先左单旋再右单旋）

这样会造成parent的平衡因子变成-2， 当前结点的平衡因子变成1

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

---

插入的整体代码

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;//parent是cur的父节点Node* cur = _root;//cur往下走while (cur){if (cur->_kv.first > kv.first)//我比你小，往左找{parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first)//我比你大，往右找{parent = cur;cur = cur->_right;}else{return false;//AVL树不允许有重复值}}//走到这里就表示找到我们要插入kv值的正确位置了,准备插入节点..........cur = new Node(kv);if (parent->_kv.first < kv.first)//如果new的节点比父节点大，那么父节点的右指针指向new节点{parent->_right = cur;cur->_parent = parent;}else//如果new的节点比父节点小，那么父节点的左指针指向new节点{parent->_left = cur;cur->_parent = parent;}//开始更新平衡因子while (parent)//更新到根节点才算更新完平衡因子{//1、如果是右子树新增结点，那么父节点的_bf就加一//2、如果是左子树新增结点，那么父节点的_bf就减一//+1和-1大家可以自己决定，只要是对的，怎么都行！if (cur == parent->_right){parent->_bf++;}else{parent->_bf--;}// 是否继续更新依据：子树的高度是否变化// 1、parent->_bf == 0说明之前parent->_bf是 1 或者 -1// 说明之前parent一边高一边低，这次插入填上矮的那边，parent所在子树高度不变，不需要继续往上更新// 2、parent->_bf == 1 或 -1 说明之前是parent->_bf == 0，两边一样高，现在插入一边更高了，// parent所在子树高度变了，继续往上更新// 3、parent->_bf == 2 或 -2，说明之前parent->_bf == 1 或者 -1，现在插入严重不平衡，违反规则// 就地处理--旋转// 旋转：// 1、让这颗子树左右高度不超过1// 2、旋转过程中继续保持他是搜索树// 3、更新调整孩子节点的平衡因子// 4、让这颗子树的高度跟插入前保持一致//如果新增节点cur，使得父节点parent的平衡因子变成了0，那么表示该插入节点对整棵树的平衡因子没有影响//不用向上判断，可以直接退出if (parent->_bf == 0){break;}//如果新增cur使得父节点parent的平衡因子变成了1或者-1，那么我们要继续向上判断是否对上面的节点的//说明之前的平衡被打破，子树的高度变化了，有可能会造成父节点的平衡因子出现问题else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}//当平衡因子出现2 or -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)//左右旋{RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1)//右左旋{RotateRL(parent);}else{assert(false);}break;//旋转完一次就可以退出了，因为旋转的时候我们已经向上判断了，除非新插入，否则树就是avl树}else{assert(false);//这里直接报错，走到这里树就已经不是AVL树了}}return true;
}