# (a,b) Trees

You might have heard of (2,3) trees or (2,4)) trees. (a,b) tress are a generalization.

## Definition

An (a,b) tree is a **balanced** (e.g. all leaves on same level) search tree in which:

- 2 ≤ a ≤ (b+1)/2
- Each internal node except the root has at least
a children and at most
b children.
- The root has at most b children.

An example of a (2,4)-tree:

**Exercise**: State whether each of the following pairs can represent an (a,b)-tree: (1,6), (2,2), (2,3), (2,4), (2,5), (3,2), (3,3), (3,5), (3,7), (3,8).

## How They Work

### Lookup

Lookup proceeds as in any search tree.

### Insertion

Start by adding into the proper leaf node. If the addition causes an overflow (*b* items), then split and propagate the middle item.

Example: to insert 10 into the tree above:

You should see from this why the root node allows for a minimum of two children (rather than *a*).

**Exercise**: Explain the reason for the requirement a ≤ (b+1)/2.

### Deletion

First, if the item you are deleting is not in a leaf node, then bring its predecessor up into its space and delete the predecessor item from its leaf node. This may require **transfers** and **fusions**. Fusions may cause underflow at the parent so in general this process has to be repeated up the tree.

A simple deletion example, requiring transfers only:

A more complex example requiring multiple fusions:

## B-Trees

A B-Tree is a (a,b)-tree with a = ceil(b/2).

The following are B-trees

- (2,3)-tree
- (2,4)-tree
- (3,5)-tree
- (3,6)-tree
- (4,7)-tree
- (4,8)-tree
- (5,9)-tree
- (5,10)-tree

A B+ tree is a cool variation of the B-tree. All elements are stored in the leaves; the internal nodes repeat keys where necessary. Also, the leaf nodes are chained together; this gives you rapid access to the entire collection in sorted order.

**Exercise**: Implement a B+ Tree class.