DS C2 Red-Black Trees, B+ Tree

Red-Black Trees

ref Introduction to Algorithms, P451-462.

A red-black tree : a BST with one extra bit of storage per node, its color, which can be either RED or BLACK.

Structure

• attributes of Tree node: color, key, left, right,and p

• Internal and External: The normal, key-bearing nodes are internal, while the extra leaves(sentinel) are not.

• NIL, Non Internal leaf : pointers to leaves (external nodes) of the BST.
  Its other attributes (p,left,right,key) can take on arbitrary values.

  If a child or the parent of a (internal) node does not exist, the corresponding pointer attribute of the node contains the value NIL.

Definition

A red-black tree is a BT that satisfies the following red-black properties:

1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black.
5. For each node, all simple paths from the node to descendant leaves(NIL) contain the same number of black nodes.

Usually the NIL are omitted in the red-black tree diagram.

black-height

The black-height of any node x, denoted by $bh(x)$, is the number of black nodes on any simple path from, but not including x down to a leaf(NIL).

The black-height of a red-black tree is the black-height of its root.

$$bh(Tree) = bh(root(Tree))$$

The notion of black-height is well defined by property 5.

Another property

A red-black tree with n internal nodes has height at most $2\log(n + 1)$.

PF:

1. For any node x,

   $$sizeof(x) \ge 2^{bh(x)} - 1$$

   where sizeof(x) refers to number of internal nodes in the subtree rooted at x.

   • Here we re-define the height of a empty tree to be 0 cause NIL exists. If $h(x) = 0$, x is NULL, $sizeof(x) = 0 = 2^0 - 1$.

   • Suppose it is true for all x with $h(x) \le k$​. Then for x = k + 1, $bh(child) \in \{bh(x),bh(x) -1\}$​ depending on the color of the child.

     $$sizeof(child) \ge 2^{bh(child)} - 1\ge 2^{bh(x) - 1} - 1$$

     $$sizeof(x) = 1 + sizeof(lchild) + sizeof(rchild) \ge 1 + 2^{bh(x)} - 2 = 2^{bh(x)} - 1$$

2. $bh(Tree) \ge \frac{h(Tree)}{2}$

   For every red node, both of its children must be black.
   Hence, on any simple path from root to a leaf, at least half the nodes (black root not included) must be black.

Hence,

$$sizeof(root) = N \ge 2^{bh(Tree)} - 1 \ge 2^{\frac{h(Tree)}{2}} - 1$$

$$h(Tree) \le 2\log(N + 1)$$

Insertion and operation