algorithm - Tarjan 自上而下的红黑树效率

Question

我想知道 Tarjan 的自上而下的红黑树算法与其他红黑树算法（例如 Robert Sedgewick 的算法）相比如何。有没有人比较过各种自顶向下和自底向上算法的结果？请让我知道，因为这将有助于决定我需要将哪种算法作为基本算法，因为我计划稍后使其并发。（我不仅想比较自上而下与自下而上的比较，还要比较这些研究人员的各种算法！）

Answer 1

据我所知，这方面的工作很少。在不同的平衡 BST（AVL vs RB vs splay）之间进行了一些性能测试，但据我所知，那些针对红黑树变体运行的测试是轶事：RB树的一种变体针对“标准”的基准测试一个具体案例的实施。

因此，如果您决定实现红黑树，您应该选择一些变体、一种语言并根据您的用例对它们进行基准测试。你可以在网上找到一些不同种类的红黑树的开源实现，这里有一些我知道的主要风格：

• 左倾 RB 树- Java - GPLv3 - (Sedgewick/Wayne)
• 递归 BU 插入/删除，迭代 TD 插入/删除 - C - MIT-like - （永远困惑）
• 递归 BU 插入，递归 TD 删除 - Java - MIT - ( me )

这些实现是节省空间的，因为它们都有不使用父指针的共同点。但是，您应该正确地对它们进行基准测试，并在需要时对其进行优化。