algorithm - 完美二叉树：DSW 和 RB 平衡树

Question

我知道我们可以使用 DSW 算法或红黑平衡树对任何二叉搜索树进行预处理并将其变成完美的二叉树。

这两种方法在时间复杂度方面有何不同？

您能否为每个提供一些示例/应用程序，以显示使用一种方法而不是另一种方法的好处。

Answer 1

DSW 是静态算法——你使用它一次，你希望树永远不会改变。使树完全平衡需要 O(N) 时间，然后您可以使用它，但不要修改它。你仍然可以这样做，但会失去完美平衡的属性。您执行的修改操作越多，树的性能就越差。

红黑树是一种动态数据结构。它在 O(log(N)) 中执行其基本操作，但当然不会像完美平衡的树那样执行。最重要的是红黑树可以随时修改，并且仍然需要 O(log(N)) 进行操作。

因此，这两种方法在用例上有所不同。希望这可以帮助。

Answer 2

当您想要创建整个 BST（不平衡）然后执行大量查找（在后平衡 BST 上）时，DSW 很有用。当您将添加/删除/查找都交织在一起时，RB 树很有用。

RB 树主要是平衡的，但 DSW 是完整的二叉树（可能除了最后一层）。

两者都提供 O(log n) 但 DSW 是可以摊销的一次性操作。