Possible Duplicate:
Red-Black Trees
I started watching a lecture at mit on red-black trees and after 15 minutes gave up.
Sure, I have not watched the previous 10 lectures but why no real world example before going into the theory?
Can someone give an example and explain why red-black trees are an essential data structure?
Red-black trees are self-balancing, and so can insert, delete, and search in O(log n) time. Other types of balanced trees (e.g. AVL trees) are often slower for insert and delete operations.
In addition, the code for red-black trees tends to be simpler.
They are good for creating Maps or associative arrays, and special-purpose data stores. I used one in a high speed telecom application to implement a least-cost routing system.
Note: I haven't seen the lecture.
Red-black trees are binary search trees that are self-balancing when an item is added or removed. This feature guarantees that every search within this tree has O(logn) complexity.
If you construct a tree without balancing it, it is possible to create a degenrated tree that is effectively a linked list with O(n) complexity.
Wikipedia says "self-balancing binary search tree".
"Put very simply, a red–black tree is a binary search tree that inserts and deletes in such a way that the tree is always reasonably balanced."
Which helps when data happens to be sorted. Without the balancing the tree devolves to a linked list.
Wikipedia provides an explanation and an important example.
Red-black trees provide worst-case guarantees for insertion time, deletion time and search time. This can be very useful for real time applications.
A real world example is the Completely Fair Scheduler in the Linux kernel.
