I am currently studying data structures and i am looking to see if my implementation of the insertion method in an M-way search tree is good and i am looking forward to improving my coding approach.

There are some basic cases in inserting a node in an M-way search tree:-

Basic Case: If there is still space in the node for new key.

Otherwise,

Case 1: If the data is smaller than the first key of the node then we move towards the first child.

Case 2: If the data is greater than the last node then we move towards the last child.

Case 3: According to the property we check accordingly if the value ranges between the values of two keys.

Code:

#include<iostream>
using namespace std;

struct mWay
 int index=-1;
 static const int m=3;
 int k[m-1];
 mWay *child[m]=NULL;
;

mWay* createNode(int value)
 mWay *node=new mWay;
 (node->index)++;
 node->k[node->index]=value;
 return node;


void sorting(mWay *s) //using bubble sort..
 int temp;
 for(int i=0;i<(s->index);i++)
 for(int j=0;j<(s->index);j++)
 if((s->k[j])>(s->k[j+1]))
 temp=(s->k[j]);
 (s->k[j])=(s->k[j+1]);
 (s->k[j+1])=temp;
 
 
 


mWay* Insert(int data,mWay *root)
 if(root==NULL) //creating a new mWay tree...
 root=createNode(data);
 return root;
 
 else //updating the mWay tree...
 mWay *ptr=root;
 mWay *par=NULL;
 int store; //we will store the index of next child node in this variable (in the last case)...
 while(ptr!=NULL)
 par=ptr;
 if((ptr->index)<(ptr->m)-2) //checking to see if we can insert more keys in the current node...
 (ptr->index)++;
 ptr->k[ptr->index]=data;
 sorting(ptr); //sorting keys..
 return root;
 
 else //we have to move to the next node..
 if(data<ptr->k[0]) //if the data is smaller than the first key of the node then we move towards the first child...
 ptr=ptr->child[0];
 
 else if(data>ptr->k[(ptr->m)-2]) //if the data is greater than the last node then we move towards the last child...
 ptr=ptr->child[(ptr->m)-1];
 
 else //according to the property we check accordingly if the value ranges between the values of two keys ...
 for(int i=1;i<(ptr->m)-1;i++)
 if(data>(ptr->k[i-1]) && data<(ptr->k[i]))
 store=i;
 ptr=ptr->child[i];
 break;
 
 
 
 
 //end of while loop which means we just have to insert the node now...
 if(data<(par->k[0]))
 par->child[0]=createNode(data);
 
 else if(data>(par->k[(par->m)-2]))
 par->child[(par->m)-1]=createNode(data);
 
 else
 par->child[store]=createNode(data);
 
 return root;
 

This looks more like C than C++.

The only features of C++ I see used are #include <iostream>, using namespace std; and new.

Since this is flagged c++, I will review it as such, but if it is intended to use with C, a review for that language might give better insights.

Don't reinvent the wheel

The C++ standard library provides many features that would help. Need a sorting algorithm? Use std::sort. Need to find something in a container? Use std::find, std::lower_bound, std::upper_bound or some other algorithm that suits your needs!

Naming

Many variables have very short and cryptic names. This makes the code hard to read.

Example: What does mWay::k stand for?

Issues

• Elements of <iostream> aren't used anywhere.




• using namespace std; is discouraged, especially in headers. If someone else includes that header, it might cause ambiguities in their code!

Design

C++ has classes. Why not use them to define the tree, instead of a loose set of free standing functions?

For example, a rough outline could look like this:

#include <array>
#include <memory>
#include <algorithm>

template<typename ValueType, size_t Arity>
class nary_search_tree 
 static_assert(Arity >= 2u, "Tree needs an arity greater than or equal to 2!");

 class node 
 size_t size = 0;
 std::array<ValueType, Arity-1> values;
 std::array<std::unique_ptr<node>, Arity> children;

 void insert_in_order(ValueType value) 
 auto insert_index = find_child_index(value);

 if(insert_index == size) 
 values[insert_index] = value;
 ++size;
 return;
 

 std::copy_backwards(&values[insert_index], &values[size-1], &values[size]);
 values[insert_index] = value;
 ++size;
 

 void find_child_index(ValueType value) const 
 for(auto i = 0u; i < size; ++i) 
 if(values[i] > value) return i;
 

 return size;
 

 public:
 void insert(ValueType value) 
 if(index < values.size()) 
 insert_in_order(value);
 return;
 

 auto index = find_child_index(value);
 if(!children[index]) 
 children[index] = std::make_unique<node>();
 

 children[index]->insert(value);
 
 ;

 std::unique_ptr<node> root = nullptr;

public:
 void insert(ValueType value) 
 if(!root) root = std::make_unique<node>();

 root->insert(value);
 
;

Makes reasoning much easier, doesn't it? And as a bonus, it's much more generic, too!

Note: This code requires C++11 or later to work.

Of course, this is just the beginning... This code could be improved, e.g. by using const ValueType& to prevent copies and by using overloads for ValueType&& to support movable types. Also, other search tree functionality is missing, like looking up an element

Don’t write using namespace std;.

You can, however, in a CPP file (not H file) or inside a function put individual using std::string; etc. (See SF.7.)

Forget that the legacy NULL macro ever existed. Don’t use it — ever. ⧺ES.47: Use nullptr rather than 0 or NULL

Don't write explicit comparisons against nullptr. Use the contextual conversion to bool as "OK to use".

⧺C.149 — no naked new or delete.

You should probably make this a unique_ptr as a drop-in replacement without otherwise changing the architecture.

Bubble sort?! Just call std::sort.

Prefer prefix over postfix

The biggest problem is this part of the code.

 if((ptr->index)<(ptr->m)-2) //checking to see if we can insert more keys in the current node...
 (ptr->index)++;
 ptr->k[ptr->index]=data;
 sorting(ptr); //sorting keys..
 return root;
 

Lets start with the minor problems, the sorting is a bubble sort ie. its an O(n^2) sort, not only is it slow but unneeded as we know our array is already sorted before adding a new value. So only the new value needs to be placed, we can find it with a binary search O(log n) plus a insert O(n) which together is O(n), where n is the number of values in the node.

The other thing is that this works ... as long as you haven't deleted any of the values. If you want to support delete and new inserts you have to move the child pointers too.