C++ -- AVL树的插入和旋转

1. AVL树基础

1.1 概念

当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

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

• 它的左右子树都是AVL树
• 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

1.2 节点的定义

template<class T>
struct AVLTreeNode
{AVLTreeNode(const T& data = T()): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _bf(0){}AVLTreeNode<T>* _pLeft;AVLTreeNode<T>* _pRight;AVLTreeNode<T>* _pParent;T _data;int _bf;   // 节点的平衡因子
};

2. 插入

AVL树的插入过程可以分为两步：

• 保持二叉搜索树性质
• 调整平衡因子

bool Insert(const T& data)
{// 先去找这个节点是否存在// 小的往左走  大的往右走  相等就返回Node* cur = _pRoot;Node* parent = nullptr;while (cur){if (data < cur->_data){parent = cur;cur = cur->_pLeft;}else if (data > cur->_data){parent = cur;cur = cur->_pRight;}else{return false;}// 到这里找到插入的位置了Node* cur = new Node(data);if (cur->_data < parent->_data){parent->_pLeft = cur;}else{parent->_pRight = cur;}// 判断平衡因子while (parent){if (parent->_bf == 0){return true;}else if (parent->_bf == -1 || parent->_bf == 1){cur = parent;parent = parent->_pParent;}else if (parent->_bf == -2 || parent->_bf == 2){// 平衡因子异常需要旋转// ......}else{assert(false);}break;}}
}

1. 按照二叉搜索树的性质找到插入的位置。如果已经存在则返回。
2. 从插入位置开始调整平衡因子
3. 平衡因子为0时代表无异常；为1或-1时向上继续调整；为2或-2时代表平衡因子异常，需要旋转

3. 旋转

3.1 LL型失衡（右旋）

新节点插入较高左子树的左侧

插入前树是平衡的。插入新节点后平衡被破坏，需要调整根节点的平衡因子。想让60平衡，需要让左子树高度减少一层，右子树高度增高一层。
同时还要保证为二叉搜索树，只能将30往上提，60下降。30的右孩子一定比30大且比60小，旋转后将其链接到60的左孩子。
旋转时有几种情况需要讨论：

1. 30的右子树可能不存在，需要特殊判断，防止出现野指针。
2. 60可能是根节点也可能是上面树的孩子节点。需要判断30提上去后的位置。

代码实现

void RotateR(Node* pParent){Node* pSubL = pParent->_pLeft;Node* pSubLR = pSubL->_pRight;// 改变pParent和pSubL孩子的指向pParent->_pLeft = pSubLR;if (pSubLR)pSubLR->_pParent = pParent;pSubL->_pRight = pParent;// 更新pParent和pSubL的双亲Node* pPParent = pParent->_pParent;pParent->_pParent = pSubL;pSubL->_pParent = pPParent;// 更新原pParent双亲的左||右指针域指向if (nullptr == pPParent){_pRoot = pSubL;}else{if (pParent == pPParent->_pLeft)pPParent->_pLeft = pSubL;elsepPParent->_pRight = pSubL;}pParent->_bf = pSubL->_bf = 0;}

3.2 RR型失衡（左旋）

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

代码实现和右旋类似

3.3 LR型失衡（先左后右）

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

代码实现：

void RotateLR(Node* pParent){Node* pSubL = pParent->_pLeft;Node* pSubLR = pSubL->_pRight;int bf = pSubLR->_bf;RotateL(pParent->_pLeft);RotateR(pParent);if (-1 == bf)pParent->_bf = 1;else if (1 == bf)pSubL->_bf = -1;}

3.4 RL型失衡（先右后左）

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

代码实现：

void RotateRL(Node* pParent){Node* pSubR = pParent->_pRight;Node* pSubRL = pSubR->_pLeft;int bf = pSubRL->_bf;RotateR(pParent->_pRight);RotateL(pParent);// 更新部分节点的平衡因子if (bf == -1)pSubR->_bf = 1;else if (bf == 1)pParent->_bf = -1;}

3.5 总结双旋情况

双旋后的平衡因子有的为0有的不为0，辨别方法：
关注pSubLR/pSubRL未插入新节点的那侧，它分给谁当孩子（只会分给pParent或pSubL/pSubR）谁的平衡因子就特殊。
它是右孩子，旋转后到了左孩子的位置，平衡因子更新为1；它是左孩子，旋转后到了右孩子位置，平衡因子更新为-1