## Binary Tree

A binary tree \(T\) is a structure defined on a finite set of nodes that either

- contains no nodes, or
- is composed of three disjoint set of nodes: a root node, a binary tree called its left subtree, and a binary tree called its right subtree.

The binary tree that contains no nodes is called the empty tree or null tree, sometimes denoted NIL.

## Binary Search Tree

The keys in a binary search tree are always stored in such a way as to satisfy the binary-search-tree property:

Let \(x\) be a node in a binary search tree. If \(y\) is a node in the left subtree of \(x\), then \(y.key \geq x.key\). If \(y\) is a node in the right subtree of \(x\), then \(y.key \leq x.key\).

#### Theorem 1

If \(x\) is the root of an \(n\)-node subtree, then the call INORDER-TREE-WALK(\(x\)) takes \(\Theta(n)\) time.

### Querying a binary search tree

TREE-SEARCH(x, k)

```
if x == NIL or k == x.key
return x
if k < x.key
return TREE-SEARCH(x.left, k)
else return TREE-SEARCH(x.right, k)
```

ITERATIVE-TREE-SEARCH(x, k)

```
while x != NIL and k != x.key
if k < x.key
x = x.left
else x = x.right
return x
```

TREE-MINIMUM(x)

```
while x.left != NIL
x = x.left
return x
```

TREE-MAXIMUM(x)

```
while x.right != NIL
x = x.right
return x
```

#### Theorem 2

We can implement the dynamic-set operations SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, and PREDECESSOR so that each one runs in \(O(h)\) time on a binary search tree of height \(h\).

#### Theorem 3

We can implement the dynamic-set operations INSERT and DELETE so that each one runs in \(O(h)\) time on a binary search tree of height \(h\).

#### Theorem 4

The expected height of a randomly built binary search tree on \(n\) distinct keys is \(O(\lg{n})\).

## Red-Black Tree

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

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

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

#### Lemma 1

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

## References

- Introduction to Algorithms, MIT Press