(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:

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

example24tree.png

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:

example24treeinsertion.png

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:

simple24treedeletion.png

A more complex example requiring multiple fusions:

complex24treedeletion.png

B-Trees

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.

Summary

We’ve covered:

  • What an (a,b) tree is
  • How they work
  • Variations on the (a,b) tree: B and B+ Trees