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

Question

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

其中一种方法可以在 O(n) 时间内将双链表转换为完美平衡的简单二叉树(前提是预先知道项目的数量)。该算法被称为“折叠”——它是二叉树重新平衡算法的后半部分，曾在 Dr. Dobbs 中发表。步骤基本上是...

• 给定树的大小，决定左右子树的大小

• 对左子树进行递归

• 从列表中弹出一个节点作为根

• 递归右子树

• 将子树链接到根

我也有类似的创建红黑树的方法。原理是一样的，但是递归跟踪节点高度——高度为零的节点被创建为红色，其他所有节点都是黑色。起始高度计算基于树大小中的最高设置位，并且被摆弄以便完美平衡的 (2^n)-1 大小的树只有黑色节点(递归只下降到高度一)。

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

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

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

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

Answer 1

简短的回答是:视情况。

基本上，任何有效的树就足够了。然而，就amortized analysis而言- 很可能您会想要选择最正确的树，从长远来看会给您带来最优化的行为。

例如如果你总是选择一棵有效的树，但它很容易进行大量平衡操作，你的摊销性能就会很差。一个明显的例子是一棵全黑树，它完全有效，但在修改后表现不佳。

视情况而定，因为这通常是特定于应用程序的。