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(log
m
(n))
time.
The m-way search trees possess some of the following properties:
Children: The maximum number of children for a node is m
.
Elements: The maximum number of elements in a node are m-1
elements.
Height: The maximum height is equal to the total number of elements n
, and the minimum height equals log
m
n+1
Searching: Best time complexity to search for an element from the tree is O(log
m
(n))
. The worst time is to search in linear time, i.e., O(n)
.
Balancing: The search time of O(log
m
(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.
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.
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:
To search for an element, we will adhere to the following steps:
We start from the first element of the root node.
If the current value equals the required value, we have found the element; otherwise, we move to step 3.
If the required element is smaller than the current element;
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.
If the left subtree does not exist, our required element is not in the tree.
If the required element is greater than the current element, we check the value of the next element of the node;
If the value exists;
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.
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.
If the value does not exist;
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.
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 treestruct 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 treebool 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 subtreeif (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 nodeif (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 treeNode* 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 treeint 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
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 nullptr
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.
M-way search trees have a maximum of m
children and m-1
elements in a node. To optimize searching efficiency to O(log
m
n)
, balancing techniques are used.
Free Resources