M-Way Trees

M-Way Trees

An M-way tree is a generalization of a binary tree where each node can have up to $M$ children. These trees are often used in databases and file systems, particularly in the context of indexing and storing large amounts of data.

Key Characteristics

1. Node Structure:

   • Each node can contain up to $M - 1$ keys.
   • Each key divides the node into $M$ subtrees.
   • The keys within a node are sorted in non-decreasing order.

2. Height: The height of an M-way tree is generally kept low to ensure efficient search, insert, and delete operations.

3. Balanced: M-way trees are usually kept balanced to ensure that the height remains logarithmic relative to the number of keys.

Properties of M-Way Trees

• Degree: The maximum number of children a node can have is $M$. The minimum number of children (except for the root) is $\lceil M/2 \rceil$.
• Search Complexity: The search operation in an M-way tree can be performed in $O(\log_M n)$, where $n$ is the number of keys in the tree.
• Insertion and Deletion: Both operations are performed in $O(\log_M n)$ as well, with the need to maintain balance.

Basic Operations

1. Search: Finding a key in the tree.
2. Insertion: Adding a new key and ensuring the node properties are maintained.
3. Deletion: Removing a key and maintaining the tree structure.
4. Traversal: Visiting nodes in a specific order (e.g., in-order, pre-order).

Example Structure of an M-Way Tree Node

Here’s how you might define a node for an M-way tree in C++:

#include <iostream>
#include <vector>
using namespace std;

class MWayNode {
public:
    vector<int> keys;            // Vector to store keys
    vector<MWayNode*> children;  // Vector to store child pointers
    bool isLeaf;                 // Indicates if the node is a leaf

    MWayNode(int M) : isLeaf(true) {
        keys.reserve(M - 1);
        children.reserve(M);
    }
};

M-Way Tree Class with Basic Operations

Here’s a simple implementation of an M-way tree focusing on insertion and search:

class MWayTree {
private:
    MWayNode* root;
    int M;

    void insertNonFull(MWayNode* node, int key) {
        int i = node->keys.size() - 1;

        if (node->isLeaf) {
            // Find the position to insert the new key
            while (i >= 0 && key < node->keys[i]) {
                i--;
            }
            node->keys.insert(node->keys.begin() + i + 1, key); // Insert key
        } else {
            // Find the child to descend into
            while (i >= 0 && key < node->keys[i]) {
                i--;
            }
            i++;
            if (children[i]->keys.size() == M - 1) { // Child is full
                splitChild(node, i);
                if (key > node->keys[i]) { // Decide which child to continue with
                    i++;
                }
            }
            insertNonFull(node->children[i], key); // Recursive insert
        }
    }

    void splitChild(MWayNode* parent, int index) {
        MWayNode* fullChild = parent->children[index];
        MWayNode* newChild = new MWayNode(M);

        // Move half of the keys and children to the new child
        for (int j = 0; j < M / 2; j++) {
            newChild->keys.push_back(fullChild->keys[j + M / 2]);
        }
        if (!fullChild->isLeaf) {
            for (int j = 0; j < (M / 2) + 1; j++) {
                newChild->children.push_back(fullChild->children[j + M / 2]);
            }
        }
        
        // Reduce the number of keys in the full child
        fullChild->keys.resize(M / 2);

        // Insert the new child into the parent
        parent->children.insert(parent->children.begin() + index + 1, newChild);
        parent->keys.insert(parent->keys.begin() + index, fullChild->keys.back());
    }

public:
    MWayTree(int m) : M(m) {
        root = new MWayNode(M);
    }

    void insert(int key) {
        if (root->keys.size() == M - 1) { // Root is full
            MWayNode* newRoot = new MWayNode(M);
            newRoot->isLeaf = false;
            newRoot->children.push_back(root);
            splitChild(newRoot, 0);
            insertNonFull(newRoot, key);
            root = newRoot; // Update root
        } else {
            insertNonFull(root, key);
        }
    }

    bool search(MWayNode* node, int key) {
        int i = 0;
        while (i < node->keys.size() && key > node->keys[i]) {
            i++;
        }
        if (i < node->keys.size() && node->keys[i] == key) {
            return true; // Found the key
        }
        if (node->isLeaf) {
            return false; // Key not found
        }
        return search(node->children[i], key); // Search in the child
    }

    bool search(int key) {
        return search(root, key);
    }
};

int main() {
    MWayTree tree(3); // Creating a 3-way tree

    tree.insert(10);
    tree.insert(20);
    tree.insert(5);
    tree.insert(6);
    tree.insert(12);
    
    cout << "Searching for 12: " << (tree.search(12) ? "Found" : "Not Found") << endl; // Output: Found
    cout << "Searching for 15: " << (tree.search(15) ? "Found" : "Not Found") << endl; // Output: Not Found

    return 0;
}

Explanation of the Code

1. Node Class: MWayNode contains vectors for keys and children, as well as a boolean to indicate if it’s a leaf.
2. MWayTree Class:
   • Insertion: The insert method manages inserting keys and handling full nodes by splitting them when necessary.
   • Searching: The search method recursively searches for a key in the M-way tree.
   • Split Child: This method handles splitting a full child into two and promoting a key to the parent.

Complexity Analysis

• Search: $O(\log_M n)$
• Insertion: $O(\log_M n)$
• Deletion: $O(\log_M n)$, although deletion requires more complex handling than insertion.

Applications of M-Way Trees

1. Databases: Used for indexing large datasets where quick search and retrieval are required.
2. File Systems: Employed in structures like B-trees to manage files efficiently.
3. Storage Systems: Useful in managing large amounts of sorted data.

Conclusion

M-way trees are powerful data structures that extend the capabilities of binary trees. Their balanced nature allows for efficient search, insertion, and deletion operations, making them particularly useful in databases and file systems. Understanding M-way trees helps in optimizing data management for large datasets.