Balanced Trees

Balanced search trees are among the most useful and versatile data structures.

Many programming languages include balanced search trees in their standard libraries. e.g. C++: std::map, Java: TreeMap, Python: dict, etc.

Many advanced data structures are layered on top of balanced search trees..

A quick BST recap

A binary search tree is a binary tree where each node has a key and a value, and the following properties hold:

• Each node in the BST stores a key, and optinally, some information associated with the key.
• The keys in the left subtree are less than the key in its parent node, and the keys in the right subtree are greater than the key in its parent node.

The height of a BST is the number of nodes on the longest path from the root to a leaf. A tree with one node has height 0, A tree with no nodes has height -1.

Deleting from a BST

Deleting a node from a BST is a bit tricky. There are three cases to consider:

1. The node to be deleted is a leaf. In this case, we simply remove the node from the tree.

2. The node to be deleted has one child. In this case, we replace the node with its child.

3. The node to be deleted has two children. In this case, we replace the node with its successor (the smallest node in its right subtree), and delete the successor.

Runtime of delete is O(h), where h is the height of the tree. The challenge is to keep the height of the tree small.

Red-Black Trees A gilmpse

A red/black tree is a BST with the following additional properties:

• Each node is either red or black.
• The root is black.
• No red node has a red child.
• Every path from the root to a null node contains the same number of black nodes.

For example, the following tree is a red/black tree:

Theorem: Any red/black tree with n nodes has height O(log n).

B-Trees

In a binary search tree, each node stores a single key. That key splits the "key space" into two pieces, and each subtree stores the keys in those halves.

In a multiway search tree, each node stores an arbitrary number of keys in sorted order. A node with k keys splits the key space into k+1 pieces, and each subtree stores the keys in one of those pieces.

Balanced multiway Trees

In some sense, building a balanced multiway tree isn't all that hard. We can always just cram more keys into single node.

what could we do if our nodes get too big?

• Option 1: Push the new key down into itw own node.

  • simple to implement
  • can lead to very unbalanced trees

• Option 2: Split big nodes in half, kicking the middle key up into the parent node.

  • more complicated to implement
  • keeps the tree balanced

General idea: Cap the maximum number of keys in a ndoe, Add keys into leaves, When a node gets too big, split it and kick the middle key up into the parent node.

A B-tree is a multiway search tree with the following properties:

• Each node has between b-1 and 2b-1 keys, except the root, which has between 1 and 2b-1 keys.

• each node is either a leaf or has one more children than keys.

• All leaves are at the same depth.

The maximum height of a B-tree is O(log_b n).

Efficiency for searching:

Option 1: use a linear saerch to find the right child. O(b) O(log_b n) = O(b log_b n) time.

Option 2: use binary search to find the right child. O(log ) O(log_b n) = O(log n) time.

Efficiency for insertion:

O(b log_b n) (split every node on the path from the root to the leaf)

b = 2 is the best choice because b/log_b n is minimized when b = 2.

2-3-4 tree

A 2-3-4 tree is a B-tree where b = 2:

• Each node has between 1 and 3 keys.

• Each node is either a leaf or has one more children than keys.

• All leaves are at the same depth.

In practice, you most often see choices of b like 1024 or 4096.

Red/black trees are an isometry of 2-3-4 trees; they represent the structure of 2-3-4 trees in a different way.

Theorem: the maximum height of a red/black tree with n nodes is O(log n).

Red/Black Tree Insertion

Rule 1: When inserting a node, if its parent is black, the node red and stop.

Tree Rotations

Building Up rules

• The complex rules on red/black trees make perfect sense if you connect it back to 2-3-4 trees.

• There are lots of cases to consider, but they're all just rotations.

• Main point: Simulating the insertion of a key into a node takes O(1) time. Therefore, since 2-3-4 trees support insertion in O(log n) time, so do red/black trees.

• Same idea for deletion.

Dynamic Problems

Given some input X, compute some interesting function f(X).

Dynamic versions of problems:

Given some input X that can change in fixed ways, maintain X while being able to compute f(X) efficiently.'

The selection problem: Given a set of n numbers, find the kth smallest.

In Static selection, we can sort the numbers and then return the kth smallest. O(n log n) time.

In Dynamic selection, we can use a balanced search tree to maintain the numbers. O(log n) time per operation.

Number each key so that it only stores its order statistic in the subtree rooted at that node.

Annotate each key with the number of keys in tis left subtree.

We only update values on nodes that gained a new key in their left subtree. And there are only O(log n) such nodes.

Order statistics trees

• This modified red/black tree is called an ordere statistics tree.

  • Start with a red/black tree.
  • Annotate each node with the number of keys in its left subtree.
  • update the annotations when inserting or deleting a node.
  • propagate the annotations up the tree when doing rotations.

• Only O(log n) values must be updated when inserting or deleting a node.

• Supports all BST operations plus select (find the kth smallest key) and rank (find the rank of a key) in O(log n) time.

gneralization

Theorem: Suppose we want to cache some computed value in each node of a red/black tree. Provided that the value can be recomputed purely from the node’s value and from it’s children’s values, and provided that each value can be computed in time O(1), then these values can be cached in each node with insertions, lookups, and deletions still taking time O(log n).

Example: Hierarchical clustering

We have a set of n points in the plane, and we want to cluster them into groups of similar points (e.g. the distance), where the number of clusters is not known in advance.

dendrogram: a tree that represents the results of hierarchical clustering.