************************ Topic 6 - Red-Black Tree ************************ A popular alternative to the AVL tree is the **red-black** tree. The popularity of this BST comes from the fact that each operation take :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 red or black. 2. The root is black. 3. If a node is red, its children must be black. 4. Every path from a node to a null pointer 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/topic6/red-black-tree_01.png :align: center .. admonition:: Activity :class: warning * 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:: ../code/topic6/RedBlackTree.h :language: cpp :linenos: :lines: 10-13, 173-181, 191-193, 296-298 Bottom-Up Insertion =================== We can see that inserting a new node in the tree is not simple. There are different cases that we need to consider. We can take the figure to illustrate the different cases: * If the new node is colored in black. * It violates condition 4. A path will have more black nodes. * It needs to be colored in red. * If it is colored in red. * 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. Parent is Red ------------- Consider the following: * Let :math:`X` be the new node. * Let :math:`P` be the parent. * Let :math:`S` be the sibling (if it exists). * Let :math:`G` being the grandparent. Only :math:`X` and :math:`P` are red. :math:`G` is black otherwise there would be two consecutive red nodes prior to the insertion, thus violating the red-black rules. We will adopt the Splay tree terminology to describe the potential cases: * It can form a zig-zig chain. * Or a zig-zag chain. Leading to the following figures .. figure:: ../img/topic6/zig-zig.png :align: center The zig-zig chain .. figure:: ../img/topic6/zig-zag.png :align: center The zig-zag chain .. note:: Don't forget there are the symmetric cases. Obviously, if we use the same terminology to the Splay trees, we can use the same methods: * Single rotation or zig rotation. * Double rotation or zig-zag rotation. .. figure:: ../img/topic6/single_rotation.png :align: center Zig rotation .. figure:: ../img/topic6/double_rotation.png :align: center Zig-zag rotation .. admonition:: Activity :class: warning * Do you find any difference with the Splay trees single and double rotation? * Do you find a pattern with the node coloring and the rotations? * What happens if :math:`S` is red? * Insert 79 in the previous example and draw the new tree. If :math:`G` is also red, then we need to apply the change up to the root. We call it **percolation**. Top-Down Red-Black Trees ------------------------ Implementing the percolation is complicated. It requires to maintain the path using a stack or parent links. To simplify the insertion, we can apply a Top-Down strategy. If a node :math:`X` has two red children, we make it red and the two children black. It only creates a violation only if :math:`X`'s parent :math:`P` is red. In this case we apply a rotation. .. admonition:: Activity :class: warning * Apply the top-down strategy to insert 45 in the following example. * Draw the tree after each step. .. figure:: ../img/topic6/red-black-tree_01.png :align: center Red-black trees are most of the time very well balanced. Experiments suggest that the average red-black tree is as deep as an average AVL tree. Consequently the searching times are typically near optimal. Implementation -------------- With what we saw, we need to add more internal variables: .. literalinclude:: ../code/topic6/RedBlackTree.h :language: cpp :linenos: :lines: 10-13, 173-181, 191-200, 296-298 First we need to handle the special case. We can start by implementing the rotation. .. literalinclude:: ../code/topic6/RedBlackTree.h :language: cpp :linenos: :lines: 255-279 .. admonition:: Activity :class: warning * Try to write the pseudocode of the function to handle the special case. * Don't forget the two cases. Top-Down 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/topic6/delete_01.* :align: center Second Case *********** The left children of :math:`T` is red. We apply a zig-zag rotation on :math:`R`. .. figure:: ../img/topic6/delete_02.* :align: center Third Case ********** The right children of :math:`T` is red. We apply a zig rotation on :math:`T`. .. figure:: ../img/topic6/delete_03.* :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.