平衡二叉树（树的旋转）_二叉树的平衡旋转

作者：盐析白兔 | 2024-05-30 00:27:21

踩

二叉树的平衡旋转

1、概念

平衡二叉树建立在二叉排序树的基础上，目的是使二叉排序树的平均查找长度更小，即让各结点的深度尽可能小，因此，树中每个结点的两棵子树的深度不要偏差太大。

平衡二叉树的递归定义：平衡二叉树是一棵二叉树，其可以为空，或满足如下2个性质：①左右子树深度之差的绝对值不大于1。②左右子树都是平衡二叉树。

平衡因子的概念：结点的平衡因子 = 结点的左子树深度 — 结点的右子树深度。若平衡因子的取值为-1、0或1时，该节点是平衡的，否则是不平衡的。

最低不平衡结点的概念：用A表示最低不平衡结点，则A的祖先结点可能有不平衡的，但其所有后代结点都是平衡的。

2、平衡化的实现

整个实现过程是通过在一棵平衡二叉树中依次插入元素(按照二叉排序树的方式)，若出现不平衡，则要根据新插入的结点与最低不平衡结点的位置关系进行相应的调整。分为LL型、RR型、LR型和RL型4种类型，各调整方法如下(下面用A表示最低不平衡结点)：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/644561