Review Binary Search Trees:
Binary search tree are organized:

BST node: key  = k*
       /      \
     T_left     T_right
     k<=k*   k*<=k

Multi-Way Trees: page 404
Multi-way search trees have 2 or more children and store items = (k, e).

Definitions:
v is a node of an ordered tree.
v is a d-node if v has d children

The ordered tree, T, is a multi-way search tree iff

• All internal nodes v are d-node with d >= 2
• Each d-node v of T with children v₁, v₂, ... v_d stores d-1 items (k₁, e₁), (k₂, e₂), ..., (k_d-1, e_d-1), where k₁ <= k₂ <=...<= k_d-1. Note one less item then children.
• Let k₀ = -inf and k_d = inf then for each item stored in the subtree of  the d-node v rooted at vi, i=1,...,d; k_i-1<= k <= k_i. Note this is just the generalization of the binary search tree ordering to multi-way trees. See below.

d-Node: keys: k₁<=k₂<=k₃<=...<=k_d-1
   /   |               |      \
T₁     T₂     ...      T_d-1     T_d
k<=k₁  k<=k₂           k<=k_d-1  k_d-1<=k

Again external nodes are place holders and can be programed away.

Proposition: A multi-way tree storing n items has n + 1 external nodes.

This is just like for binary trees.

Data Structure:
At each internal node a multi-way search tree, T with v at each internal node of T. The items stored at an node maybe:

List
Sequence
Tree
etc.

We store at d-node v of T the items (k₁, e₁, v₁), (k₂, e₂, v₂), ... , (k_d-1, e_d-1, v_d-1), (inf, null, v_d).  This gives us access to the children.

Illustrate: page 405(a)

Searching:
Searching for key, k, in search tree T we process a d-node v.

We find the smallest key, k_i >= k among the d keys at v.

if k < k_i then continue the search in the dictionary of v_i.
else k = k_i then the search terminates.

The space requirement is O(n).

The time spent searching is dependent on the secondary structure.  Say the primary structure, the multi-way tree, has height h. Say d_max is the maximum d-node size.  If the secondary structure is ordered structure that the search through the secondary structure is O(lg d_max)  and the total search is O(h lg d_max).  If the secondary structure is unordered then the search through the secondary structure is O(d_max) and the total search is O(h d_max).
 

2-3-4 Trees: page 408
2-3-4 tree keeps the secondary data structure small;  d_max = 4.  So every node has at most 4 children.

Properties:

• Size: every node has between 2 and 4 children
• Depth: all external nodes are at the same height

• Because the secondary structure is bounded, the search through the secondary data structure  is O(1) even for a vector ADT.
• The depth property insures a balance tree
• Also the height of the 2-3-4 tree storing n items is O(lg n) because of depth property
• The algorithms must maintain the properties.

• Depth property
• example

Search for k terminates at external node z with parent v.
Insert a new item (k, x, w) into v along with the additional external node w.
This may cause an overflow, in other words v becomes a 5-node with keys k₁ < k₂ < k₃ < k₄ .
If overflow then split  v

Replace v with two nodes v' and v''.

v' a 3-node with children v₁, v₂, v₃ storing k₁ and k₂
v'' is a 2-node with children v₄ and v₅ storing k₄

If v is root then make new root u
u is parent of v in either case
Insert k₃ into u and make v' and v'' children of u

Note that inserting the middle key, k₃, into the parent u may cause u to overflow resulting in a cascading split.
A single split is O(1) but cascading split may take O(lg n).

Note the tree grows up through the root.

Removal:
Remove item with key k from tree T.

Search for k terminates at z such that k_i = k
If z does not have external children then we must swap k_i with node v that has only external children

Find the right most node v in subtree rooted at ith child of z (v has only external node children)
Swap the item k_i at z with the last item v.  Note we will remove item k_i so the ordering will be OK

Else v = z    // z originally only had external node children

Remove the item with k from v
This may cause and underflow in other words  v becomes a 1-node.

If underflow then

If v's adjacent sibling, w, is 3-node or greater then transfer

move a key of u to v
move a key of w to parent u.
// which keys depends on which sibling we transfer from

If v's adjacent sibling is 2-node then fusion

merge v with adjacent sibling, w, making v'
move a key from the parent u to v'
// which keys depends on which sibling we fussing to

Check for underflow at u.
If root underflow then replace root with u (delete root)

Note that the cascading underflow causes the tree to shrink at the root.

Fusion does not seem like a Fusion in a 2-3-4 tree because the node v is empty.  For example in a (3, 5) tree then the node that has underflow is not empty and could be fussed.  The essence of Fusion is that we are reducing the number children of the parent node, u, so we must remove a key from the parent and but it into the new node representing the fusion, v'.

Because the tree grows and shrink at the root then depth property is maintain => balance tree => O(lg n) methods

Performance: