Red black trees

[lulusweety]

I know that red black tree is a special case of binary-search tree. But what is the advantage of red black trees over BSTs. Is there any advantage regarding complexity.
Does coloring the node cause any difference regarding the complexity? please anyone give me an answer.. Thanks in advance

[darkagn]

http://en.wikipedia.org/wiki/Red_black_tree describes the difference in fairly good detail. The main difference between the two is in the worst case, where a BST can be as bad as O(n) for insertion, search and delete, but a red-black tree is O(log n) in the worst case for these operations. The article is well worth a read as it describes how the red-black tree maintains its balance.

[Nick Evan]

And if you want to build your own:

eternallyconfuzzled

[lulusweety]

Thank you very much.

[haider_up32]

that is why its also used in completely fair scheduler ]

from wiki
Red-black trees offer worst-case guarantees for insertion time, deletion time, and search time. Not only does this make them valuable in time-sensitive applications such as real-time applications, but it makes them valuable building blocks in other data structures which provide worst-case guarantees; for example, many data structures used in computational geometry can be based on red-black trees.
The AVL tree is another structure supporting O(log n) search, insertion, and removal. It is more rigidly balanced than Red-Black trees, leading to slower insertion and removal but faster retrieval.
Red-black trees are also particularly valuable in functional programming, where they are one of the most common persistent data structures, used to construct associative arrays and sets which can retain previous versions after mutations. The persistent version of red-black trees requires O(log n) space for each insertion or deletion, in addition to time.