m-Way Search Tree
Multi-way search trees are a generalized version of binary trees that allow for efficient data
searching and sorting. Here each node contains multiple elements.
In an m-Way tree of order m, each node contains a maximum of m – 1 elements and m
children.
To make the processing of m-way trees easier some type of constraint or order will be
imposed on the keys within each node, resulting in a multiway search tree of order m (or an
m-way search tree). By definition an m-way search tree is a m-way tree in which following
condition should be satisfied −
Each node is associated with at most m children and m-1 key fields
The keys in each node are arranged in ascending order.
The keys in the first j children are less than the j-th key.
The keys in the last m-j children are higher than the j-th key.
An example of a 5-Way search tree is shown in the figure below. Observe how each
node has at most 5 child nodes & therefore has at most 4 keys contained in it.
Searching in an m-Way search tree:
The algorithm for searching for a value in an M-way search tree is the obvious generalization
of the algorithm for searching in a binary search tree. If we are searching for value X are and
currently at node consisting of values V1...Vk, there are four possible cases that can arise:
1. If X < V1, recursively search for X in V1's left subtree.
2. If X > Vk, recursively search for X in Vk's right subtree.
3. If X=Vi, for some i, then we are done (X has been found).
4. the only remaining possibility is that, for some i, Vi < X < V(i+1). In this case
recursively search for X in the subtree that is in between Vi and V(i+1).
For example, here is a 3-way search tree:
For example, suppose we were searching for 68 in the tree above. At the root, case (2)
would apply, so we would continue the search in V2's right subtree. At the root of this
subtree, case (4) applies, 68 is between V1=55 and V2=70, so we would continue to search
in the subtree between them. Now case (3) applies, 68=V2, so we are done. If we had been
searching for 69, exactly the same processing would have occurred down to the last node. At
that point, case (2) would apply, but the subtree we want to search in is empty. Therefore,
we conclude that 69 is not in the tree.
Insertion in an m-Way search tree:
The insertion in an m-Way search tree is similar to binary trees but there should be no
more than m-1 elements in a node. If the node is full then a child node will be created to
insert the further elements.
Let us see the example given below to insert an element in an m-Way search tree.
Example:
To insert a new element into an m-Way search tree we proceed in the same
way as one would in order to search for the element.
To insert 6 into the 5-Way search tree shown in the figure, we proceed to
search for 6 and find that we fall off the tree at the node [7, 12] with the first
child node showing a null pointer.
Since the node has only two keys and a 5-Way search tree can accommodate
up to 4 keys in a node, 6 is inserted into the node like [6, 7, 12].
But to insert 146, the node [148, 151, 172, 186] is already full, hence we open a
new child node and insert 146 into it. Both these insertions have been
illustrated below.
Deletion in an m-Way search tree:
Let K be a key to be deleted from the m-Way search tree. To delete the key, we proceed as
one would to search for the key. Let the node accommodating the key be as illustrated
below.
Approach:
There are several cases for deletion
If (Ai = Aj = NULL) then delete K
If (Ai != NULL, Aj = NULL) then choose the largest of the key elements K’ in the
child node pointed to by Ai, delete the key K’ and replace K by K’
Obviously, deletion of K’ may call for subsequent replacements and therefore
deletions in a similar manner, to enable the key K’ move up the tree
If (Ai = NULL, Aj != NULL) then choose the smallest of the key element K” from
the sub-tree pointed to by Aj, delete K” and replace K by K”
Again, deletion of K” may trigger subsequent replacements and deletions to
enable K” move up the tree
If (Ai !=NULL, Aj != NULL) then choose either the largest of the key
elements K’ in the sub-tree pointed to by Ai, or the smallest of the key
elements K” from the sub-tree pointed to by Aj to replace K
As mentioned before, to move K’ or K” up the tree it may call for subsequent
replacements and deletions
Example:
To delete 151, we search for 151 and observe that in the leaf node [148, 151,
172, 186] where it is present, both its left sub-tree pointer and right sub-tree
pointer are such that (Ai = Aj = NULL)
We therefore simply delete 151 and the node becomes [148, 172, 186].
Deletion of 92 also follows a similar process
To delete 262, we find its left and right sub-tree pointers A i and Aj respectively,
are such that (Ai = Aj = NULL)
Hence, we choose the smallest element 272 from the child node [272, 286,
350], delete 272 and replace 262 with 272. Note that, to delete 272 the
deletion procedure needs to be observed again
To delete 12, we find the node [7, 12] accommodates 12 and the key
satisfies (Ai != NULL, Aj = NULL)
Hence, we choose the largest of the keys from the node pointed to by Ai, viz.,
10 and replace 12 with 10.
