Iterative Algorithm for Red-Black Tree

Question 1

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.

Question 2

Since a Red-Black tree is balanced, the height of a tree withN elements in it is approximatelylog_2(N) (at most2*log_2(N+1)). Therefor recursive operations will not take that many steps even if your structure is very large. Of course, you haven't specified what "large" actually is (could you clarify that?). Also, have you tried using an existing implementation of a self balancing tree? If not, it would be a waste of time if you'd start implementing something that is not necessary to begin with.

Question 3

Tree-based algorithms are by their very nature recursive.

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

Red-black trees and similar data structures areself-balanced and their height is logarithmic with the number of values stored. This means that you willnever 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.

Question 4

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.

Question 5

@Anindya: Quite the opposite. Recursion relies on the call stack, which is avery 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.

Question 6

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

Question 7

Did you find any better version/ you've implemented your own? I would like to know how will you change your answer after 10 years.

Question 8

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

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

Like pointed out in the comments, the approach of copying the data to nodez instead of replacingz byy 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 == BLACKif 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.colorif do_fixup:    ...

Wherereplace_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

Question 9

It must be noted that their RBT node deleting pseudo-code is dangerous as instead of properly relinking a node it just copies data to it from another node. See line 15 of RB-DELETE(T,z) on page 288.

Question 10

@AlexeyFrunze Why is this dangerous? And can you explain what should be done instead?

Question 11

It doesn't work well with practical C and C++ code. If there are any pointers/references from the node data to the node or to the node data elsewhere, the code breaks because they become invalid. The fix is to just do the intended node exchange without copying node data. You only need to relink nodes to other nodes correctly.

Question 12

One scenario in particular won't work with the approach described in the book. If you want your data to be in the nodes of 2 or more trees, deleting a node in one tree will corrupt the other tree(s).

Question 13

@AlexeyFrunze Updated the answer, is this your preferred way?

Konrad Rudolph 549k142 gold badges965 silver badges1.3k bronze badges · Accepted Answer · 2010-09-21 08:08:46Z

Tree-based algorithms are by their very nature recursive.

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

Red-black trees and similar data structures areself-balanced and their height is logarithmic with the number of values stored. This means that you willnever 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.

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: Quite the opposite. Recursion relies on the call stack, which is avery 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.

Movatterモバイル変換

Collectives™ on Stack Overflow

Iterative Algorithm for Red-Black Tree

3 Answers3

2 Comments

1 Comment

6 Comments

Your Answer

Sign up orlog in

Post as a guest

Linked

Related

Hot Network Questions

Subscribe to RSS