In which situations would I use a red/black tree instead of an unbalanced tree?
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ this seems easy to look up on wikipedia... $\endgroup$– Lev Reyzin ♦Aug 17, 2010 at 13:34
-
2$\begingroup$ Indeed, it took me under a minute to find thorough answers to this using Google. $\endgroup$– Daniel AponAug 17, 2010 at 13:52
-
1$\begingroup$ I think the point of this site is to ask/answer questions that require some expert knowledge and are of some interest to the community. If something looks like an easy homework problem or can be found on wikipedia then it just wastes everyone's time. However I think the question "In which situations would I use red/black trees..." is better than "what are the advantages of a red/black tree," as the answer is less obvious. However, it not clear that's really a theory question... $\endgroup$– Lev Reyzin ♦Aug 17, 2010 at 14:06
-
$\begingroup$ I agree with the others, the question does seem off-topic for cshtoery, please check the FAQ if you are not familiar with the scope of cstheory. Remember that there is also Computer Science which has a broader scope than cstheory. $\endgroup$– KavehNov 14, 2012 at 23:59
-
$\begingroup$ Interestingly, this question has garnered over 1000 views. Not so irrelevant it seems ;-) $\endgroup$– txwikingerNov 15, 2012 at 20:11
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Red-Black trees are a form of balanced trees. This means that the tree height is always O(log n), where n is the number of node in the tree. The effect of this is that searching for a node in a balanced tree takes O(log n) time. Similarly, adding and removing also take O(log n). This is in contrast to unbalanced trees, where the worst-case complexity for searching/adding/removing is O(n) (which means that in the worst case they're not any better than linked lists).
You should use balanced trees whenever you need to bound the worst-case performance of operations on the tree.
