如何实现二叉树的平衡？

Question

我正在研究如何平衡树木，我有一些问题

• 平衡正常的二叉树是可能的吗？如果是，应该使用哪种算法？
• 我是否必须使用AVL或红黑树来获得平衡树？这些是怎么工作的？

我读过一些关于旋转，举重的书，但我现在有点困惑

Answer 1

好吧..。AVL和红黑树是平衡的“普通二叉树”，并保持这种平衡(对于某些“平衡”的定义)。我不是一位计算机科学老师，我不能给出我自己对算法的解释，我猜你不是在寻找维基百科的剪贴:-)

现在，为了平衡二叉树:如果树是一棵搜索树(即“排序”，但如果不是，那么“平衡”就没有多大意义了)，那么您可以随时重新创建树。最简单的算法是使用数组和树中的所有元素按排序顺序(从无序遍历中轻松获得)。然后，围绕这一总体思想构建一个算法：

• 将数组的中间元素作为树的根。这将创建一个树节点和两个数组“左”和“右”，用于形成左和右子树。
• 递归地应用相同的算法从“左”数组创建树，从“右”数组创建树。这两棵树成为父节点的子节点。

当数组有偶数的元素时，您可能必须小心:没有明显的“中间元素”，如果删除两个候选元素中的一个，就会创建不同大小的数组。我太懒了，不想进一步分析这个问题，看它是否能抵消整个平衡。

当然，每次你改变树的时候做这样的事情并不是一个好主意；你真的想要使用像AVL这样的自平衡树。在创建树之后这样做可能也没有什么用处:您可以只使用数组本身并对其执行二进制搜索，而不是创建树。数组只是二叉树的另一种形式..。

编辑:有一个原因，为什么许多计算机科学家花了大量的时间来开发数据结构和算法，在某些情况下表现良好。滚动你自己版本的平衡二叉树不太可能胜过这些..。

Answer 2

平衡正常的二叉树是可能的吗？如果是，应该使用哪种算法？

在O(n)中，您可以构建一个完整的树，并用有序遍历中的元素填充它。

它不能做得更好，因为在极少数情况下，BST可能会衰变为链表(链表)，其中所有节点都有一个子节点作为null。在这种情况下，访问中间的元素是O(n)本身。

我是否必须使用AVL或红黑树来获得平衡树？

还有其他平衡树(如B+树 )和其他数据结构(不是树)(而不是树)，如跳过列表。您可能需要查看已知数据结构的列表，特别是乔木段。

这些是怎么工作的？

我发现维基百科的文章都是关于AVL树和红黑树的，内容非常丰富。如果你有什么特别的东西，你不明白--你应该问。

另外：试图自己实现一个平衡的树(实现一个已知的树，而不是发明一个新的树--当然)--这对于教育目的来说是很棒的，通过这样做--你肯定会明白它是如何工作的。

Answer 3

你能平衡一棵不平衡的树吗？是的，你能。在PostOrderTraversal函数中，您使用为AVL创建的相同的平衡函数。

你应该这么做吗？不！你应该重新创造它！平衡这棵树会让你付出不必要的代价。

如何重新创建它？使用InOrderTraversal函数将节点放入数组中。然后使用一个变量，该变量将始终位于数组的中间和左、中、右中间，并将节点添加到新树中。

可以平衡正常的二叉树吗？如果是，应该使用哪种算法？我是否必须使用AVL或红黑树来获得平衡树？这些是如何工作的？，一般来说，树不是不平衡就是平衡。AVL，红色-黑色，2-3，等等。只是有一些属性的树，根据它们的属性，它们使用一些额外的变量和函数。这些额外的变量和函数也可以用于“正常”二叉树。换句话说，这些函数和变量不局限于它们各自类型的树。“正常”二叉树的节点总是有平衡的！您只是不使用它，因为您不关心“正常”二叉树是否平衡。他们也总是有一个高度，深度，等等。你只是不在乎。一般来说，你会在某一时刻意识到，所有这些都是在速度和内存之间的权衡。如果你知道你在做什么，更多的内存使用将使你的程序更快。较少的内存使用意味着更多的计算，因此您将有一个较慢的程序。