2. 因为二叉排序树的插入是将新节点插入到树的叶子节点，因此可以在插
入递归返回的过程中更新每个节点的平衡因子*Node->bf，即计算该节点的左子
树与右子树高度的差。
3. 根据 A、B 的平衡因子，判断是否失衡及失衡类型，并作旋转处理。
4. 如果平衡因子*Node->bf>=2，则证明节点在左子树插入导致失衡，此时
分两种情况，①插入的值小于失衡节点左子树的值即 data < (*Node)->lchild-
>data，则证明失衡是在该节点的左子树的左子树插入节点导致的，进行 LL 型
平衡旋转；②插入的值大于失衡节点左子树的 值 即 data > (*Node)->lchild-
>data，则证明失衡是在该节点的左子树的右子树插入节点导致的，进行 LR 型
平衡旋转。
5. 如果平衡因子*Node->bf<=-2，则证明节点在右子树插入导致失衡，此时
分两种情况，①插入的值大于失衡节点右子树的值即 data>(*Node)->rchild-
>data，则证明失衡是在该节点的右子树的右子树插入节点导致的，进行 RR 型
平衡旋转；②插入的值小于失衡节点左子树的值即 data<(*Node)->lchild->data，
则证明失衡是在该节点的右子树的左子树插入节点导致的，进行 RL 型平衡旋
转。
LL 型平衡旋转
由于在 A 的左孩子的左子树上插入结点使 A 的平衡因子由 1 增到 2 而使树
失去平衡。调整方法是将子树 A 进行一次顺时针旋转。具体方法是将失衡节点
的左指针指向其左孩子的右子树，将其左孩子的右指针指向该失衡节点。随即
更新这两个节点的平衡因子。
RR 型平衡旋转
其实这和第一种 LL 型是镜像对称的，由于在 A 的右子树的右子树上插入
结点使得 A 的平衡因子由 1 增为 2；解决方法也类似，只要进行一次逆时针旋
转。具体方式是将失衡节点的右指针指向其右孩子的左子树，将其右孩子的左
指针指向该失衡节点。随即更新这两个节点的平衡因子。
LR 型平衡旋转
这种情况稍复杂些。是在 A 的左子树的右子树 C 上插入了结点引起失衡。
但具体是在插入在 C 的左子树还是右子树却并不影响解决方法，只要进行两次
旋转（先逆时针，后顺时针）即可恢复平衡。具体操作是先对失衡节点的左孩
子进行左旋（RR）操作，然后再对失衡节点本身进行右旋（LL）操作。
RL 平衡旋转
也是 LR 型的镜像对称，是 A 的右子树的左子树上插入的结点所致，也需
进行两次旋转(先顺时针，后逆时针)恢复平衡。具体操作是先对失衡节点的右
孩子进行右旋（LL）操作，然后再对失衡节点本身进行左旋（RR）操作。
(2) 生成了一棵平衡二叉树
1. 每次插入的新结点都是平衡二叉树上新的叶子结点。
2. 由于插入节点可能会破坏平衡二叉树的性质，因此在插入节点后需要进
行调整以维护二叉树的平衡性。
3. 由不同顺序的关键字序列，可能会得到不同二叉排序树。平衡二叉树既
持了二叉排序树排序的性质，又降低了原来操作的复杂度。
(3) 平衡二叉树的删除
在二叉排序树中删除节点，要保证删除后的二叉树仍然符合平衡二叉树的
定义。对于排序性的维护，可以延用上述二叉排序树的做法。对于平衡性的维
3
5星 · 超过95%的资源 201 浏览量
2021-12-18
17:49:49
上传
评论 1
收藏 3.07MB DOC 举报 
抚刺752023-06-26感谢大佬，让我及时解决了当下的问题，解燃眉之急，必须支持！
CAIVII2022-01-16用户下载后在一定时间内未进行评价，系统默认好评。
weixin_508743612022-06-24用户下载后在一定时间内未进行评价，系统默认好评。
