Tree Map Implementation and it’s Internal working (Red Black Tree Insertion)

Chinmay Venkata Sabbam

Published in

art of coding

7 min readOct 19, 2019

1. Hierarchy Diagram of Tree Map

2. Customized Implementation of Tree Map

if you need to Implement Custom Objects as a keys in Tree Map , you Must Implement the Comparator<K> Interface and you Must Overridden the Compare Method between the Two Keys . Then only it will works

Let’s see Below Example for the Better Understanding …..
we have Employee custom object , we put Employee Object as a key and their PF amount <Long> as a Values in Tree Map with and without implementing the Comparator Interface

TreeMap with and without Comparator Interface implementation

Output:

In the above Example we Implemented the Comparator Interface to the name field of the Employee Object,so output is printed with Employee name sorting order

Tree Map Internally Implements the Red Black Tree Data-structure internally. so let’s see Red Black Tree and How it’s Insertion Operation will works

3. Properties of the Red Black Tree

It must obey the Binary Search Tree Property

Binary search Tree property : Always the nodes compared to the parent
If the value of the node < the value of the parent — it must be left of the parent node
If the value of the node > the value of the parent — it must be right of the parent node

2. Every node must be whether in red or black in color

3. The root node must be black

4. Children of red color node must be black( 2 consecutive red nodes is not allowed)

5. Every path from parent node to null must contain the same number of black nodes

6. Leaf nodes children are null it is also in black

Trees are not Red black trees because due to property violations

Analyze the above mentioned image , they are not a red black tree due to violation of above mentioned properties

Tree-1 : it violates point no: 5 i.e Every path from parent node to null must contain the same number of black nodes
Tree-2 : it violates point no : 4 i.e Children of red color node must be black( 2 consecutive red nodes is not allowed)
Tree-3 : it violates point no : 3 i.e The root node must be black
Tree-4 : it violates point no : 1 It must obey the Binary Search Tree Property

it satisfies all the properties of the Red black tree

4. Insertion Operation of the Red Black Tree

Tree Notation :

Cases of the Red Black Tree

Color Change :

Grandparent as red
Uncle and parent as black

CASE:1 : Root is in red : then we will change the color from Red to black

if Two consecutive nodes are red then :

CASE:2 : Red Uncle condition : Locate uncle and see if it is Red or not if it is red then Apply the Color Change points and Now Node position Moves to the Grand Parent

CASE:3 : No uncle or Black Uncle Condition :
CASE:3.1 : Same side (If node is in same direction with the parent node is located to the side of the root node)
Apply the Color Change points and perform the Opposite side rotation

CASE:3.2 : Opposite side(If node is in opposite direction with the parent node is located to the side of the root node)
Move node to parent (Parent <-> grandparent side_rotation) and Perform the CASE:3.1

Let’s Understand the above cases with the Example

Insert 25,14,45,51,55,40,32,60,57,12,13 in to the red black tree

STEP:1 : Inserted 25,14,45,51,55,40,32,60,57,12,13 in to the red black tree

STEP:2 : Inserted 25,14,45,51,55,40,32,60,57,12,13 in to the red black tree

STEP:3 : Inserted 25,14,45,51,55,40,32,60,57,12,13 in to the red black tree

if you observe the Tree-1 then we clearly observe that there are consecutive red Nodes . when we check the uncle node it is in red. so we performed the Red uncle condition (CASE:2).
In Tree-2 , we performed color change (grand parent as red and uncle and parent as black) . Now node position moved to grand parent
In Tree-3 , we performed the CASE-1 (we will change the color from Red to black)

STEP:4 : Inserted 25,14,45,51,55,40,32,60,57,12,13 in to the red black tree

if you observe the Tree-1 then we clearly observe that there are consecutive red Nodes .when we check the uncle node there is no uncle node and same side . so we performed the CASE:3.1 : Same side
In Tree-2 ,we Apply the Color Change points and perform the Opposite side rotation
Tree-3 is after we perform opposite side rotation

STEP:5 : Inserted 25,14,45,51,55,40,32,60,57,12,13 in to the red black tree

if you observe the Tree-1 then we clearly observe that there are consecutive red Nodes . when we check the uncle node it is in red. so we performed the Red uncle condition (CASE:2).
In Tree-2 , we performed color change (grand parent as red and uncle and parent as black) . Now node position moved to grand parent. it is fine and satisfies all red black tree properties

STEP:6 : Inserted 25,14,45,51,55,40,32,60,57,12,13 in to the red black tree

STEP:7 : Inserted 25,14,45,51,55,40,32,60,57,12,13 in to the red black tree

STEP:8 : Inserted 25,14,45,51,55,40,32,60,57,12,13 in to the red black tree

if you observe the Tree-1 then we clearly observe that there are consecutive red Nodes .when we check the uncle node there is no uncle node and opposite side . so we performed the CASE:3.2 : Opposite side
In Tree-2 , Move node to parent node , again we observed that there are consecutive nodes
In Tree-3 , we perform the CASE:3.1 : Same side i.e we Apply the Color Change points and perform the Opposite side rotation
In Tree-4 , it is fine and satisfies all red black tree properties

STEP:9 : Inserted 25,14,45,51,55,40,32,60,57,12,13 in to the red black tree

STEP:10 : Inserted 25,14,45,51,55,40,32,60,57,12,13 in to the red black tree

In Tree-2 , Move node to parent node , again we observed that there are consecutive nodes
In Tree-3 , we perform the CASE:3.1 : Same side i.e we Apply the Color Change points and perform the Opposite side rotation
In Tree-4 , it is fine and satisfies all red black tree properties