What is the m-way search tree?

The m-way search trees are self-balanced trees used to search or retrieve data efficiently. m represents the maximum number of children for a node in the tree. Binary trees are also called 2-way search trees as they have a maximum of two children. The m-way search tree's primary use is to optimize searching and attain the best O(logm(n)) time.

Examples of m-way search trees
Examples of m-way search trees

Properties

The m-way search trees possess some of the following properties:

  1. Children: The maximum number of children for a node is m.

  2. Elements: The maximum number of elements in a node are m-1 elements.

  3. Height: The maximum height is equal to the total number of elements n, and the minimum height equals logmn+1

  4. Searching: Best time complexity to search for an element from the tree is O(logm(n)). The worst time is to search in linear time, i.e., O(n).

  5. Balancing: The search time of O(logm(n)) is achieved by applying different balancing techniques. For example, B-Trees are self-balancing m-way trees that ensure the maintenance of at least [m/2] children except for the root node.

  6. Elements arrangement: Elements in a node are arranged in ascending order. Elements in the left subtree are smaller than the key value of the root element. Similarly, elements in the right subtree are greater than the key value of the root element. Elements in the middle subtree of two elements are greater than the left parent and smaller than the right parent.

Note: To understand the insertion of elements in an m-way search tree, you may visit the link.

Example

To explain searching in an m-way tree, let us consider the example in the slides below. The tree shows a 5-array tree with a maximum number of m-1 elements, i.e., 4. Our goal is to search for the element with a value of 45. A complete illustration to search for the element is shown below:

Search for 45
Search for 45
1 of 7

Searching algorithm

To search for an element, we will adhere to the following steps:

  1. We start from the first element of the root node.

  2. If the current value equals the required value, we have found the element; otherwise, we move to step 3.

  3. If the required element is smaller than the current element;

    1.  We check if the left subtree exists and move to the left subtree, and point to the first element. After that, we move back to step 2. 

    2. If the left subtree does not exist, our required element is not in the tree.

  4. If the required element is greater than the current element, we check the value of the next element of the node;

    1. If the value exists;

      1. We check if it is smaller than or equal to the required element and move the current element to the next element. After that, we move back to step 2. 

      2. If it is greater than the required element, we move to the right subtree of the current element and go back to step 2. If the right subtree does not exist, the required value is absent in the tree.

    2. If the value does not exist;

      1. We check if the right subtree exists, move to the right subtree of the current element, and move back to step 2. If the right subtree does not exist, the required value is absent in the tree.

Coding example

All m-way trees use the same searching technique. The code to search for an element in an m-way search tree is given below:

#include <iostream>
using namespace std;
// Node structure for m-way tree
struct Node {
int data;
Node* leftSubtree;
Node* rightSubtree;
Node* next;
Node(int val) {
data = val;
leftSubtree = nullptr;
rightSubtree = nullptr;
next = nullptr;
}
};
// Function to search for a value in an m-way tree
bool searchMArrayTree(Node* root, int target) {
if (root == nullptr) {
return false; // If the root is null, value is not found
}
if (root->data == target) {
return true; // If the root's data matches the target, value is found
}
// Search in the left subtree
if (target < root->data && root->leftSubtree != nullptr) {
return searchMArrayTree(root->leftSubtree, target); // Recursively search in the left subtree
}
// Search in the right subtree or next element of the node
if (target > root->data) {
if (root->next != nullptr && target >= root->next->data){
return searchMArrayTree(root->next , target); // If there is a next node in the same level and target is greater than the next node's data, search in the next node
}
if (root->rightSubtree != nullptr){
return searchMArrayTree(root->rightSubtree, target); // If there is a right subtree, recursively search in the right subtree
}
}
return false; // Target not found
}
int main() {
// Create an example m-ary tree
Node* root = new Node(18);
root->next = new Node(54);
root->next->next = new Node(86);
root->next->next->next = new Node(400);
root->leftSubtree = new Node(5);
root->leftSubtree->next = new Node(10);
root->leftSubtree->rightSubtree = new Node(7);
root->leftSubtree->rightSubtree->next = new Node(9);
root->rightSubtree = new Node(25);
root->rightSubtree->next = new Node(35);
root->rightSubtree->next->next = new Node(40);
root->rightSubtree->leftSubtree = new Node(19);
root->rightSubtree->leftSubtree->next = new Node(20);
root->rightSubtree->leftSubtree->next->next = new Node(21);
root->rightSubtree->leftSubtree->next->next->next = new Node(22);
root->rightSubtree->next->next->rightSubtree = new Node(45);
root->next->next->next->rightSubtree = new Node(450);
root->next->next->next->rightSubtree->next = new Node(470);
// Search for a value in the tree
int target;
cin >> target;
bool found = searchMArrayTree(root, target);
if (found) {
cout << "Value " << target << " found in the m-way tree." << endl;
} else {
cout << "Value " << target << " not found in the m-way tree." << endl;
}
return 0;
}

Enter the input below

C++ code to search for an element in an m-way tree

Code explanation

  • Lines 6–18: We create a Node of type struct. The Node contains information on its data and three links. One link is to the Node of the left subtree, one to the Node of the right subtree, and one to the next Node on the same level.

  • Lines 21–45: We define the searchMArrayTree function.

  • Lines 22–24: We check if the current Node has a nullptrnullptr means null pointer. We use nullptr when we want to show that the link does not exist.. If we find nullptr, we return false. This means the number we are searching for does not exist in the m-way search tree.

  • Lines 26–28: We check if the current node's data equals the required number and return true if it matches.

  • Lines 31–33: We check if the required number is lesser than the current node's data and if the left subtree exists. If the conditions are true, we search for the target number in the left subtree.

  • Lines 35–42: We check if the target number is greater than the current node's data. If it is true, we check if the next element to the current node exists and if the data in the next node is greater than or equal to the target number. If true, we search for the target number in the same level as the current node. Otherwise, we check if the right subtree exists and search for the target number in the right subtree.

Conclusion

M-way search trees have a maximum of m children and m-1 elements in a node. To optimize searching efficiency to O(logmn), balancing techniques are used.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved