algorithm - 转换为红黑树时，是否有任何理由选择一种形式而不是另一种形式？

Question

我有一个链表/二叉树方法库，可在标准容器不适合时使用 - 例如，当有不同类型的节点时，或者当我需要从二叉树转换为列表并再次转换回来时。它包括红黑树处理。

其中一种方法将双链表及时转换为完美平衡的简单二叉树O(n)（假设项目数是预先知道的）。该算法被称为“折叠”——它是二叉树再平衡算法的后半部分，曾在 Dobbs 博士上发表过。步骤基本...

我也有类似的方法可以创建一棵红黑树。原理相同，但递归跟踪节点高度 - 高度为零的节点创建为红色，所有其他节点为黑色。起始高度计算基于树大小中的最高设置位，并且经过调整，以便完美平衡(2^n)-1大小的树只有黑色节点（递归只下降到高度一）。

这里的要点是我在叶级别只有红色节点，最多恰好一半的节点是红色的。

问题是，虽然这是生成有效红黑树的一种简单方法，但它不是唯一的选择。避免让一棵完美平衡的树中的所有叶子都变红是一种随意的选择。我可以有交替的红色和黑色节点层。或者，在某些情况下，我可以通过发现完全平衡的子树并（如果需要红色节点）使子树根而不是其所有叶子变为红色，从而显着减少红色节点的数量。

问题是 - 是否有任何实际理由选择一种有效的红黑树形式而不是另一种？

这纯粹是好奇——我知道我没有任何实际的理由——但有谁知道这个选择很重要的专业应用程序吗？

score 2 · Accepted Answer

简短的回答是：这取决于.

基本上，任何有效的树就足够了。但是，就摊销分析而言- 您很可能希望选择最正确的树，从长远来看，它会给您带来最优化的行为。

例如，如果您总是选择一棵有效的树，但它容易进行大量平衡操作，那么您将获得糟糕的摊销性能。一个明显的例子是全黑树，它完全有效，但在修改时表现不佳。

这取决于，因为这通常是特定于应用程序的。

score 1 · Accepted Answer

在使用物理学家方法修改红黑树的摊销成本的标准分析中，具有零个或两个红色子节点的黑色节点被分配一个正电位，这意味着它们代表树中可能需要额外工作的有问题的地方要完成。红色节点和正好有一个红色子节点的黑色节点被分配为零的电位。

因此，为了降低修改成本，给每个黑色节点一个红色子节点。

最好用冗余二进制数类比来解释为什么有一个红色孩子的黑色节点会受到祝福。我将首先解释如何将红黑树与二进制数相关联，然后我将解释为什么单红子节点很有用。

您可能知道，红黑树是表示 2-4 棵树的一种方式，其中从根到叶的每条简单路径都具有相同的长度，但节点有 2、3 或 4 个子节点。在 2-4 树中添加或删除节点的最简单算法与从冗余二进制数中添加或减去一个的算法相同。

冗余二进制数是第 i 位表示 2 ⁱ的数字，就像在标准二进制数中一样，但第 i 位可以是 0、1或 2。它们被称为冗余，因为有多种方法可以写入给定的数字。4 _dec可以写成 100 或 20 或 12。

要将冗余二进制数加一，请增加最低有效位；如果为 3，则将其设置为 1 并递增下一个最低有效位，依此类推。算法在遇到 0 或 1 时停止。

要将叶子添加到 2-4 树，请将子添加到其预期的父级。如果父节点有五个子节点，则将其拆分为两个节点并使其成为父节点的子节点。继续，直到到达不需要拆分的节点。因此，当它遇到一个有两个或三个孩子的节点时，通往根的路径会停止。

要限制增加冗余二进制数的摊销成本，请使用物理学家方法并为每 2 位分配 1 的潜力。一个触及 k 位数的 xall 增量释放 k-1 的潜力，使其摊销成本为 O(1)。

该分析类似于增加标准二进制数的摊销成本，但标准二进制数不能同时支持 O(1) 摊销时间内的递增和递减：考虑 2 ^k - 1。它是 k 1 位数。增量成本 Θ(k)。如果随后递减，则该对花费 Θ(k) 并将数字带回其旧状态。

冗余二进制的特殊之处在于 1 位停止递增和递减的级联操作。2-4 树的特殊之处在于 3 节点停止插入和删除的级联操作。

在红黑树中，具有一个红色子节点的节点只是 2-4 树中 3 节点的表示。这些节点对子树中的插入或删除是特殊且健壮的，因此在构建会看到大量更新的红黑树时，您应该偏爱它们。

如果您知道您只会看到插入，请支持具有两个黑色子节点的节点。如果您知道您只会看到删除，请支持具有两个红色子节点的节点。

2 回答 2