algorithm - 第一次平衡树 - 菜鸟问题

Question

我开始研究如何平衡树木进行面试，我有一些问题

• 是否可以平衡正常的二叉树？如果是，应该使用哪种算法？
• 我是否必须使用 AVL 或红黑树才能获得平衡树？这些是如何工作的？您能否提供尽可能简单地解释这些内容的链接？

我读了一些关于旋转、重量的东西，但我现在有点困惑

Answer 1

嗯...... AVL 和红黑树是平衡的“正常二叉树”，并保持这种平衡（对于“平衡”的某些定义）。我不是计算机科学老师，无法对算法提出自己的解释，而且我猜您不是在寻找维基百科的剪切和粘贴:-)

现在，对于平衡二叉树：如果树是搜索树（即“排序”，但如果不是，则“平衡”并没有多大意义）你总是可以重新创建树。最简单的算法是使用一个数组，其中包含树中的所有元素，按排序顺序（很容易从中序遍历中获得）。然后围绕这个总体思路构建一个算法：

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

当数组具有偶数个元素时，您可能必须小心：没有明显的“中间元素”，并且删除两个候选者之一将创建不同大小的数组。我懒得进一步分析这是否可以抵消整个平衡的事情。

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

编辑：许多计算机科学家花费大量时间开发在某些情况下表现良好的数据结构和算法是有原因的。滚动你自己的平衡二叉树版本不太可能击败这些......

Answer 2

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

O(n)您可以在其中构建一个完整的树，并使用in-order traversal 中的元素填充它。

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

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

还有其他平衡树，例如B+ 树，以及其他数据结构（不是树），例如跳过列表。您可能想查看已知数据结构的列表，尤其是树部分。

这些是如何工作的？您能否提供尽可能简单地解释这些内容的链接？

我发现关于AVL 树和红黑树的维基百科文章非常有用。如果你有一些具体的东西你不明白 - 你应该问。

另外：尝试自己实现平衡树（实现已知的树，而不是发明新的树 - 当然） - 非常适合教育目的，这样做 - 你肯定会理解它是如何工作的。