平衡二叉树

对不起，多线程和网络. 我实际上正在为视频课程做准备，但是中间有很多问题，例如字幕平衡二叉排序树，视频编辑等，它做得不好，并且课程延迟了很多. 因此，我推进了数据结构课程. 该视频仍在制作中. 让我们继续数据结构.

小米圈子自今天起关闭，不再接受新来者. 因为已达到上限. 因此，如果我和同学有一封私人信件，我会在这里回复.

今天让我们来看一个更高级的数据结构.

我们知道，对于二叉搜索树，树层越少，用于搜索数据的平均搜索时间就越短. 在许多情况下，二进制排序树无法保证树的高度是最佳的. 例如，在极端情况下，如果插入排序树中的数据是有序的，则二叉树将退化为单个链，并且搜索时间很复杂. 该度也退化为O（n）. 为了解决这个问题，我们希望二叉树尽可能地平衡，也就是说，对于树中的任何节点，左子树上的节点数和右子树上的节点数也不会不同很多.

接下来的四课将介绍两种不同的平衡树，即AVL树和红黑树.

如前所述，平衡二叉树的目的是平衡二叉搜索树，以确保树的高度更优化，从而确保操作树的时间复杂度不会降低. 尽管在实践中，平衡二叉树不像红黑树那样常见，但是由于平衡二叉树中提出的节点旋转概念是自平衡树的基础，因此在本节中我们仍将详细讨论平衡二叉树.

平衡二叉树也称为AVL树. AVL树以其发明者G.M. Adelson-Velsky和E.M. Landis在1962年的论文“用于组织信息的算法”中发表了该论文.

平衡二叉树是具有以下属性的二叉搜索树: 对于树中的任何节点，该节点的左子树的高度和右子树的高度之差的绝对值小于2.与普通的BST相比，AVL树仅定义旋转操作，因此当左右子树之间的高度差的绝对值大于或等于2时，平衡树可以自动调整树的形状再次满足以上属性.

许多参考书中对AVL树的解释太复杂了. 在这里，我们将完全简化此过程. 只要记住两张简单的图片和一句咒语，您就可以完全理解平衡的二叉树，而且您也不必记住它.

首先定义一个特殊名称，平衡因子. 每个节点的平衡因子是节点的左子树的高度减去右子树的高度. 平衡二叉树的每个节点的平衡因子的绝对值将不超过2. 接下来，看两个实际示例，考虑依次将数据5,3,6,2,4,1插入二叉搜索树. 生成的二进制搜索树的形状如图2.12（a）所示. 对于该节点，其数据为5，其左子树的高度与右子树的高度之间的差为2. 我们可以将其更改为节点5和节点3的相关指针，如图2.12（b）所示. 显示的形状. 由于节点3的右子指针指向节点5，因此节点4暂时离开了二叉树，但是注意到节点5的左子指针变为空，因此我们可以将节点4挂在5上. 如图2.12（c）所示. 这样，整个树将继续满足平衡二叉树的性质. 此操作就像将树向右旋转一样，将其称为旋钮，我们将此操作称为右旋. 右手咒语可以简单地概括为“左儿子是父亲，父亲是右儿子，右太阳变为左太阳”. 可以看出，右手操作的效果是原始的右孩子的深度（注意不是身高）增加了1，左孙子的深度减少了1，右孙子的深度没有变化. 左手镜和右手镜是彼此的镜像，在此不再赘述.

如果插入顺序变为5、2、6、1、3、4，则生成的二叉搜索树的形状如图2.13（a）所示. 此时，节点5的左子树和右子树之间的高度差仍为2. 这时，可以执行右旋吗？我们可以尝试做到这一点. 右旋的结果如图2.13（b）所示. 此时，新的根节点2的平衡因子为-2. 显然，右旋不会重新平衡树. 这是因为在右孙子变为左孙子之后右太阳的深度不会改变，并且树不平衡的主要原因是右第3号孙子节点的深度太大. 为了解决此问题，请尝试将其变为第一个示例，即旋转左节点2一次，并得到图2.13（c）. 这会将右孙子的深度移动到左孙子. 现在树的形状与上面的示例相同，然后右手树将使左孙子的深度减少1平衡二叉排序树，而右孙子的深度将保持不变. 获得一棵新树满足平衡二叉树的特性，如图2.13（d）所示.

通过以上两个示例，我们可以找到模式. 将新节点插入平衡的二叉树中时，某个节点的子树的高度可能会更改，这会影响该节点的平衡因子. 当节点的平衡因子为2时，应考虑对节点执行右手操作. 在执行右旋之前，您还应该检查左子树上左右子孙的高度. 如果惯用左手的孙子比较大，则惯用右手的人可以重新平衡. 如果右手孙子相对较大，则必须在左子节点上执行左手旋转. （请读者考虑一下，如果一个节点的平衡因子为2，那么其左子节点的平衡因子可能为0？为什么？）

好. 今天的作业. 尝试编写此左手代码. 明天我将在该程序上上一堂课. 请不要阅读本课程的下一部分，请先自己编写.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-168549-1.html