Iterative Algorithm for Red-Ebony

Question

Can anyone suggest me any pointer to an iterative algorithm to insert and delete into a Red-Black tree? All the algorithms available in .Net / C # are based on recursion, which I cannot trust to process a very large amount of data (hence, a large amount of recursion depth for insert / delete). Is there anyone based on iteration?

Note. Goletas.Collection uses an iterative algorithm for the AVL tree, which is very efficient for large amounts of data. I also need a similar thing for Red-Black Tree.

Answer 1

Thank you all for your valuable comments. I just found it, but in VB6 and C. I think it is enough to understand the idea. Here are the links

• Article
• Source C
• VB source

Hope someone finds this helpful. :)

Answer 2

Tree-based algorithms are recursive in nature.

Of course, you could rewrite them as iterative, but that would be a futile exercise. That's why:

Red-black trees and similar data structures are self-balanced, and their height is logarithmic with the number of stored values. This means that you will never reach the ceiling of recursion - for this you will need to insert elements ~ 2 ²⁰⁰⁰ which simply will not happen: your computer does not have enough memory, and never, never will be.

- Stick to recursion, its fine.

Answer 3

There is a version in the introduction to the algorithms of Thomas X Cormen, Charles E Lazerson, Ronald Lavert, Clifford Stein.

Pseudo-code is available on Google books (p. 270).

As pointed out in the comments, the approach to copying data to node z instead of replacing z with y on line 14/15 is not optimal, especially if you have pointers to nodes somewhere else. So line 13-16 can be:

 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: ... 

Where replace_parent defined as (this can also be used for lines 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