What are the applications of red-black trees? Is there any application where only RB Trees can be used and no other data structures?
+3
A:
Unless you have very specific performance requirements, an R-B tree could be replaced by some other self-balancing binary tree, for example an AVL tree. Choosing between the two of them is basically a performance optimization - they offer the same basic operations.
Not that either of them is definitively "faster" than the other, just that they're different enough that specific uses of them will tend to have slightly different performance, all else being equal. So if you draw your requirements carefully enough, or just by chance, you could end up with one of them being "fast enough" for your use, and the other not. R-B offers slightly faster insertion than AVL, at the cost of slightly slower lookup.
Steve Jessop
2010-10-10 16:45:24
A:
In database indexing some problems can be solved only using red-black trees, becuase this is optimal way to get result in fast time.
Svisstack
2010-10-10 16:56:07
+3
A:
A red-black tree is a particular implementation of a self-balancing binary search tree, and today it seems to be the most popular choice of implementation.
Binary search trees are used to implement finite maps, where you store a set of keys with associated values. You can also implement sets by only using the keys and not storing any values.
Balancing the tree is needed to guarantee good performance, as otherwise the tree could degenerate into a list, for example if you insert keys which are already sorted.
The advantage of search trees over hash tables is that you can traverse the tree efficiently in sort order.
AVL-trees are another variant of balanced binary search trees. They where popular before red-black trees where known. They are more carefully balanced, with a maximal difference of one between the heights of the left and right subtree (RB trees guarantee at most a factor of two). Their main drawback is that rebalancing takes more effort.
So red-black trees are certainly a good but not the only choice for this application.
starblue
2010-10-10 17:20:35
I think AVL trees better because they are understandable. I have yet to meet a developer who understands how RB trees work - by that, I mean more understanding than reciting the list of balancing rules.
Blank Xavier
2010-10-12 18:32:20
The basic invariant is not that complicated: In a red-black tree every path to a leaf has the same number of black nodes, and there are no adjacent red nodes on a path. This implies that the lengths of paths differ by at most a factor of two. As for the rotations required, this is a case-by-case analysis for both kinds of trees.
starblue
2010-10-13 09:55:40