【C++】AVL树的两单旋和两双旋

本文主要是介绍【C++】AVL树的两单旋和两双旋，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

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

代码

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

 代码

3. 新节点插入较高左子树的右侧---左右：先左单旋再右单旋 ​编辑

代码 

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

​编辑代码 

---

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

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

a/b/c分别是高度为h的AVL子树

  上图在插入前，AVL树是平衡的，新节点插入到30的左子树(注意：此处不是左孩子)中，30左子树增加了一层，导致以60为根的二叉树不平衡，要让60平衡，只能将60左子树的高度减少一层，右子树增加一层，即将左子树往上提，这样60转下来，因为60比30大，只能将其放在30的右子树，而如果30有右子树，右子树根的值一定大于30，小于60，只能将其放在60的左子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：
1. 30节点的右孩子可能存在，也可能不存在
2. 60可能是根节点，也可能是子树
如果是根节点，旋转完成后，要更新根节点
如果是子树，可能是某个节点的左子树，也可能是右子树
 

代码

//右单旋
void RotateR(Node* parent)
{Node* SubL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subL->_right = 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;}parent->_bf = 0;subL->_bf = 0;
}

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

 

 左单旋与右单旋的操作类似，只有左右节点的区别

 代码

//左单旋
void RotateL(Node* parent)
{Node* SubR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subR->_left = 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;}

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

参考30和60的相对位置，将双旋变成单旋后再旋转，即：先对30进行左单旋，然后再对90进行右单旋，旋转完成后再考虑平衡因子的更新。

代码 

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

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

代码 

 

//右左单旋
void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 1){parent->_bf = 0;subR->_bf = 0;subRL->_bf = 1;}else 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{assert(false);}
}

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

这篇关于【C++】AVL树的两单旋和两双旋的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---