.net - 红黑树迭代算法

Question

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

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

Answer 1

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

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

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

– 坚持递归，没问题。