四、AVL树的旋转
如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡
根据节点插入位置的不同，AVL树的旋转分为四种：
新节点插入较高右子树的右侧—右右：左单旋
1、左单旋
抽象示图：
注意：
上图在插入前AVL树是平衡的，新节点插入到60的右子树(注意：此处不是有孩子)中，60右子树增加了一层，导致以30为根的二叉树不平衡
要让30平衡，只能将30右子树的高度减少一层，左子树增加一层，即将右子树往上提，这样30转下来，因为30比60大=小，只能将其放在60的左子树，而如果60有左子树，左子树根的值一定大于30，小于60，只能将其放在30的右子树，旋转完成后，更新节点的平衡因子即可
对于a,b,c都是符合AVL树且高度为h的树的一种，这里不具体表示，以抽象表示各种情况，对于以下抽象图示也是如此
在旋转过程中，有以下几种情况需要考虑：
60节点的左孩子可能存在，也可能不存在
30可能是根节点，也可能是子树：如果是根节点，旋转完成后，要更新根节点；如果是子树，可能是某个节点的左子树，也可能是右子树，需要更新父结点的左右结点地址
旋转后，子树得到平衡，两个旋转结点的平衡因子更新为0，而高度没有改变，不用再向上更新结点平衡因子
实例示图：
实现代码：
// 左单旋 void RotateL(Node* parent) { //记录节点信息 Node* subR = parent->_right; Node* subRL = subR->_left; Node* parentP = parent->_parent; //修改链接关系 parent->_right = subRL; if (subRL)//避免为空节点的情况 subRL->_parent = parent; subR->_left = parent; parent->_parent = subR; //讨论父节点的情况 if (parent == _root) { _root = subR; subR->_parent = nullptr; } else { if (parentP->_left == parent) { parentP->_left = subR; } else { parentP->_right = subR; } subR->_parent = parentP; } //更新平衡因子 subR->_bf = parent->_bf = 0; }
- 新节点插入较高左子树的左侧—左左：右单旋
2、右单旋
注：具体思路和步骤可以参考左单旋
- 抽象示图：
- 实例示图：
- 实现代码：
// 右单旋 void RotateR(Node* parent) { //记录节点信息 Node* subL = parent->_left; Node* subLR = subL->_right; Node* parentP = parent->_parent; //修改链接关系 parent->_left = subLR; if (subLR)//避免为空节点的情况 subLR->_parent = parent; subL->_right = parent; parent->_parent = subL; //讨论父节点的情况 if (parent == _root) { _root = subL; subL->_parent = nullptr; } else { if (parentP->_left == parent) { parentP->_left = subL; } else { parentP->_right = subL; } subL->_parent = parentP; } //更新平衡因子 subL->_bf = parent->_bf = 0; }
新节点插入较高左子树的右侧**—**左右：先左单旋再右单旋
3、左右双旋
抽象示图：
注意：
将双旋变成单旋后再旋转，即先对30进行左单旋，然后再对90进行右单旋，旋转完成后再考虑平衡因子的更新（并不都为0，具体情况具体分析）
复用单旋会把其他情况都给处理，例如子树是否为空，当前不平衡结点为根结点还是子树结点
对于h高度的子树，h满足大于等于0，当h=0时，插入新节点就是60
左右双旋可以看做是60做当前树的根结点，并将左子树给给30结点，将右子树给给90结点
旋转后更新平衡因子具有三种情况：
插入结点就是不平衡结点的subLR（左子结点的右子结点），30,60,90都更新为0
插入结点为不平衡结点的subLR的左子结点，30,60更新为0，90更新为1
插入结点就是不平衡结点的subLR的右子节点，90,60更新为0，30更新为-1
实例示图：h为0的情况
实现代码：
// 左右双旋 void RotateLR(Node* parent) { //记录节点地址和平衡因子 Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; //旋转 RotateL(subL); RotateR(parent); //处理平衡因子 if (bf == -1)//新增节点为subLR的左子树 { subLR->_bf = 0; parent->_bf = 1; subL->_bf = 0; } else if (bf == 1)//新增节点为subRL的右子树 { subL->_bf = -1; parent->_bf = 0; subLR->_bf = 0; } else if (bf == 0)//新增节点就是subRL { subLR->_bf = 0; parent->_bf = 0; subL->_bf = 0; } else //旋转之前就已经存在错误了 { assert(false); } }
4、右左双旋
- 抽象示图：
注：具体情况可以参考左右双旋
- 实例示图：
- 实现代码：
// 右左双旋 void RotateRL(Node* parent) { //记录节点地址和平衡因子 Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; //旋转 RotateR(subR); RotateL(parent); //处理平衡因子 if (bf == -1)//新增节点为subLR的左子树 { subRL->_bf = 0; parent->_bf = 0; subR->_bf = 1; } else if (bf == 1)//新增节点为subLR的右子树 { subRL->_bf = 0; parent->_bf = -1; subR->_bf = 0; } else if (bf == 0)//新增节点就是subLR { subRL->_bf = 0; parent->_bf = 0; subR->_bf = 0; } else //旋转之前就已经存在错误了 { assert(false); } }
