Multi-way Trees

Review Binary Search Trees

Binary search tree are organized:

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

Lets call k* the pivot.  The text does not use this terminology, I have made it up for now.  The pivot organizes the key below the node by keys less than or greater then the pivot value.  For a binary tree each node has only one pivot because there are only two sub-trees.

Multi-Way Trees

Multi-way search trees have 2 or more children and store entries = (k, x), key and value pair.  

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₁, x₁), (k₂, x₂), ..., (k_d-1, x_d-1), where k₁ ≤ k₂ ≤...≤ k_d-1. Note one less entry then children.

• Let k₀ = -inf and k_d = inf then for each entry stored in the subtree of  the d-node v rooted at v_i, 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.

If we continue to call the keys stored at a node of a multi-way tree pivots, then the search tree can still be organized by the pivots:

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

We see that the number of sub-trees, children, of a node is one more then the degree of the node, the number of pivots, entries, of the node.

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

Proposition
A multi-way tree storing n entries 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 entries stored at an node may be contained in a:

List
Sequence
Tree
etc.

It is a good idea for the container ot be an ordered dictionary. The multi-way tree is a compound data type, divided into primary and secondary data structure.  In this case a dictionary of dictionaries.

We store at d-node v of T the items (k₁, x₁, v₁), (k₂, x₂, v₂), ... , (k_d-1, x_d-1, v_d-1), (inf, null, v_d).  This gives us access to the children. Note that v_i is a reference to the sub-tree root node. 

Searching

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

We find the smallest key among the d keys stored at v such that k_i ≥ k.

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

Cost

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 then 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 dictionary then the search through the secondary structure is O(d_max) and the total search is O(h d_max).