algorithm - 二叉树的平衡是如何实现的？

Question

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

• 是否可以平衡普通的二叉树？如果是，应该使用哪种算法？
• 我是否必须使用 AVL 或红黑树来获得平衡树？这些是如何工作的？

我读了一些关于旋转、权重的内容，但我现在有点困惑

Answer 1

Is it possible to balance a normal binary tree? If yes, whichalgorithm should be used?

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

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

Do I necessarily have to use a AVL or Red-black tree to obtain abalanced tree?

还有其他平衡树，例如B+ trees ，以及其他数据结构(不是树)，例如 skip-lists .您可能想查看已知 data structures 的列表。 ，尤其是 trees section .

How do these work?

我在 AVL tree 上找到维基百科文章和 Red-Black tree非常翔实。如果您有什么不明白的地方 - 您应该问。

此外:尝试自己实现平衡树(实现已知树，而不是发明新树 - 当然) - 非常适合教育目的，这样做 - 你会绝对了解它是如何工作的。