# Insertion of a node in M-way search tree

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){     //if the data is smaller than the first key of the node then we move towards the first child...
ptr=ptr->child;
}
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)){
par->child=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;
}
}

• Do you mind adding a little more information about M-Way search trees for those of us not familiar with the data structure? – Dannnno Jul 13 '18 at 21:32
• @Dannnno I am so sorry for replying late. I forgot to reply you. Here is the detail for this data structure (although i think you have already studied about it ;) ) : webdocs.cs.ualberta.ca/~holte/T26/m-way-trees.html – sazharsha Aug 4 '18 at 7:06

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 , 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

• It seems that there is much to learn. I am a beginner and a student who is taking this DS and A course. My aim was to implement this data structure from scratch all by myself :) maybe this is the reason it looks for like C. I should’ve done this in C then. oh well. Thank you :) – sazharsha Jul 14 '18 at 6:33
• @sazharsha: The intention behind data structures is structuring data in order to better reason about it. The intention behind classes is to structure behavior in order to better reason about it :) The C style implementation of the data structure works, but reasoning about what it does is a lot harder IMO. Often, it's easy to implement data structure as classes, since their behavior easily maps to methods. In any way, extracting helper functions nearly always improves readability and reusability, so try to do so if possible. – hoffmale Jul 14 '18 at 9:20

# 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.

• ohh. I have only implemented insertion method. i will implement this including deletion and searching in B tree. Half of this DSA course is still left and its giving me a hard time. – sazharsha Jul 14 '18 at 9:01
• i still didn’t get the sorting part.I want all the elements in the array of the node to be in sorted order after inserting a new one (which is not possible every time) so i implemented bubble sort for that ,in this multi way search tree. – sazharsha Jul 14 '18 at 9:11
• I'd use a linear search (see the snippet in my answer) instead of binary search. If the arity of the tree is big enough that binary search gives a measurable performance win, then reducing the arity of the tree would likely result in the same performance win, if not better. ($\log{2}(n)$ vs $\log{Arity}(n)$) – hoffmale Jul 14 '18 at 9:16
• After seeing the latest iteration of Alexandescu's Fastware from NDC I have to agree with you that linear search is better for small arities. – Surt Jul 19 '18 at 22:04