3

任何人都可以向我建议任何指向用于插入和删除红黑树的迭代算法的指针吗？.Net/C# 中可用的所有算法都基于递归，我不能相信它可以处理大量数据（因此插入/删除的递归深度很大）。有人有基于迭代的吗？

注意：Goletas.Collection 对 AVL 树使用迭代算法，该算法对大量数据非常有效，我也希望红黑树也有类似的东西。

4

3 回答 3

9

基于树的算法本质上是递归的。

当然，您可以将它们重写为迭代，但这将是徒劳的。原因如下：

红黑树和类似的数据结构是自平衡的，它们的高度与存储的值的数量成对数。这意味着您永远不会达到递归上限——这将需要您插入 ~ 2 2000个元素，这根本不会发生：您的计算机没有足够的内存，而且永远不会。

– 坚持递归，没关系。

于 2010-09-21T08:08:46.453 回答
3

感谢大家的宝贵意见。我刚刚找到了一个，但在 VB6 和 C 中。我认为它足以掌握这个想法。这是链接

  1. 文章
  2. C 源
  3. VB源码

希望有人会发现它有帮助。:)

于 2010-09-21T11:07:31.077 回答
1

Thomas H Cormen、Charles E Leiserson、Ronald L Rivest、Clifford Stein在《算法导论》中有一个版本。

伪代码可在Google 图书（第 270 页）上在线获取。

就像评论中指出的那样，将数据复制到节点z而不是在第 14/15 行替换z的y方法不是最佳的，特别是如果您有指向其他地方的节点的指针。所以第 13-16 行可以改为：

do_fixup = y.color == BLACK

if y is not z:
    replace_parent(tree, y, z)
    y.left = z.left
    y.left.parent = y
    y.right = z.right
    y.right.parent = y
    y.color = z.color

if do_fixup:
    ...

Wherereplace_parent定义为（这也可用于第 7-12 行）：

def replace_parent(tree, a, b):
    a.parent = b.parent
    if not b.parent:
        tree.root = a
    else:
        if b is b.parent.left:
            b.parent.left = a
        else:
            b.parent.right = a
于 2012-07-04T11:33:06.403 回答