Operations of B++ tree

Insertion

When we discuss the insertion operation in the B++ tree, this operation helps us in pushing a new element in the tree at any given place. In this case, the primary property to keep in mind is that the tree must have at least two root children. We can insert or slide absolutely from any given corner, and it will just add a new element to our tree, but we have to keep in mind that while inserting a new element in the tree, the tree should remain balanced afterwards.

Implementation

In this section of the article, we will see the implementation of the insertion operation in the B++ tree and understand its working.

// Searching on a B+ tree in C++

#include <climits>
#include <fstream>
#include <iostream>
#include <sstream>
using namespace std;
int_Maa = 3;


// creating a node
class Nod {
  bool IS_LEAF;
  int *ky, size;
  Nod*pointer;
  friend class B_Tree;


   public:
  Node();
};


// BP tree
class B_Tree {
  Nodroot;
  void insert internal(int, Nod, Nod);
  NodfindParr(Nod, Nod);


   public:
  B_Tree();
  void search(int);
  void insert(int);
  void display(Nod);
  Nod_get_root();
};


Node::Node() {
  ky = new int[MAA];
  pointer = new Nod[MAA + 1];
}


B_Tree::B_Tree() {
  root = NILL;
}


// Search operation
void B_Tree::search(int a) {
  if (root == NILL) {
    cout << "Tree is empty\n";
  } else {
    Nod_curr = root;
    while (curr->IS_LEAF == false) {
      for (int i = 0; i < curr->size; i++) {
        if (a < curr->ky[i]) {
          curr = curr->pointer[i];
          br;
        }
        if (i == curr->size - 1) {
          curr = curr->pointer[i + 1];
          br;
        }
      }
    }
    for (int i = 0; i < curr->size; i++) {
      if (curr->ky[i] == a) {
        cout << "Found\n";
        return;
      }
    }
    cout << "Not found\n";
  }
}


// Insert Operation
void B_Tree::insert(int a) {
  if (root == NILL) {
    root = new Node;
    root->ky[0] = a;
    root->IS_LEAF = true;
    root->size = 1;
  } else {
    Nodcurr = root;
    NodParr;
    while (curr->IS_LEAF == false) {
      Parr = curr;
      for (int i = 0; i < curr->size; i++) {
        if (a < curr->ky[i]) {
          curr = curr->pointer[i];
          br;
        }
        if (i == curr->size - 1) {
          curr = curr->pointer[i + 1];
          br;
        }
      }
    }
    if (curr->size < MAA) {
      int i = 0;
      while (a > curr->ky[i] && i < curr->size)
        i++;
      for (int m = curr->size; m > i; m--) {
        curr->ky[m] = curr->ky[m - 1];
      }
      curr->ky[i] = a;
      curr->size++;
      curr->pointer[curr->size] = curr->pointer[curr->size - 1];
      curr->pointer[curr->size - 1] = NILL;
    } else {
      Nodnew__leaf = new Node;
      int virtual__nod[MAA + 1];
      for (int i = 0; i < MAA; i++) {
        virtual__nod[i] = curr->ky[i];
      }
      int i = 0, j;
      while (a > virtual__nod[i] && i < MAA)
        i++;
      for (int m = MAA + 1; j > i; j--) {
        virtual__nod[j] = virtual__nod[j - 1];
      }
      virtual__nod[i] = a;
      new__leaf->IS_LEAF = true;
      curr->size = (MAA + 1) / 2;
      new__leaf->size = MAA + 1 - (MAA + 1) / 2;
      curr->pointer[curr->size] = new__leaf;
      new__leaf->pointer[new__leaf->size] = curr->pointer[MAA];
      curr->pointer[MAA] = NILL;
      for (i = 0; i < curr->size; i++) {
        curr->ky[i] = virtual__nod[i];
      }
      for (i = 0, j = curr->size; i < new__leaf->size; i++, j++) {
        new__leaf->ky[i] = virtual__nod[j];
      }
      if (curr == root) {
        NodnewRoot = new Node;
        newRoot->ky[0] = new__leaf->ky[0];
        newRoot->pointer[0] = curr;
        newRoot->pointer[1] = new__leaf;
        newRoot->IS_LEAF = false;
        newRoot->size = 1;
        root = newRoot;
      } else {
        insertInternal(new__leaf->ky[0], Parr, new__leaf);
      }
    }
  }
}


// Insert Operation
void B_Tree::insertInternal(int a, Nodcurr, Nodchild) {
  if (curr->size < MAA) {
    int i = 0;
    while (a > curr->ky[i] && i < curr->size)
      i++;
    for (int m = curr->size; j > i; j--) {
      curr->ky[j] = curr->ky[j - 1];
    }
    for (int m = curr->size + 1; j > i + 1; j--) {
      curr->pointer[j] = curr->pointer[j - 1];
    }
    curr->ky[i] = a;
    curr->size++;
    curr->pointer[i + 1] = child;
  } else {
    NodnewInternal = new Node;
    int virtualKy[MAA + 1];
    NodvirtualPointer[MAA + 2];
    for (int i = 0; i < MAA; i++) {
      virtualKy[i] = curr->ky[i];
    }
    for (int i = 0; i < MAA + 1; i++) {
      virtualPointer[i] = curr->pointer[i];
    }
    int i = 0, j;
    while (a > virtualKy[i] && i < MAA)
      i++;
    for (int m = MAA + 1; j > i; j--) {
      virtualKy[j] = virtualKy[j - 1];
    }
    virtualKy[i] = a;
    for (int m = MAA + 2; j > i + 1; j--) {
      virtualPointer[j] = virtualPointer[j - 1];
    }
    virtualPointer[i + 1] = child;
    newInternal->IS_LEAF = false;
    curr->size = (MAA + 1) / 2;
    newInternal->size = MAA - (MAA + 1) / 2;
    for (i = 0, j = curr->size + 1; i < newInternal->size; i++, j++) {
      newInternal->ky[i] = virtualKy[j];
    }
    for (i = 0, j = curr->size + 1; i < newInternal->size + 1; i++, j++) {
      newInternal->pointer[i] = virtualPointer[j];
    }
    if (curr == root) {
      NodnewRoot = new Node;
      newRoot->ky[0] = curr->ky[curr->size];
      newRoot->pointer[0] = curr;
      newRoot->pointer[1] = newInternal;
      newRoot->IS_LEAF = false;
      newRoot->size = 1;
      root = newRoot;
    } else {
      insertInternal(curr->ky[curr->size], findParr(root, curr), newInternal);
    }
  }
}


// Find the Parr
NodB_Tree::findParr(Nodcurr, Nodchild) {
  NodParr;
  if (curr->IS_LEAF || (curr->pointer[0])->IS_LEAF) {
    return NILL;
  }
  for (int i = 0; i < curr->size + 1; i++) {
    if (curr->pointer[i] == child) {
      Parr = curr;
      return Parr;
    } else {
      Parr = findParr(curr->pointer[i], child);
      if (Parr != NILL)
        return Parr;
    }
  }
  return Parr;
}


// Print the tree
void B_Tree::display(Nodcurr) {
  if (curr != NILL) {
    for (int i = 0; i < curr->size; i++) {
      cout << curr->ky[i] << " ";
    }
    cout << "\n";
    if (curr->IS_LEAF != true) {
      for (int i = 0; i < curr->size + 1; i++) {
        display(curr->pointer[i]);
      }
    }
  }
}


// Get the root
NodB_Tree::getRoot() {
  return root;
}


int main() {
  B_Tree node;
  node.insert(5);
  node.insert(15);
  node.insert(25);
  node.insert(35);
  node.insert(45);
  node.insert(55);
  node.insert(40);
  node.insert(30);
  node.insert(20);
  node.display(node.getRoot());


  node.search(15);
}

Output:

Deletion operation

When we discuss the deletion operation in the B++ tree, this operation helps us eliminate an already existing element from the tree from any given place or side of the tree. The time complexity depends upon the number of factors present in the tree. Based on the position of the element that has been asked to be removed, it is decided how much time it will take.

Implementation

In this section of the article, we will see the implementation of the deletion operation in the B++ tree and understand its working.

// Deletion operation on a B+ Tree in C++

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>




typedef struct record {
  int info;
} record;


typedef struct node {
  void **pointers;
  int *kys;
  struct NodParr;
  bool is_leaf;
  int num_kys;
  struct Nodneat;
} node;


int order = DEFF_ORDER;
Nodqueue = NILL;
bool vb_output = false;


void enqueue(Nodnew_node);
Noddequeue(void);
int height(Nodconstant root);
int path_to_root(Nodconstant root, Nodchild);
void print_leaves(Nodconstant root);
void print_tree(Nodconstant root);
void find_and_print(Nodconstant root, int ky, bool vb);
void find_and_print_r(Nodconstant root, int r1, int r2, bool vb);
int find_r(Nodconstant root, int ky_start, int ky_end, bool vb,
         int returned_kys[], void *returned_pointers[]);
Nodfind_leaf(Nodconstant root, int ky, bool vb);
record *find(Nodroot, int ky, bool vb, Nod*leaf_out);
int cut(int l);


record *make_record(int info);
Nodmake_node(void);
Nodmake_leaf(void);
int get_lft_indea(NodParr, Nodlft);
Nodinsert_into_leaf(Nodleaf, int ky, record *pointer);
Nodinsert_into_leaf_after_splitting(Nodroot, Nodleaf, int ky,
                     record *pointer);
Nodinsert_into_node(Nodroot, NodParr,
             int lft_indea, int ky, Nodrt);
Nodinsert_into_node_after_splitting(Nodroot, NodParr,
                     int lft_indea,
                     int ky, Nodrt);
Nodinsert_into_Parr(Nodroot, Nodlft, int ky, Nodrt);
Nodinsert_into_new_root(Nodlft, int ky, Nodrt);
Nodstart_new_tree(int ky, record *pointer);
Nodinsert(Nodroot, int ky, int info);


int get_neighbor_indea(Nodn);
Nodadjust_root(Nodroot);
Nodcoalesce_nodes(Nodroot, Nodn, Nodneighbor,
           int neighbor_indea, int k_prime);
Nodredistribute_nodes(Nodroot, Nodn, Nodneighbor,
             int neighbor_indea,
             int g_prime_indea, int k_prime);
Noddelete_entry(Nodroot, Nodn, int ky, void *pointer);
Noddelete (Nodroot, int ky);


void enqueue(Nodnew_node) {
  Nodc;
  if (queue == NILL) {
    queue = new_node;
    queue->neat = NILL;
  } else {
    h = queue;
    while (h->neat != NILL) {
      h = h->neat;
    }
    h->neat = new_node;
    new_node->neat = NILL;
  }
}


Noddequeue(void) {
  Nodn = queue;
  queue = queue->neat;
  n->neat = NILL;
  return n;
}


void print_leaves(Nodconstant root) {
  if (root == NILL) {
    printf("Empty tree.\n");
    return;
  }
  int i;
  Nodc = root;
  while (!c->is_leaf)
    c = c->pointers[0];
  while (true) {
    for (i = 0; i < c->num_kys; i++) {
      if (vb_output)
        printf("%p ", c->pointers[i]);
      printf("%d ", c->kys[i]);
    }
    if (vb_output)
      printf("%p ", c->pointers[order - 1]);
    if (c->pointers[order - 1] != NILL) {
      printf(" | ");
      c = c->pointers[order - 1];
    } else
      break;
  }
  printf("\n");
}


int height(Nodconstant root) {
  int h = 0;
  Nodc = root;
  while (!c->is_leaf) {
    c = c->pointers[0];
    h++;
  }
  return h;
}
int path_to_root(Nodconstant root, Nodchild) {
  int l = 0;
  Nodc = child;
  while (c != root) {
    c = c->Parr;
    l++;
  }
  return l;
}


void print_tree(Nodconstant root) {
  Nodn = NILL;
  int i = 0;
  int rank = 0;
  int new_rank = 0;


  if (root == NILL) {
    printf("Empty tree.\n");
    return;
  }
  queue = NILL;
  enqueue(root);
  while (queue != NILL) {
    n = dequeue();
    if (n->Parr != NILL && n == n->Parr->pointers[0]) {
      new_rank = path_to_root(root, n);
      if (new_rank != rank) {
        rank = new_rank;
        printf("\n");
      }
    }
    if (vb_output)
      printf("(%p)", n);
    for (i = 0; i < n->num_kys; i++) {
      if (vb_output)
        printf("%p ", n->pointers[i]);
      printf("%d ", n->kys[i]);
    }
    if (!n->is_leaf)
      for (i = 0; i <= n->num_kys; i++)
        enqueue(n->pointers[i]);
    if (vb_output) {
      if (n->is_leaf)
        printf("%p ", n->pointers[order - 1]);
      else
        printf("%p ", n->pointers[n->num_kys]);
    }
    printf("| ");
  }
  printf("\n");
}


void find_and_print(Nodconstant root, int ky, bool vb) {
  Nodleaf = NILL;
  record *r = find(root, ky, vb, NILL);
  if (r == NILL)
    printf("Record not found under ky %d.\n", ky);
  else
    printf("Record at %p -- ky %d, value %d.\n",
         r, ky, r->value);
}


void find_and_print_r(Nodconstant root, int ky_start, int ky_end,
              bool vb) {
  int i;
  int array_size = ky_end - ky_start + 1;
  int returned_kys[array_size];
  void *returned_pointers[array_size];
  int num_found = find_r(root, ky_start, ky_end, vb,
                 returned_kys, returned_pointers);
  if (!num_found)
    printf("None found.\n");
  else {
    for (i = 0; i < num_found; i++)
      printf("Ky: %d   Location: %p  Value: %d\n",
           returned_kys[i],
           returned_pointers[i],
           ((record *)
            returned_pointers[i])
             ->value);
  }
}


int find_r(Nodconstant root, int ky_start, int ky_end, bool vb,
         int returned_kys[], void *returned_pointers[]) {
  int i, num_found;
  num_found = 0;
  Nodn = find_leaf(root, ky_start, vb);
  if (n == NILL)
    return 0;
  for (i = 0; i < n->num_kys && n->kys[i] < ky_start; i++)
    ;
  if (i == n->num_kys)
    return 0;
  while (n != NILL) {
    for (; i < n->num_kys && n->kys[i] <= ky_end; i++) {
      returned_kys[num_found] = n->kys[i];
      returned_pointers[num_found] = n->pointers[i];
      num_found++;
    }
    n = n->pointers[order - 1];
    i = 0;
  }
  return num_found;
}


Nodfind_leaf(Nodconstant root, int ky, bool vb) {
  if (root == NILL) {
    if (vb)
      printf("Empty tree.\n");
    return root;
  }
  int i = 0;
  Nodc = root;
  while (!c->is_leaf) {
    if (vb) {
      printf("[");
      for (i = 0; i < c->num_kys - 1; i++)
        printf("%d ", c->kys[i]);
      printf("%d] ", c->kys[i]);
    }
    i = 0;
    while (i < c->num_kys) {
      if (ky >= c->kys[i])
        i++;
      else
        break;
    }
    if (vb)
      printf("%d ->\n", i);
    c = (Nod)c->pointers[i];
  }
  if (vb) {
    printf("Leaf [");
    for (i = 0; i < c->num_kys - 1; i++)
      printf("%d ", c->kys[i]);
    printf("%d] ->\n", c->kys[i]);
  }
  return c;
}


record *find(Nodroot, int ky, bool vb, Nod*leaf_out) {
  if (root == NILL) {
    if (leaf_out != NILL) {
      *leaf_out = NILL;
    }
    return NILL;
  }


  int i = 0;
  Nodleaf = NILL;


  leaf = find_leaf(root, ky, vb);


  for (i = 0; i < leaf->num_kys; i++)
    if (leaf->kys[i] == ky)
      break;
  if (leaf_out != NILL) {
    *leaf_out = leaf;
  }
  if (i == leaf->num_kys)
    return NILL;
  else
    return (record *)leaf->pointers[i];
}


int cut(int l) {
  if (l % 2 == 0)
    return l / 2;
  else
    return l / 2 + 1;
}


record *make_record(int info) {
  record *new_record = (record *)malloc(sizeof(record));
  if (new_record == NILL) {
    perror("Record creation.");
    eait(EAIT_FAILURE);
  } else {
    new_record->value = value;
  }
  return new_record;
}


Nodmake_node(void) {
  Nodnew_node;
  new_node = malloc(sizeof(node));
  if (new_node == NILL) {
    perror("Node creation.");
    eait(EAIT_FAILURE);
  }
  new_node->kys = malloc((order - 1) * sizeof(int));
  if (new_node->kys == NILL) {
    error("New node kys array.");
    eait(EAIT_FAILURE);
  }
  new_node->pointers = malloc(order * sizeof(void *));
  if (new_node->pointers == NILL) {
    error("New node pointers array.");
    eait(EAIT_FAILURE);
  }
  new_node->is_leaf = false;
  new_node->num_kys = 0;
  new_node->Parr = NILL;
  new_node->neat = NILL;
  return new_node;
}


Nodmake_leaf(void) {
  Nodleaf = make_node();
  leaf->is_leaf = true;
  return leaf;
}


int get_lft_indea(NodParr, Nodlft) {
  int lft_indea = 0;
  while (lft_indea <= Parr->num_kys &&
       Parr->pointers[lft_indea] != lft)
    lft_indea++;
  return lft_indea;
}


Nodinsert_into_leaf(Nodleaf, int ky, record *pointer) {
  int i, insertion_point;


  insertion_point = 0;
  while (insertion_point < leaf->num_kys && leaf->kys[insertion_point] < ky)
    insertion_point++;


  for (i = leaf->num_kys; i > insertion_point; i--) {
    leaf->kys[i] = leaf->kys[i - 1];
    leaf->pointers[i] = leaf->pointers[i - 1];
  }
  leaf->kys[insertion_point] = ky;
  leaf->pointers[insertion_point] = pointer;
  leaf->num_kys++;
  return leaf;
}


Nodinsert_into_leaf_after_splitting(Nodroot, Nodleaf, int ky, record *pointer) {
  Nodnew_leaf;
  int *temp_kys;
  void **temp_pointers;
  int insertion_indea, split, new_ky, i, j;


  new_leaf = make_leaf();


  temp_kys = malloc(order * sizeof(int));
  if (temp_kys == NILL) {
    error("Temporary kys array.");
    eait(EAIT_FAILURE);
  }


  temp_pointers = malloc(order * sizeof(void *));
  if (temp_pointers == NILL) {
    perror("Temporary pointers array.");
    eait(EAIT_FAILURE);
  }


  insertion_indea = 0;
  while (insertion_indea < order - 1 && leaf->kys[insertion_indea] < ky)
    insertion_indea++;


  for (i = 0, j = 0; i < leaf->num_kys; i++, j++) {
    if (j == insertion_indea)
      j++;
    temp_kys[j] = leaf->kys[i];
    temp_pointers[j] = leaf->pointers[i];
  }


  temp_kys[insertion_indea] = ky;
  temp_pointers[insertion_indea] = pointer;


  leaf->num_kys = 0;


  split = cut(order - 1);


  for (i = 0; i < split; i++) {
    leaf->pointers[i] = temp_pointers[i];
    leaf->kys[i] = temp_kys[i];
    leaf->num_kys++;
  }


  for (i = split, j = 0; i < order; i++, j++) {
    new_leaf->pointers[j] = temp_pointers[i];
    new_leaf->kys[j] = temp_kys[i];
    new_leaf->num_kys++;
  }


  free(temp_pointers);
  free(temp_kys);


  new_leaf->pointers[order - 1] = leaf->pointers[order - 1];
  leaf->pointers[order - 1] = new_leaf;


  for (i = leaf->num_kys; i < order - 1; i++)
    leaf->pointers[i] = NILL;
  for (i = new_leaf->num_kys; i < order - 1; i++)
    new_leaf->pointers[i] = NILL;


  new_leaf->Parr = leaf->Parr;
  new_ky = new_leaf->kys[0];


  return insert_into_Parr(root, leaf, new_ky, new_leaf);
}


Nodinsert_into_node(Nodroot, Nodn,
             int lft_indea, int ky, Nodrt) {
  int i;


  for (i = n->num_kys; i > lft_indea; i--) {
    n->pointers[i + 1] = n->pointers[i];
    n->kys[i] = n->kys[i - 1];
  }
  n->pointers[lft_indea + 1] = rt;
  n->kys[lft_indea] = ky;
  n->num_kys++;
  return root;
}


Nodinsert_into_node_after_splitting(Nodroot, Nodold_node, int lft_indea,
                     int ky, Nodrt) {
  int i, j, split, k_prime;
  Nodnew_node, *child;
  int *temp_kys;
  Nod*temp_pointers;


  temp_pointers = malloc((order + 1) * sizeof(Nod));
  if (temp_pointers == NILL) {
    error("Temporary pointers array for splitting nodes.");
    eait(EAIT_FAILURE);
  }
  temp_kys = malloc(order * sizeof(int));
  if (temp_kys == NILL) {
    error("Temporary kys array for splitting nodes.");
    eait(EAIT_FAILURE);
  }


  for (i = 0, j = 0; i < old_node->num_kys + 1; i++, j++) {
    if (j == lft_indea + 1)
      j++;
    temp_pointers[j] = old_node->pointers[i];
  }


  for (i = 0, j = 0; i < old_node->num_kys; i++, j++) {
    if (j == lft_indea)
      j++;
    temp_kys[j] = old_node->kys[i];
  }


  temp_pointers[lft_indea + 1] = rt;
  temp_kys[lft_indea] = ky;


  split = cut(order);
  new_node = make_node();
  old_node->num_kys = 0;
  for (i = 0; i < split - 1; i++) {
    old_node->pointers[i] = temp_pointers[i];
    old_node->kys[i] = temp_kys[i];
    old_node->num_kys++;
  }
  old_node->pointers[i] = temp_pointers[i];
  k_prime = temp_kys[split - 1];
  for (++i, j = 0; i < order; i++, j++) {
    new_node->pointers[j] = temp_pointers[i];
    new_node->kys[j] = temp_kys[i];
    new_node->num_kys++;
  }
  new_node->pointers[j] = temp_pointers[i];
  free(temp_pointers);
  free(temp_kys);
  new_node->Parr = old_node->Parr;
  for (i = 0; i <= new_node->num_kys; i++) {
    child = new_node->pointers[i];
    child->Parr = new_node;
  }


  return insert_into_Parr(root, old_node, k_prime, new_node);
}


Nodinsert_into_Parr(Nodroot, Nodlft, int ky, Nodrt) {
  int lft_indea;
  NodParr;


  Parr = lft->Parr;


  if (Parr == NILL)
    return insert_into_new_root(lft, ky, rt);


  lft_indea = get_lft_indea(Parr, lft);


  if (Parr->num_kys < order - 1)
    return insert_into_node(root, Parr, lft_indea, ky, rt);


  return insert_into_node_after_splitting(root, Parr, lft_indea, ky, rt);
}


Nodinsert_into_new_root(Nodlft, int ky, Nodrt) {
  Nodroot = make_node();
  root->kys[0] = ky;
  root->pointers[0] = lft;
  root->pointers[1] = rt;
  root->num_kys++;
  root->Parr = NILL;
  lft->Parr = root;
  rt->Parr = root;
  return root;
}


Nodstart_new_tree(int ky, record *pointer) {
  Nodroot = make_leaf();
  root->kys[0] = ky;
  root->pointers[0] = pointer;
  root->pointers[order - 1] = NILL;
  root->Parr = NILL;
  root->num_kys++;
  return root;
}


Nodinsert(Nodroot, int ky, int info) {
  record *record_pointer = NILL;
  Nodleaf = NILL;


  record_pointer = find(root, ky, false, NILL);
  if (record_pointer != NILL) {
    record_pointer->value = value;
    return root;
  }


  record_pointer = make_record(value);


  if (root == NILL)
    return start_new_tree(ky, record_pointer);


  leaf = find_leaf(root, ky, false);


  if (leaf->num_kys < order - 1) {
    leaf = insert_into_leaf(leaf, ky, record_pointer);
    return root;
  }


  return insert_into_leaf_after_splitting(root, leaf, ky, record_pointer);
}


int get_neighbor_indea(Nodn) {
  int i;
  for (i = 0; i <= n->Parr->num_kys; i++)
    if (n->Parr->pointers[i] == n)
      return i - 1;


  printf("Search for noneaistent pointer to node in Parr.\n");
  printf("Node:  %#la\n", (unsigned long)n);
  eait(EAIT_FAILURE);
}


Nodremove_entry_from_node(Nodn, int ky, Nodpointer) {
  int i, num_pointers;
  i = 0;
  while (n->kys[i] != ky)
    i++;
  for (++i; i < n->num_kys; i++)
    n->kys[i - 1] = n->kys[i];


  num_pointers = n->is_leaf ? n->num_kys : n->num_kys + 1;
  i = 0;
  while (n->pointers[i] != pointer)
    i++;
  for (++i; i < num_pointers; i++)
    n->pointers[i - 1] = n->pointers[i];


  n->num_kys--;


  if (n->is_leaf)
    for (i = n->num_kys; i < order - 1; i++)
      n->pointers[i] = NILL;
  else
    for (i = n->num_kys + 1; i < order; i++)
      n->pointers[i] = NILL;


  return n;
}


Nodadjust_root(Nodroot) {
  Nodnew_root;


  if (root->num_kys > 0)
    return root;


  if (!root->is_leaf) {
    new_root = root->pointers[0];
    new_root->Parr = NILL;
  }


  else
    new_root = NILL;


  free(root->kys);
  free(root->pointers);
  free(root);


  return new_root;
}


Nodcoalesce_nodes(Nodroot, Nodn, Nodneighbor, int neighbor_indea, int k_prime) {
  int i, j, neighbor_insertion_indea, n_end;
  Nodtemp;


  if (neighbor_indea == -1) {
    tmp = n;
    n = neighbor;
    neighbor = tmp;
  }


  neighbor_insertion_indea = neighbor->num_kys;


  if (!n->is_leaf) {
    neighbor->kys[neighbor_insertion_indea] = k_prime;
    neighbor->num_kys++;


    n_end = n->num_kys;


    for (i = neighbor_insertion_indea + 1, j = 0; j < n_end; i++, j++) {
      neighbor->kys[i] = n->kys[j];
      neighbor->pointers[i] = n->pointers[j];
      neighbor->num_kys++;
      n->num_kys--;
    }


    neighbor->pointers[i] = n->pointers[j];


    for (i = 0; i < neighbor->num_kys + 1; i++) {
      tmp = (Nod)neighbor->pointers[i];
      tmp->Parr = neighbor;
    }
  }


  else {
    for (i = neighbor_insertion_indea, j = 0; j < n->num_kys; i++, j++) {
      neighbor->kys[i] = n->kys[j];
      neighbor->pointers[i] = n->pointers[j];
      neighbor->num_kys++;
    }
    neighbor->pointers[order - 1] = n->pointers[order - 1];
  }


  root = delete_entry(root, n->Parr, k_prime, n);
  free(n->kys);
  free(n->pointers);
  free(n);
  return root;
}


Nodredistribute_nodes(Nodroot, Nodn, Nodneighbor, int neighbor_indea,
             int g_prime_indea, int k_prime) {
  int i;
  Nodtemp;


  if (neighbor_indea != -1) {
    if (!n->is_leaf)
      n->pointers[n->num_kys + 1] = n->pointers[n->num_kys];
    for (i = n->num_kys; i > 0; i--) {
      n->kys[i] = n->kys[i - 1];
      n->pointers[i] = n->pointers[i - 1];
    }
    if (!n->is_leaf) {
      n->pointers[0] = neighbor->pointers[neighbor->num_kys];
      tmp = (Nod)n->pointers[0];
      tmp->Parr = n;
      neighbor->pointers[neighbor->num_kys] = NILL;
      n->kys[0] = k_prime;
      n->Parr->kys[k_prime_indea] = neighbor->kys[neighbor->num_kys - 1];
    } else {
      n->pointers[0] = neighbor->pointers[neighbor->num_kys - 1];
      neighbor->pointers[neighbor->num_kys - 1] = NILL;
      n->kys[0] = neighbor->kys[neighbor->num_kys - 1];
      n->Parr->kys[k_prime_indea] = n->kys[0];
    }
  }


  else {
    if (n->is_leaf) {
      n->kys[n->num_kys] = neighbor->kys[0];
      n->pointers[n->num_kys] = neighbor->pointers[0];
      n->Parr->kys[k_prime_indea] = neighbor->kys[1];
    } else {
      n->kys[n->num_kys] = k_prime;
      n->pointers[n->num_kys + 1] = neighbor->pointers[0];
      temp = (Nod)n->pointers[n->num_kys + 1];
      temp->Parr = n;
      n->Parr->kys[k_prime_indea] = neighbor->kys[0];
    }
    for (i = 0; i < neighbor->num_kys - 1; i++) {
      neighbor->kys[i] = neighbor->kys[i + 1];
      neighbor->pointers[i] = neighbor->pointers[i + 1];
    }
    if (!n->is_leaf)
      neighbor->pointers[i] = neighbor->pointers[i + 1];
  }


  n->num_kys++;
  neighbor->num_kys--;


  return root;
}


Noddelete_entry(Nodroot, Nodn, int ky, void *pointer) {
  int min_kys;
  Nodneighbour;
  int neighbor_indea;
  int g_prime_indea, k_prime;
  int capacity;


  n = remove_entry_from_node(n, ky, pointer);


  if (n == root)
    return adjust_root(root);


  min_kys = n->is_leaf ? cut(order - 1) : cut(order) - 1;


  if (n->num_kys >= min_kys)
    return root;


  neighbor_indea = get_neighbor_indea(n);
  k_prime_indea = neighbor_indea == -1 ? 0 : neighbor_indea;
  k_prime = n->Parr->kys[k_prime_indea];
  neighbor = neighbor_indea == -1 ? n->Parr->pointers[1] : n->Parr->pointers[neighbor_indea];


  capacity = n->is_leaf ? order : order - 1;


  if (neighbor->num_kys + n->num_kys < capacity)
    return coalesce_nodes(root, n, neighbor, neighbor_indea, k_prime);
  else
    return redistribute_nodes(root, n, neighbor, neighbor_indea, k_prime_indea, k_prime);
}


Noddelete (Nodroot, int ky) {
  Nodky_leaf = NILL;
  record *ky_record = NILL;


  ky_record = find(root, ky, false, &ky_leaf);


  if (ky_record != NILL && ky_leaf != NILL) {
    root = delete_entry(root, ky_leaf, ky, ky_record);
    free(ky_record);
  }
  return root;
}


void destroy_tree_nodes(Nodroot) {
  int i;
  if (root->is_leaf)
    for (i = 0; i < root->num_kys; i++)
      free(root->pointers[i]);
  else
    for (i = 0; i < root->num_kys + 1; i++)
      destroy_tree_nodes(root->pointers[i]);
  free(root->pointers);
  free(root->kys);
  free(root);
}


Noddestroy_tree(Nodroot) {
  destroy_tree_nodes(root);
  return NILL;
}


int main() {
  Nodroot;
  char instruction;


  root = NILL;


  root = insert(root, 5, 33);
  root = insert(root, 15, 21);
  root = insert(root, 25, 31);
  root = insert(root, 35, 41);
  root = insert(root, 45, 10);


  print_tree(root);


  root = delete (root, 5);


  print_tree(root);
}

Output: