Iterative Algorithm for Red-Black Tree

Question

Can anyone please suggest me any pointer to an iterative algorithm for insertion and deletion into a Red-Black Tree? All the algorithms available in .Net/C# are based on recursion, which I can't trust for handling very large number of data (hence large number of recursion depth for insertion/deletion). Does anybody have one based on iteration?

Note : Goletas.Collection uses an iterative algorithm for AVL tree which is highly efficient for large number of data, I want similar thing for Red-Black Tree also.

Answer 1

Thanks everyone for your valuable comments. I just found one but in VB6 and C. I think its enough to grasp the idea. Here are the links

1. Article
2. C Source
3. VB Source

Hope someone will find it helpful. :)

Answer 2

Tree-based algorithms are by their very nature recursive.

Of course you could rewrite them to be iterative but that would be an exercise in futility. Here’s why:

Red-black trees and similar data structures are self-balanced and their height is logarithmic with the number of values stored. This means that you will never hit the recursion ceiling – this would require that you insert ~ 2²⁰⁰⁰ elements, which is simply not going to happen: your computer doesn’t have enough memory, and never, ever will.

– Stick with recursion, it’s fine.

Answer 3

There is a version in Introduction To Algorithms by Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein.

The pseudo code is online available at Google books (page 270).

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

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 is defined as (this can be used for line 7-12, too):

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