RB Trees

Red-Black Trees

Define

• A red-black tree is one of self-balancing binary search tree.
• A red-black tree is a representation of a (2, 4) tree by means of a binary tree whose nodes are colored red or black.
• In comparison with its associated (2, 4) tree, a red-black tree has
  • same searching time performance O(log n).
  • simpler implementation with a single node type.

• A red-black tree can also be defined as a tree that satisfies the following properties.
• Root Property: the root is black.
• External Property: every leaf is black.
• Internal Property: the children of a red node are black.
• Depth Property: all the leaves have the same black depth.

Big O Notation

• Theorem: A red-black tree storing n entries has height O(log n)
• Proof:
  • The height of a red-black tree is at most twice the height of its associated (2,4) tree, which is O(log n).
  • The search algorithm for a red-black tree is the same as that for a binary search tree.
  • By the above theorem, searching in a red-black tree takes O(log n) time.

Insertion

• To perform operation put(k, o), we execute the insertion algorithm for binary search trees and color red the newly inserted node z unless it is the root
  • We preserve the root, external, and depth properties.
  • If the parent v of z is black, we also preserve the internal property and we are done.
  • Else (v is red ) we have a double red (i.e., a violation of the internal property), which requires a reorganization of the tree.
• Example where the insertion of 4 causes a double red

Handling a Double Red

• Consider a double red with child z and parent v, and let w be the sibling of v.
• Case 1: w is black.
  • The double red is an incorrect replacement of a 4-node.
  • Restructuring: we change the 4-node replacement.
• Case 2: w is red.
  • The double red corresponds to an overflow.
  • Recoloring: we perform the equivalent of a split.


Restructuring

• A restructuring remedies a child-parent double red when the parent red node has a black sibling.
• It is equivalent to restoring the correct replacement of a 4-node.
• The internal property is restored and the other properties are preserved.
• There are four restructuring configurations depending on whether the double red nodes are left or right children.

Recoloring

• A recoloring remedies a child-parent double red when the parent red node has a red sibling.
• The parent v and its sibling w become black and the grandparent u becomes red, unless it is the root.
• It is equivalent to performing a split on a 5-node.
• The double red violation may propagate to the grandparent u.

Pseudo-Code

Algorithm put(k, o):
search for key k to locate the
insertion node z

add the new entry (k, o) at
node z and color z red

while doubleRed(z)
	if isBlack(sibling(parent(z)))
		z <- restructure(z)
		return
	else { sibling(parent(z) is red }
		z <- recolor(z)

Deletion

• To perform operation erase(k), we first execute the deletion algorithm for binary search trees.
• Let v be the internal node removed, w the external node removed, and r the sibling of w.
  • If either v or r was red, we color r black and we are done. (we call case 0)
  • Else (v and r were both black) we color r double black, which is a violation of the internal property requiring a reorganization of the tree.
• Example where the deletion of 8 causes a double black:

Handling a Double Black

• Case 1: The sibling y of r is black, and has a red child z.
  • We perform a restructuring.

• Case 2: The sibling y of r is black, and y’s both children are black.
  • We perform a recoloring
  • Case 2-1: x (r’s parent) is red.

• Case 3: The sibling y of r is red.
  • We perform adjustment.
    • If y is the right child of x, then let z be the right child of y.
    • If y is the left child of x, then let z be the left child of y.
  • Case 3-1: z is the left child of y.