Iterative Algorithm for Red-Black Tree

views:

106

answers:

+2 Q:

Iterative Algorithm for Red-Black Tree

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.

+5 A:

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.

Konrad Rudolph 2010-09-21 08:08:46

Yes I agree with you, but does not iterative algorithm take much more less time than its recursive counterpart? I am concerned about the response time also, which I forgot to mention.

Anindya Chatterjee 2010-09-21 08:28:12

@Anindya, no, it does not.

Bart Kiers 2010-09-21 08:28:59

@Anindya: Quite the opposite. Recursion relies on the call stack, which is a **very** efficient low-level data structure. If you rewrite the algorithm to be iterative, you need to manage your own stack, which will always be less efficient (at least one added level of pointer indirection, plus bounds checks). The only way to make iteration more efficient than recursion is when you can get rid of the explicit stack (tail recursion). The rumour that iteration is faster than recursion is just that: a rumour.

Konrad Rudolph 2010-09-21 08:38:33

I’m surprised. Goletas actually manage without a call stack. They must have found a way to make the algorithm tail recursive (don’t remember the algorithms right now so I can’t comment on that) and have refactored that tail recursion into a loop. Which is impressive, but results in really horrible code: long, convoluted, lots of repetitions and lots of `goto`.

Konrad Rudolph 2010-09-21 08:51:19

http://geeksforgeeks.org/?p=6358

Dario 2010-09-21 11:13:24

Binary Search tree insertion by nature is tail recursive.

Moron 2010-09-21 14:08:30

@Moron: Yes. I was more concerned with the rebalancing strategies. But they seem to be tail recursive as well.

Konrad Rudolph 2010-09-21 14:24:45

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

Hope someone will find it helpful. :)

Anindya Chatterjee 2010-09-21 11:07:31

ansaurus

tags:

views:

answers:

Iterative Algorithm for Red-Black Tree

related questions