How tree map uses red black tree algorithm

Question

I have read many articles on Red black tree where it take O(log n) time for operations .I am not very clear how it works and how actually tree map uses red black tree algorithm to balance the tree compared to binary search tree.

Ref Links https://www.topcoder.com/community/data-science/data-science-tutorials/an-introduction-to-binary-search-and-red-black-trees/

Can anyone please explain with a example how the algorithm works.

Answer 1

A red-black tree is a binary search tree. It's just a flavor of BST that has fancy versions of insert and delete operations that reorganize the tree as they run so that the tree never gets "long and stringy." The longer and stringier a tree gets, the more it behaves like a linked list. On average, linked list operations require half the list to be touched (or the whole list in the worst case), so run time varies linearly (O(n) in the number of elements n). When the tree is "bushy" or nearly balanced, then operations are much cheaper ( O (log n) ) each. The red-black algorithms guarantee that the tree remains bushy.

To make this concrete, here are two trees that store the keys A to G. The left is long and stringy. Note how it looks like a list. In the worst case, it takes 4 key comparisons to find an element. The tree on the right is bushy. It needs only 3. Here the difference is small. For a tree of 1023 elements, the stringy tree needs 512 comparisons and the bushy one only 10. This is the power of log n.

  B                    _D_
 / \                  /   \
A   D                B     F
   / \              / \   / \
  C   F            A   C E   G
     / \
    E   G

The red-black tree isn't guaranteed to be perfectly bushy (in correct terminology "perfectly balanced"), but the red-black rules guarantee that it's bushy enough in a mathematically strict way so that operation times vary as the log of n rather than linearly in n.

The red-black rules' genius is that they are "local." During an insertion or deletion that breaks the rules, it's possible to restore them by adjusting only a constant number of nodes for each node touched by the operation. Therefore they are cheap and fairly easy to implement.

Yet when the red-black rules are true for the whole tree, it's possible to show by a clever mathematical proof that it's bushy enough as described above.

What about the tree map? A map is a function with a domain called the key set K and range called the value set V. To implement a tree map, each node stores a key-value pair <k,v> where k \in K and v \in V. In the drawings above (and most presentations), only keys (letters A-G) are shown. In the map, insertion, lookup, and deletion work on these pairs in a pretty obvious way. For example, lookup searches for a key using the usual BST algorithm. When the key is found, the value is also found because it's in the same pair. That's what's returned. In java, the pair is called Map.Entry. You can check this out in the Java source code.

I won't go into the details on how the red-black rules work because I couldn't improve on the Wikipedia page. My guess and hope is that you were missing the "big picture" so now that discussion will make sense. The good news is that nearly all languages provide a thoroughly tested and performance-optimized tree implementation, so knowing the arcane details of rotations is not necessary. Of course, if you're curious and just want to know, have at it! Congratulations!

For what it's worth, Top Coder explanations of algorithms are not always the clearest. Hunt around for others until one "clicks" for you. The respected textbooks in CS are respected for a reason: their explanations are excellent. Corman and Rivest is an accepted favorite.