MULTIWAY TREES

Multiway Trees

Name

Date

Multiway Trees

Introduction

Binary trees and tries represent different approaches to looking up strings. In a binary tree, each node represents one string in the data set. Thus, the number of nodes is minimized. Also, each node contains links to only two other nodes. Thus, the size of each node is minimal. Binary search trees are very compact. However, to find a string within the tree, that entire string must be compared with the entire string contained at each node searched. This is slow. A trie is optimized for speed at the expense of size. (Devroye, 2009)

Descending the trie only involves looking at each character once, eliminating string comparisons. In the most basic implementation, each node has as many children as letters in the string's alphabet. The trie is navigated by looking up the string's characters in sequence and descending through the nodes. The process is fast, but the number and size of the nodes is large. The ternary search tree replaces each node of the trie with a modified binary search tree. For sparse tries, this binary tree will be smaller than a trie node. Each binary tree implements a single-character lookup.

Discussion

A multiway tree of order m is an ordered tree where each node has at most m children. For each node, if k is the actual number of children in the node, then k - 1 is the number of keys in the node. If the keys and subtrees are arranged in the fashion of a search tree, then this is called a multiway search tree of order m. For example, the following is a multiway search tree of order 4. Note that the first row in each node shows the keys, while the second row shows the pointers to the child nodes. Of course, in any useful application there would be a record of data associated with each key, so that the first row in each node might be an array of records where each record contains a key and its associated data. Another approach would be to have the first row of each node contain an array of records where each record contains a key and a record number for the associated data record, which is found in another file. This last method is often used when the data records are large. (Knuth 2009a) The example software will use the first method.

What does it mean to say that the keys and subtrees are "arranged in the fashion of a search tree"? Suppose that we define our nodes as follows:

typedef struct

{

int Count; // number of keys stored in the current node

ItemType Key[3]; // array to hold the 3 keys

long Branch[4]; // array of fake pointers (record numbers)

} NodeType;

Then a multiway search tree of order 4 has to fulfill the following conditions related to the ordering of the keys:

The keys in each node are in ascending order.

At every given node (call it Node) the following is true:

The ...