单独开一章节介绍 RotateL 、 RotateR 及更复杂的 LR 和 RL 型旋转，更多是为了红黑树的旋转部分做铺垫；由于 AVL 树和红黑树发生旋转的判断标准不同 —— 分别为平衡因子和节点的颜色，两棵树左旋和右旋的在细节上会有一些差异，但从整体来看，二者的精神一致。
定义节点
template <class K, class V> struct AVLTreeNode { AVLTreeNode* _left; AVLTreeNode* _right; pair<K, V> _kv; AVLTreeNode* _parent; int _bf; AVLTreeNode(const pair<K, V>& kv) :_left(nullptr) ,_right(nullptr) ,_kv(kv) ,_parent(nullptr) ,_bf(0) {} };
关于如何快速记忆什么时候为左旋、右旋、或左右旋、或右左旋，有一个小技巧：
当左树更高，需要向右调整高度，此时右旋；
当右树更高，需要向左调整高度，此时左旋 … …
一、新节点插入较高左子树的左侧 —— 引发右单旋
void RotateR(Node* parent) { Node* ppnode = parent->_parent; Node* subLeft = parent->_left; Node* subLeftR = subLeft->_right; parent->_left = subLeftR; if (subLeftR) subLeftR->_parent = parent; subLeft->_right = parent; parent->_parent = subLeft; if (ppnode == nullptr) { _root = subLeft; subLeft->_parent = nullptr; } else { subLeft->_parent = ppnode; } // 调整平衡因子 parent->_bf = 0; subLeft->_bf = 0; }
二、新节点插入较高右子树的右侧 —— 引发左单旋
void RotateL(Node* parent) { Node* ppnode = parent->_parent; Node* subRight = parent->_right; Node* subRightL = subRight->_left; parent->_right = subRight; if (subRight) subRight->_parent = parent; subRight->_left = parent; parent->_parent = subRight; if (ppnode == nullptr) { _root = subRight; subRight->_parent = nullptr; } else { subRight->_parent = ppnode; } parent->_bf = 0; subRight->_bf = 0; }
三、新节点插入较高左子树的右侧 —— 引发左右双旋
根据旋转之前 subLeftR 的平衡因子，来决定旋转后各节点的平衡因子。
void RotateLR(Node* parent) { Node* subLeft = parent->_left; Node* subLeftR = subLeft->_right; int bf = subLeftR->_bf; // 记录旋转前的平衡因子 RotateL(subLeft); RotateR(parent); if (bf == -1) { parent->_bf = 1; subLeft->_bf = subLeftR->_bf = 0; } else if (bf == 1) { subLeft->_bf = -1; parent->_bf = subLeftR->_bf = 0; } else { parent->_bf = subLeft->_bf = subLeftR->_bf = 0; } }
四、新节点插入较高右子树的左侧 —— 引发右左双旋
void RotateRL(Node* parent) { Node* subRight = parent->_right; Node* subRightL = subRight->_left; int bf = subRightL->_bf; RotateR(subRight); RotateL(parent); if (bf == 1) { parent->_bf = -1; subRight->_bf = subRightL->_bf = 0; } else if (bf == -1) { subRight->_bf = 1; parent->_bf = subRightL->_bf = 0; } else { parent->_bf = subRight->_bf = subRightL->_bf = 0; } }
