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.

Brunet

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.

Dobsonfly

Answer 2

First of all, you should be more specific about your question. Specify what you know, what you don't and what you have tried.

Coming to the question, TreeMap and Red–black trees are completely different concepts. The conceptual understanding of either is not at all dependent on the other and I suggest that you do not mix them up. I will not give you the exact answer, rather I will give a brief overview of the concepts and the sequence in which you have to learn them(IMO).

The Map Data Structures

1. Map
2. Types of Map - HashMap, SortedMap, TreeMap, etc

The Tree Data Structures

1. Tree
2. Binary Tree
3. Binary Search Tree(BST)
4. Balanced BST
5. Self-balancing BST - AVL Tree, Red-Black Tree, etc

I am assuming you know the concept of Maps and Binary Search Trees. If not, a simple search will lead you to a lot of good resources.

Now, to the actual answer.

First of all you should know what are SortedMap and Self-balancing BST.

What is a SortedMap?

From Java docs,

A Map that further provides a total ordering on its keys. The map is ordered according to the natural ordering of its keys, or by a Comparator typically provided at sorted map creation time.

A SortedMap is used when you want the underlying key,value pairs to be sorted (by key). This way, it would be easier to retrieve the minimum, maximum or perform range based operations.

What is a Self-balancing Binary Search Tree?

From wikipedia,

a self-balancing (or height-balanced) binary search tree is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.

Again, Red-black tree in one implementation of Self-balancing BST. There are others like ALV tree, etc. The worst case for any of the operation on a normal BST is O(n). The main advantage of using Balanced BST over normal/un-balanced BST is that the worst case of all the operations is brought down to O(logn) with only a little overhead involved with the rearrangement of the nodes on insertion/deletion. Have a look at this.

So, what is a TreeMap?

A TreeMap is an implementation of SortedMap.

How are the TreeMap and the Red-black tree related?

They are two different things. Theoretically, you can use any of the Binary Search Trees for implementing a TreeMap. In order to get good results, we use Self-balancing Binary Search Trees which have a lesser time complexity for insert, delete and retrieve operations. In case of Java, Red-black tree is used. I do not know the exact reason as to why Red-black tree is used, but I believe there is one.

Fichte