Red-black tree

Red-black tree is a binary search tree which garanties searching, insertion and deletion in logarithmic time. As all extensions of BST it has additional properties which helps to keep tree balanced:

  1. A node has color either black or red.
  2. The root node is black.
  3. All leaves are black and don’t contain data. Sometimes to reduce memory consumption a single node performs the role of all leaves.
  4. Every red node must have two black child. This implies that on any path there can’t be two consecutive red nodes or in other words a red node can’t have a red child.
  5. Every path from a node to a descendant leaf contains the same number of black nodes. This number is called black height.

rbt

The best way to get the idea of these properties is an example. Let’s say we have inserted three elements in a plain vanilla binary search tree:

bst_rbtIn order to be a red-black tree we need to fix all property violations that we have. The first property states that every node must be colored, so let’s mark all nodes as black and fix violation of the first property.

rbt_viol_1The second property is not violated now and we can skip it. The third property is violated because we don’t have empty leaves, so we must add missing leaves:

rbt_viol_2Since we don’t have the red nodes, the fourth property is not violated. But, the last property is violated and here is two possible cases to fix last violation:

rbt_viol_3In both cases I did left rotation on node one.

Operations

We’ll consider only insert and delete operations since all other operations are very similar to the binary search tree operations. Also, I found AVL tree balancing more natural than RB tree, but this is only my own opinion.

Apart of the terms which was described in binary search tree topic there are two more terms:

  1. Uncle.
  2. Grandparent.

You can find these relatives on the diagram below:

rbt_uncle_and_grandparent

Insert

There is a small difference with BST insert: the inserted node must be colored in red and left and right leaves shall be connected to the sentinel node (in my implementation I use one NIL node for all leaves).

Once a new node is inserted we need to restore balance in the tree. To do that we have to focus on the properties which can be violated right after insertion:

[table ai=”1/No.”] Property,Can be violated, Reason
Every node is either red or black.,No,We’ve inserted a red node so the property is not violated.
The root node is black.,Yes,If a new inserted node is root.
All leaves are black and don’t contain data.,No,Because a new node already has two empty leaf nodes.
Every red node must have two black child.,Yes,Possible violation if parent is red.
Every path from a node to a descendant leaf contains the same number of black nodes.,No,Because we’ve inserted a red node.
[/table]

Only two properties can be violated, to fix it we can use following algorithm:

Pre-conditions for balancing:

  1. A new node X is inserted using binary search tree insert operation.
  2. X is red.
  3. X has two NIL children.

Algorithm:

  1. If X is not root and X‘s parent is red go to step # 1.1.
    1. If X‘s parent and uncle are both red then go to step 1.1.1.
      1. Make parent and uncle black.
      2. Make grandparent red.
      3. Set grandparent to X.
      4. Go to step 1.
    2. If grandparent exists go to step 1.2.1.
      1. If is right child of parent and parent is left child of grandparent go to step 1.2.1.1.
        1. Make left rotation on parent.
        2. Set parent to X.
        3. Go to step 2.3.
      2. If is left child of parent and parent is right child of grandparent go to step 1.2.2.1.
        1. Make right rotation on parent.
        2. Set parent to X.
        3. Go to step 2.3.
      3. Make parent black.
      4. Make grandparent red.
      5. If X is left child of parent and parent is left child of grandparent then rotate right on grandparent otherwise rotate left on grand parent.
      6. Go to step 1.
  2. Make root black.
  3. End.
Delete

Deletion is most difficult part, I spent a lot of time to understand and implement it. It’s difficult because we can remove a black node and this causes problems with black height. In case if we remove a red node the black height remains the same.

Pre conditions for balancing:

  1. Deleted node was black.
  2. Let X be a node from which balancing is starting.
  3. If deleted node was a leaf then set parent of deleted node to X.
  4. If node had at most one non-leaf child then X is equal to this this child.
  5. If node had two non-leaf children then X must be equal to the right NIL node of deleted node.

Ok, let’s get party started:

  1. If X is not root and black go to 1.1.
    1. If X is left child go to 1.1.1.
      1. If sibling is red go to 1.1.1.1.
        1. Make sibling black
        2. Make parent red.
        3. Rotate left on parent.
      2. If sibling’s children are black go to 1.1.2.1.
        1. Make sibling red.
        2. Set X equal to X‘s parent.
        3. Go to step 1.
      3. If sibling right child is black go to 1.1.3.1.
        1. Make sibling’s left child black.
        2. Make sibling red.
        3. Rotate right on sibling.
      4. Make sibling color equal to X‘s parent color.
      5. Make X‘s parent black.
      6. Make sibling right child black.
      7. Rotate left on X‘s parent.
      8. Set X equal to root.
      9. Go to step 1.
    2. If X is right child go to 1.2.1 .
      1. The same steps that below 1.1 but left changed to right and vise versa.
    3. Go to step 1.
  2. Make root black.
  3. End.
Implementation

You can find my implementation of the red-black tree on GitHub: https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/ds/impl/RedBlackTree.java.

AVL tree vs. Red-black tree

On the internet you can find information and proves on why AVL trees are more rigidly balanced than red-black trees. Anyway, as a result of this in worst cases RBT’s searching is little bit slower, but insertion and deletion operations require lesser rotations.

In practice red-black trees are commonly used, for instance, Java TreeMap class and Linux kernel use this type of the tree.

Leave a Reply