红黑树的迭代算法

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

能够

红黑树和类似的数据结构是 它们的高度与存储的值的数量成对数关系。这意味着你会 达到递归上限这将需要插入~2 ²⁰⁰⁰ 元素,这是根本不会发生的:你的计算机没有足够的内存,而且永远不会。

谢谢大家的宝贵意见。我刚刚在VB6和C中找到了一个,我认为它足以理解这个想法。以下是链接

1. Article
2. C Source
3. VB Source

希望有人会觉得有用。:)

中有一个版本 算法简介

伪代码可在线获取 Google books (第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