我知道我们可以使用DSW算法或红黑平衡树对任何二进制搜索树进行预处理并将其转化为完美的二进制树。
这两种方法在时间复杂度方面有何不同？
您能否为每种方法提供一些示例/应用程序，说明使用一种方法而不是另一种方法的好处。
DSW是静态算法——你使用一次，你希望树永远不会改变。使树完全平衡需要O（N）时间，然后你可以使用它，但不需要修改它。你仍然可以这样做，但完全平衡的属性将丢失。你做的修改操作越多，树的性能就越差。
红黑树是一种动态数据结构。它在 O（log（N）） 中执行其基本操作，但当然不会像完美平衡的树那样好。最重要的是，红黑树可能会在苍蝇上被修改，并且仍然需要O（log（N））才能进行操作。
因此，这两种方法的用例不同。希望这有帮助。
当您想要创建整个BST（不平衡）然后执行大量查找（在平衡后的BST上）时，DSW很有用。当您将所有发生的添加/删除/查找交织在一起时，RB树很有用。
RB树主要是平衡的，但DSW是一个完整的二叉树（可能除了最后一级）。
两者都提供 O（log n），但 DSW 是可以摊销的一次性操作。
