-6
$\begingroup$

In which situations would I use a red/black tree instead of an unbalanced tree?

$\endgroup$
  • 1
    $\begingroup$ this seems easy to look up on wikipedia... $\endgroup$ – Lev Reyzin Aug 17 '10 at 13:34
  • 2
    $\begingroup$ Indeed, it took me under a minute to find thorough answers to this using Google. $\endgroup$ – Daniel Apon Aug 17 '10 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 '10 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$ – Kaveh Nov 14 '12 at 23:59
  • $\begingroup$ Interestingly, this question has garnered over 1000 views. Not so irrelevant it seems ;-) $\endgroup$ – txwikinger Nov 15 '12 at 20:11
4
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.