*************** Red-Black Trees *************** A popular alternative to the AVL tree is the **red-black** tree. The popularity of this BST comes from the fact that each operation takes :math:`O(\log N)` time in the worst-case. An added bonus is that it is easy to implement a nonrecursive insertion function. How is it different from another BST? ===================================== A red-black tree is a BST with the following coloring properties: 1. Every node is colored either in red or black. 2. The root is always black. 3. If a node is red, its children must be black. (A :code:`null` node is considered to be black node) 4. Every path from a node to a :code:`null` node must contain the same number of black nodes. These rules ensure that the height of a red-black tree is at most :math:`2\log (N+1)`. The direct consequence is that searching is guaranteed to be a logarithmic operation. The following figure represents a red-black tree. The red nodes are shown with double circles. .. figure:: ./img/rbt.drawio.png :align: center | .. admonition:: Activity :class: activity * Check that each property is respected. * What happens if we insert a new node? Red-black tree will be similar in terms of structure to a BST with some modifications: .. literalinclude:: ./RedBlackTree.java :language: java :linenos: :lines: 3-47, 168 Insertion ========= We can see that inserting a new node in the tree is not simple. We consider that the nodes are initially colored in red to maintain property 4. Then there are few cases to consider. We can take the figure to illustrate the different cases: * If the parent is black: * We are done. * If the parent is red. * It will violate condition 3. * We need to adjust the tree to ensure condition 3 is enforced. Basically, we need to focus on the cases in which the parent is red. Case 1 ------ The parent sibling is also red. We can change the grandparent's color to red and change the parent and parent's sibling color to black. If the grandparent is also the root, then we change its color to black to restore property 2. .. figure:: ./img/rbt_case_1.drawio.png :align: center | Case 2 ------ This case appears when we insert a new node with a red parent, but the parent does not have a sibling. The situation is more complicated and we need to apply the following processes: * Color the grandparent to red. * Color the parent to black. * Note that it violates the property 4. * Apply a left rotation around the grandparent. .. figure:: ./img/rbt_case_2.drawio.png :align: center | .. admonition:: Activity :class: activity * Insert 2 in the following tree and balance it. .. figure:: ./img/rbt_acti vity_1.drawio.png :align: center Case 3 ------ The last case is the most complicated one. It happens when we insert a left node of a right node. Then we need to apply a double rotation. Consider the following example. .. admonition:: Example :class: example Consider the following tree. .. figure:: ./img/rbt_case_3_1.drawio.png :align: center If we insert 7 we obtain the following tree. .. figure:: ./img/rbt_case_3_2.drawio.png :align: center We apply property 3 and color 7 to black. .. figure:: ./img/rbt_case_3_3.drawio.png :align: center Then we apply the first rotation (right rotation). .. figure:: ./img/rbt_case_3_4.drawio.png :align: center The issue now is that property 4 is not true anymore. .. figure:: ./img/rbt_case_3_5.drawio.png :align: center To fix that we color 5 to red. .. figure:: ./img/rbt_case_3_6.drawio.png :align: center Property 4 is not fixed yet, so we apply a left rotation on 5. .. figure:: ./img/rbt_case_3_7.drawio.png :align: center Now, we can see that every properties holds. .. figure:: ./img/rbt_case_3_8.drawio.png :align: center | .. admonition:: Activity :class: activity * Consider the following tree. * Insert 25 and balance the tree. .. figure:: ./img/rbt_activity_2.drawio.png :align: center Insertion ========= Before implementing the insertion, we must take a look at the pseudocode. .. admonition:: Algorithm :class: example .. figure:: ./img/insertion_algorithm_rbt.png :align: center We can implement the start :code:`add` method. This method only checks if the root is empty and insert the nod. Otherwise call the recursive method :code:`add`. .. code-block:: java public boolean add(E item) { if (root == null) { root = new RedBlackNode<>(item); ((RedBlackNode) root).isRed = false; // root is black. return true; } else { root = add((RedBlackNode) root, item); ((RedBlackNode) root).isRed = false; // root is always black. return addReturn; } } Now we can implement the recursive :code:`add` method. .. code-block:: java private Node add(RedBlackNode localRoot, E item) { if (item.compareTo(localRoot.data) == 0) { // item already in the tree. addReturn = false; return localRoot; } else if (item.compareTo(localRoot.data) < 0) { // item < localRoot.data. if (localRoot.left == null) { // Create new left child. localRoot.left = new RedBlackNode<>(item); addReturn = true; return localRoot; } else { // Need to search. // Check for two red children, swap colors if found. moveBlackDown(localRoot); // Recursively add on the left. localRoot.left = add((RedBlackNode) localRoot.left, item); // See whether the left child is now red if (((RedBlackNode) localRoot.left).isRed) { // Check whether right grandchildren are red if (localRoot.left.left != null && ((RedBlackNode) localRoot.left.left).isRed) { // Left-left grandchild is also red. // Single rotation is necessary. ((RedBlackNode) localRoot.left).isRed = false; localRoot.isRed = true; return rotateRight(localRoot); } else if (localRoot.left.right != null && ((RedBlackNode) localRoot.left.right).isRed) { // Left-right grandchild is also red. // Double rotation is necessary. localRoot.left = rotateLeft(localRoot.left); ((RedBlackNode) localRoot.left).isRed = false; localRoot.isRed = true; return rotateRight(localRoot); } } } } else{ // ... } } .. admonition:: Activity :class: activity * Implement the method :code:`moveBlackDown(RedBlackNode node)`. * This method swaps the color of the two children to black and node to red. Deletion ======== After insertion, deletion is important too. And as the section suggest it, it can be down with a top-down strategy. In practice, we need to be able to delete a leaf. * To delete a node :math:`X` with two children, we swap it with the smallest node in the right subtree. Then delete it. * Same for a node with only a right child. * To delete a node with only one left child, we find the largest one in the subtree and swap it. Then we delete it. Deleting a red leaf is trivial. .. important:: However, deleting a black node will violate condition 4, so we need to ensure during the top-down pass that the leaf is red. * We start by coloring the root red. * When we arrive at a new node: * We are certain that :math:`P` is red, * and :math:`X` and :math:`T` (the sibling) are black. (We cannot have two consecutive red nodes). :math:`T` has two black children -------------------------------- Then there are 3 subcases. First case ********** In this case :math:`T` has two black children. We just need to flip the colors of :math:`X`, :math:`T` and :math:`P`. .. figure:: ./img/delete_01.drawio.png :align: center | Second Case *********** The left children of :math:`T` is red. We apply a zig-zag rotation on :math:`R`. .. figure:: ./img/delete_02.drawio.png :align: center | Third Case ********** The right children of :math:`T` is red. We apply a double rotation on :math:`T`. .. figure:: ./img/delete_03.drawio.png :align: center | One of :math:`X`'s children is red ---------------------------------- We go to the next level to obtain new :math:`X`, :math:`T` and :math:`P`. If the new :math:`X` is the red node, we can continue to the next level. Otherwise :math:`T` is red and :math:`X` and :math:`P` are black. We rotate :math:`T` and :math:`P` making :math:`X`'s new parent red. At this point we can go back to the first main case. Java API ======== Red-Black tree is implemented in the Java API :code:`java.util` with the :code:`TreeMap` class.