Red-Black based implementation for TreeMap (Part 1)

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 nulland 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.

References

About the Author: Miguel KAKANAKOU

Leave a Reply

WP to LinkedIn Auto Publish Powered By : XYZScripts.com