<p>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).</p>

<p>You should use balanced trees whenever you need to bound the worst-case performance of operations on the tree.</p>

CC BY-SA 2.5
2010-08-17T13:38:09.890Z
2010-08-17T13:38:09.890Z
Tomer Vromen
<p>In which situations would I use a red/black tree instead of an unbalanced tree?</p>

CC BY-SA 3.0
2012-11-14T23:59:51.017Z
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 [cs.se] which has a broader scope than cstheory.
Kaveh
CC BY-SA 3.0
2012-11-15T20:11:00.590Z
Interestingly, this question has garnered over 1000 views. Not so irrelevant it seems ;-)
txwikinger
CC BY-SA 2.5
2010-08-17T13:34:18.150Z
this seems easy to look up on wikipedia...
Lev Reyzin
CC BY-SA 2.5
2010-08-17T13:52:08.153Z
Indeed, it took me under a minute to find thorough answers to this using Google.
Daniel Apon
CC BY-SA 2.5
2010-08-17T14:06:22.177Z
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...
Lev Reyzin
<ds.data-structures><tree>
What is the advantage of red/black trees in comparison with unbalanced trees?
txwikinger
# What is the advantage of red/black trees in comparison with unbalanced trees?

(Asked by: username_0 on 2010-08-17)

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

**Tags:** ds.data-structures, tree

> **Comments:**
> **username_2**: this seems easy to look up on wikipedia...  
> **username_3**: Indeed, it took me under a minute to find thorough answers to this using Google.  
> **username_2**: 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...  
> **username_1**: 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 [cs.se] which has a broader scope than cstheory.  
> **username_0**: Interestingly, this question has garnered over 1000 views. Not so irrelevant it seems ;-)  

---

## 1 answers

### Answer by username_4 on 2010-08-17. Score: 4 | Accepted answer

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.


---

