请问有没有针对红黑树的迭代算法,可以给我一些指导?.Net/C# 中所有可用的算法都基于递归,但是我不能信任它们来处理非常大量的数据(因此需要大量递归深度进行插入/删除)。有没有人有基于迭代的算法呢?
注意:Goletas.Collection 使用迭代算法实现 AVL 树,这对于大量数据非常高效,我也希望能够实现类似的红黑树。
请问有没有针对红黑树的迭代算法,可以给我一些指导?.Net/C# 中所有可用的算法都基于递归,但是我不能信任它们来处理非常大量的数据(因此需要大量递归深度进行插入/删除)。有没有人有基于迭代的算法呢?
注意:Goletas.Collection 使用迭代算法实现 AVL 树,这对于大量数据非常高效,我也希望能够实现类似的红黑树。
在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
y.left.parent = y
(以及右边的操作)之前,你可能需要检查一下是否为叶节点,但我不知道你的具体实现细节,也不会说 Pythonese。 - Alexey Frunze
N
个元素的树的高度大约为log_2(N)
(最多为2*log_2(N+1)
)。因此,即使您的结构非常大,递归操作也不会花费太多步骤。当然,您还没有指定“大”实际上是多少(您能澄清一下吗?)。另外,您是否尝试过使用现有的自平衡树实现?如果没有,那么开始实现不必要的东西将是浪费时间。 - Bart Kiers