红黑树的迭代算法

3

请问有没有针对红黑树的迭代算法,可以给我一些指导?.Net/C# 中所有可用的算法都基于递归,但是我不能信任它们来处理非常大量的数据(因此需要大量递归深度进行插入/删除)。有没有人有基于迭代的算法呢?

注意:Goletas.Collection 使用迭代算法实现 AVL 树,这对于大量数据非常高效,我也希望能够实现类似的红黑树。


2
由于红黑树是平衡的,具有N个元素的树的高度大约为log_2(N)(最多为2*log_2(N+1))。因此,即使您的结构非常大,递归操作也不会花费太多步骤。当然,您还没有指定“大”实际上是多少(您能澄清一下吗?)。另外,您是否尝试过使用现有的自平衡树实现?如果没有,那么开始实现不必要的东西将是浪费时间。 - Bart Kiers
3个回答

9
树形算法天生具有递归性质。当然,你可以重写它们为迭代式,但那是徒劳无功的练习。原因在于:红黑树和类似数据结构是自平衡的,它们的高度随存储值的数量呈对数增长。这意味着你永远不会遇到递归层数过多的情况——这需要插入大约2^2000个元素,这是不可能发生的:你的计算机没有足够的内存,并且永远不会有足够的内存。所以,请坚持使用递归,没问题的。

是的,我同意你的观点,但是迭代算法所需的时间比递归算法少得多,这一点你是否考虑到了呢?我也很关注响应时间,这一点我之前忘记提到了。 - Anindya Chatterjee
4
@Anindya: 恰恰相反。递归依赖于调用栈,这是一种非常高效的低级数据结构。如果将算法重写为迭代形式,则需要管理自己的堆栈,这始终不如递归效率高(至少需要一个额外的指针间接层级加上边界检查)。只有当您可以摆脱显式堆栈时(尾递归)才能使迭代比递归更有效。迭代比递归快的传言只是谣言。 - Konrad Rudolph

3
感谢大家宝贵的评论。我找到了VB6和C语言中的一个问题,我认为这已经足够了解其思想。以下是链接:
  1. 文章
  2. C源代码
  3. VB源代码
希望对大家有所帮助。 :)

你找到了更好的版本/你已经实现了自己的版本吗?我想知道在10年后你会如何改变你的答案。 - VimNing

1

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

伪代码可以在Google图书(第270页)上在线获取。

正如评论中指出的那样,在第14/15行将数据复制到节点z而不是用y替换z的方法并不是最优的,特别是如果您在其他地方有节点的指针。因此,第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

需要注意的是,他们的RBT节点删除伪代码是危险的,因为它不是正确地重新链接节点,而是仅从另一个节点复制数据到它。请参见第288页RB-DELETE(T,z)的第15行。 - Alexey Frunze
@AlexeyFrunze 这为什么是危险的?你能解释一下应该做什么吗? - schlamar
它在实际的C和C++代码中效果不好。如果节点数据中存在任何指针/引用到其他地方的节点或节点数据,代码会出现错误,因为它们变得无效。修复方法是只执行预期的节点交换而不复制节点数据。您只需正确地重新链接节点即可。 - Alexey Frunze
特别是在书中描述的方法中,有一种情况无法实现。如果您希望数据位于2个或更多树的节点中,则删除一个树中的节点将破坏其他树。 - Alexey Frunze
@AlexeyFrunze 更新了答案,这是您首选的方式吗? - schlamar
差不多就是这样。在执行 y.left.parent = y(以及右边的操作)之前,你可能需要检查一下是否为叶节点,但我不知道你的具体实现细节,也不会说 Pythonese。 - Alexey Frunze

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接