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

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 2

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