红黑树的迭代算法

Question

谁能建议我向迭代算法进行任何指针，以插入并删除红黑树？ .NET/C＃中可用的所有算法均基于递归，我无法相信处理大量数据（因此，插入/删除的大量递归深度）。有人根据迭代而有一个吗？

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

Answer 1

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

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

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

Answer 2

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

当然你 可以 重写它们是迭代的，但这将是徒劳的。为什么：

红黑树和类似的数据结构是 自我平衡 它们的高度与存储的值数量相对。这意味着你会 绝不 点击递归天花板 - 这需要您插入〜2²⁰⁰⁰ 元素，这根本不会发生：您的计算机没有足够的内存，并且永远不会。

- 坚持递归，很好。

Answer 3

有一个版本 算法简介 由托马斯·H·科尔森（Thomas H Cormen），查尔斯·莱西森（Charles E Leiserson），罗纳德·L·里维斯特（Ronald L Rivest），克利福德·斯坦（Clifford Stein）。

伪代码在线可用 Google书籍 （第270页）。

就像评论中指出的那样，将数据复制到节点的方法 z 而不是更换 z 经过 y 在第14/15行中，并不是最佳的，尤其是如果您在其他地方的节点上有指示。因此，第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:
    ...

在哪里 replace_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