Lecture 2: RB Tree and B+ Tree

Red-Black Trees

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 contain the same number of black nodes.

Lemma

A red-black tree with N internal nodes has height at most .

For any node x, sizeof(x).

B+ Trees

Definition

_A B+ tree of order M_

1. The root is either a leaf or has between 2 and M children.
2. All nonleaf nodes (except the root) have between and children.
3. All leaves are at the same depth.