**The full code is available on Github.**

In this tutorial, we will implement a custom TreeMap data structure. As in the Java Collections Framework, our **TreeMap** implementation will be based on be based on **Red-Black Binary Search Tree** data structure.

# Red-Black Tree

A Red–Black tree is a type of self-balancing binary search tree which follows the following rules:

- Every node has a color either
`red`

or`black`

. - The root of tree is always black.
- There are no two adjacent red nodes (A red node cannot have a red parent or red child).
- Every path from root to a
`NIL`

node has same number of black nodes.

In this tutorial, we will use the **Left-leaning red–black tree**.

# Custom TreeMap Interface

Our custom TreeMap will implement the following methods:

METHOD | DESCRIPTION |
---|---|

put | Associates the specified value with the specified key in this map |

get | Returns the value to which the specified key is mapped |

containsKey | Check if the TreeMap contains a mapping for the specified key |

containsValue | Check if the TreeMap maps one or more keys to the specified value |

ceilingKey | Returns the least key greater than or equal to the given key |

floorKey | Returns the greatest key less than or equal to the given key |

keySet | Returns a Set view of the keys contained in the TreeMap. |

values | Returns a Collection view of the values contained in the TreeMap. |

remove | Removes the mapping for a key from the TreeMap if it is present |

size | Returns the number of key-value mappings in the TreeMap |

isEmpty | Returns true if the TreeMap contains no key-value mappings. |

clear | Removes all of the mappings from this TreeMap |

We define an interface that will contain all the above methods. In order to make our custom TreeMap iterable, our interface extends the ** java.lang.Iterable** interface.

public interface I_TreeMapCustom<K, V> extends Iterable<K> { /** * Associates the specified value with the specified key in this map. * * @param key * key with which the specified value is to be associated * @param value * value to be associated with the specified key * @return The specified value * @exception java.lang.NullPointerException * if the specified key or value is null */ V put(K key, V val); ...

**The full code of the interface is available on Github.**

# Implementation

## Node class

We create a class called `Node`

to represent each node of the red-black tree. The `Node`

class also represent **a key-value mapping** in our custom TreeMap.

In Red-Black tree, Every node has a color either **red** or **black**. To represent node color, we use a `boolean`

type variables: `true`

for **Red** and `false`

for **Black**.

private static final boolean RED = true; private static final boolean BLACK = false; static class Node<K, V> { K key; V val; boolean color; Node<K, V> left; Node<K, V> right; public Node(K key, V val, boolean col) { this.key = key; this.val = val; this.color = col; } }

## Attributes

We define the following three attributes for our custom TreeMap:

- A
`Node`

type attribute which is a reference to the root node of the red-black tree. - An
`integer`

that keep track of the size of the TreeMap - A
`Comparator`

that will help to compare the keys. If this attribute is`null`

, the TreeMap will use the natural order.

/*** A reference to the root node of the red-black tree. */ private Node<K, V> root; /*** Contains the size of the SymbolTable. */ private int size; /** * the comparator used by the treemap. If not provided, the treemap use the natural order. */ private Comparator<? super K> cmp;

## Constructors

We define two constructors for our custom TreeMap:

- The first constructor is a no-argument constructor. It constructs a new, empty tree map using the natural ordering of its keys. In this case, all the keys into the tree map should implement the
`Comparable`

interface. - The second constructor has a
`Comparator`

input parameter. It constructs a new, empty tree map using the comparator to compare the keys. If the comparator is`null`

, he natural ordering of the keys will be used.

public TreeMapCustom() { size = 0; root = null; cmp = null; } public TreeMapCustom(Comparator<? super K> c) { size = 0; root = null; cmp = c; }

## Helper Methods

### Comparaison Method

The comparaison helper method takes two keys *(key1 and key2)* as input parameters. It returns :

- a value greater than 0 if
*key1 > key2* - a value smaller than 0 if
*key1 < key2* - 0 if
*key1 = key2*

The comparaison helper method use the `Comparator`

attribute if not null. If `null`

and the keys does not implement the `Comparable`

interface, the method will throw a ** ClassCastException**. The time complexity of this method is

**O(1)**.

private int compare(K key1, K key2) { if (cmp != null) return cmp.compare(key1, key2); try { Comparable<? super K> cmpKey1 = (Comparable<? super K>) key1; return cmpKey1.compareTo(key2); } catch (ClassCastException e) { throw new ClassCastException(e.getMessage()); } }

### Identify Red Node

We implement a method `isRed`

that takes a node and returns `true`

if the node a **Red Node** and `false`

if not. A **NIL** node is considered as a black node. The time complexity of this method is **O(1)**.

private boolean isRed(Node<K, V> x) { if (x == null) return false; return x.color == RED; }

### Red-Black Tree elementary operations

In **Left Leaning Red-Black** implementation, there are a some elementary operations that are used to help to maintain symmetric order and perfect black balance. Those operations are local operations that change only few links. They have a constant time complexity **O(1)**.

#### 1- Left rotation

This operation helps to orient a (temporarily) right-leaning red link to lean left.

private Node<K, V> rotateLeft(Node<K, V> h) { assert (h != null) && isRed(h.right); Node<K, V> x = h.right; h.right = x.left; x.left = h; x.color = x.left.color; x.left.color = RED; return x; }

#### 2- Right rotation

This operation helps to orient a left-leaning red link to (temporarily) lean right.

private Node<K, V> rotateRight(Node<K, V> h) { assert (h != null) && isRed(h.left); Node<K, V> x = h.left; h.left = x.right; x.right = h; x.color = x.right.color; x.right.color = RED; return x; }

#### 3- Color Flip

The flip color operation recolor node when a node has two red children.

private void flipColors(Node<K, V> h) { // h must have opposite color of its two children assert (h != null) && (h.left != null) && (h.right != null); assert (!isRed(h) && isRed(h.left) && isRed(h.right)) || (isRed(h) && !isRed(h.left) && !isRed(h.right)); h.color = !h.color; h.left.color = !h.left.color; h.right.color = !h.right.color; }

## Put method implementation

The put method insert a key-value pair into the TreeMap. For the insertion, we follow the following rules:

- Perform
**standard BST insertion**and make the color of newly inserted nodes as red - If the newly inserted node has its right child red and its left child black, we apply the
**left rotation**elementary operation to the node. - If the newly inserted node has its left child red and its left-left grandchild red, we apply the
**right rotation**elementary operation to the node. - If the newly inserted node has both children red, we apply the
**flip color**elementary operation to the node.

The time complexity of the put method is **O(n)**.

@Override public V put(K key, V val) { if (key == null) throw new NullPointerException("The given key is null."); root = put(root, key, val); root.color = BLACK; size++; return val; } private Node<K, V> put(Node<K, V> h, K key, V val) { if (h == null) return new Node<K, V>(key, val, RED); int c = compare(key, h.key); if (c < 0) h.left = put(h.left, key, val); else if (c > 0) h.right = put(h.right, key, val); else h.val = val; // fix-up any right-leaning links if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h); if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); if (isRed(h.left) && isRed(h.right)) flipColors(h); return h; }

In the next part, we will implement the remaining methods and a JUnit test to test our custom TreeMap.

**The full code is available on Github.**