(a,b) Trees

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


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

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 proceeds as in any search tree.


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.


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:



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

The following are B-trees

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.