B+ Tree in Data Structure (DBMS) Properties & Operation

//A C++ function to delete keys from b+ tree in data structure 

Node *bptree::findparent(Node *csr, Node *child) {

  Node *parent;

  if (csr->isleaf || (csr->ptr[0])->isleaf) {

    return NULL;

  }

//a for loop to locate parent

  for (int j = 0; j < csr->size + 1; j++) {

    if (csr->ptr[j] == child) {

      parent = csr;

      return parent;

    } else {

      parent = findparent(csr->ptr[j], child);

  .

    if (parent != NULL)

        return parent;

    }

  }

  return parent;

}

void bptree::remove(int x) {

  if (root == NULL) {

    cout << "Tree is empty\n";

  } else {

    Node *csr = root;

    Node *parent;

    int ltsibling, rtsibling;

    while (csr->isleaf == false) {

      for (int j = 0; j < csr->size; j++) {

        parent = csr;

        ltsibling =j- 1;

        rtsibling = j+ 1;

        if (x < csr->key[j]) {

          csr = csr->ptr[j];

          break;

        }

        if (j == csr->size - 1) {

          ltsibling =j;

          rtsibling = j + 2;

          csr = csr->ptr[j + 1];

          break;

        }

      }

    }

    bool found = false;

    int pos;

    for (pos = 0; pos < csr->size; pos++) {

      if (csr->key[pos] == x) {

        found = true;

        break;

      }

    }

    if (!found) {

      cout << "Not found\n";

      return;

    }

    for (int j= pos; j< csr->size; j++) {

      csr->key[j] = csr->key[j + 1];

    }

    csr->size--;

    if (csr == root) {

      for (int j = 0;j < MAX + 1; j++) {

        csr->ptr[j] = NULL;

      }

      if (csr->size == 0) {

        cout << "Tree is dead\n";

        delete[] csr->key;// delete csr's key

        delete[] csr->ptr;//delete csr's pointer

        delete csr;// delete csr

        root = NULL; //root is set to NULL

      }

      return;

    }

//shift csr's pointer value back by one

    csr->ptr[csr->size] = csr->ptr[csr->size + 1];

//delete previous csr'pointer location

    csr->ptr[csr->size + 1] = NULL;

    if (csr->size >= (MAX + 1) / 2) {

      return;

    }

    if (ltsibling >= 0) {

      Node *leftnode = parent->ptr[ltsibling];

      if (leftnode->size >= (MAX + 1) / 2 + 1) {

        for (int j= csr->size; j > 0;j--) {

          csr->key[j] = csr->key[j - 1];

        }

        csr->size++;

        csr->ptr[csr->size] = csr->ptr[csr->size - 1];

        csr->ptr[csr->size - 1] = NULL;

        csr->key[0] = leftnode->key[leftnode->size - 1];

        leftnode->size--;

        leftnode->ptr[leftnode->size] = csr;

        leftnode->ptr[leftnode->size + 1] = NULL;

        parent->key[ltsibling] = csr->key[0];

        return;

      }

    }

    if (rtsibling <= parent->size) {

      Node *rightnode = parent->ptr[rtsibling];

      if (rightnode->size >= (MAX + 1) / 2 + 1) {

        csr->size++;

        csr->ptr[csr->size] = csr->ptr[csr->size - 1];

        csr->ptr[csr->size - 1] = NULL;

        csr->key[csr->size - 1] = rightnode->key[0];

       rightnode->size--;// decrease size of right node

        rightnode->ptr[rightnode->size] = rightnode->ptr[rightnode->size + 1];

//shift rightnode pointer back by one

        rightnode->ptr[rightnode->size + 1] = NULL;

        for (int j = 0;j < rightnode->size;j++) {

          rightnode->key[j] = rightnode->key[j+ 1];

        }

        parent->key[rtsibling - 1] = rightnode->key[0];

        return;

      }

    }

    if (ltsibling >= 0) {

      Node *leftnode = parent->ptr[ltsibling];

      for (int k= leftnode->size, j = 0; j < csr->size; k++, j++) {

        leftnode->key[k] = csr->key[j];

      }

//delete left node pointer located at index as its size

      leftnode->ptr[leftnode->size] = NULL;

      leftnode->size += csr->size;// increase leftnode pointer size by csr's

      leftnode->ptr[leftnode->size] = csr->ptr[csr->size];

      csr(parent->key[ltsibling], parent, csr);

      delete[] csr->key;

      delete[] csr->ptr;

      delete csr;

    } else if (rtsibling <= parent->size) {

      Node *rightnode = parent->ptr[rtsibling];

      for (int k = csr->size, j = 0; j < rightnode->size; k++, j++) {

        csr->key[k] = rightnode->key[j];

      }

//delete csr ptr

      csr->ptr[csr->size] = NULL;

      csr->size += rightnode->size; // increase size of csr by rightnode's

      csr->ptr[csr->size] = rightnode->ptr[rightnode->size];

// store right node pointer's size in csr

      cout << "Merging two leaf nodes\n";

      csr(parent->key[rtsibling - 1], parent, rightnode);

      delete[] rightnode->key;//delete righnode's key

      delete[] rightnode->ptr;//delete rightnode's pointer

      delete rightnode;// delete right node

    }

  }

}

void bptree::csr(int x, Node *csr, Node *child) {

  if (csr == root) {

    if (csr->size == 1) {

// check if csr's pointer points at a child

      if (csr->ptr[1] == child) {

        delete[] child->key;//delete child's key

        delete[] child->ptr;// delete child's pointer

        delete child; //delete child itself

        root = csr->ptr[0]; //store root at csr pointer index 1

        delete[] csr->key;//delete csr key

        delete[] csr->ptr;//delete csr pointer

        delete csr;//delete csr

        cout << "Change root node";      

      } else if (csr->ptr[0] == child) {

        delete[] child->key;// delete child's key

        delete[] child->ptr;//delete child's pointer

        delete child;//delete child itself

        root = csr->ptr[1];

        delete[] csr->key;

        delete[] csr->ptr;

        delete csr;

        cout << "Changed root node\n";

        return;

      }

    }

  }

  int pos;

  for (pos = 0; pos < csr->size; pos++) {

    if (csr->key[pos] == x) {

      break;

    }

  }

  for (int i = pos; i < csr->size; i++) {

    csr->key[i] = csr->key[i + 1];

  }

  for (pos = 0; pos < csr->size + 1; pos++) {

    if (csr->ptr[pos] == child) {

      break;

    }

  }

  for (int i = pos; i < csr->size + 1; i++) {

    csr->ptr[i] = csr->ptr[i + 1];

  }

  csr->size--;

  if (csr->size >= (MAX + 1) / 2 - 1) {

    return;

  }

  if (csr == root)

    return;

  Node *parent = findparent(root, csr);

  int ltsibling, rtsibling;

  for (pos = 0; pos < parent->size + 1; pos++) {

    if (parent->ptr[pos] == csr) {

      ltsibling = pos - 1;

      rtsibling = pos + 1;

      break;

    }

  }

  if (ltsibling >= 0) {

    Node *leftnode = parent->ptr[ltsibling];

    if (leftnode->size >= (MAX + 1) / 2) {

      for (int i = csr->size; i > 0; i--) {

        csr->key[i] = csr->key[i - 1];

      }

      csr->key[0] = parent->key[ltsibling];

      parent->key[ltsibling] = leftnode->key[leftnode->size - 1];

      for (int i = csr->size + 1; i > 0; i--) {

        csr->ptr[i] = csr->ptr[i - 1];

      }

      csr->ptr[0] = leftnode->ptr[leftnode->size];

      csr->size++;

      leftnode->size--;

      return;

    }

  }

  if (rtsibling <= parent->size) {

    Node *rightnode = parent->ptr[rtsibling];

    if (rightnode->size >= (MAX + 1) / 2) {

      csr->key[csr->size] = parent->key[pos];

      parent->key[pos] = rightnode->key[0];

      for (int j = 0; j < rightnode->size - 1; j++) {

        rightnode->key[j] = rightnode->key[j + 1];

      }

      csr->ptr[csr->size + 1] = rightnode->ptr[0];

      for (int j = 0; j < rightnode->size; ++j) {

        rightnode->ptr[j] = rightnode->ptr[j + 1];

      }

      csr->size++;

      rightnode->size--;

      return;

    }

  }

  if (ltsibling >= 0) {

    Node *leftnode = parent->ptr[ltsibling];

    leftnode->key[leftnode->size] = parent->key[ltsibling];

    for (int k = leftnode->size + 1, j = 0; j < csr->size; j++) {

      leftnode->key[k] = csr->key[j];

    }

    for (int k = leftnode->size + 1, j = 0; j < csr->size + 1; j++) {

      leftnode->ptr[k] = csr->ptr[j];

      csr->ptr[j] = NULL;

    }

    leftnode->size += csr->size + 1;

    csr->size = 0;

    csr(parent->key[ltsibling], parent, csr);

  } else if (rtsibling <= parent->size) {

    Node *rightnode = parent->ptr[rtsibling];

    csr->key[csr->size] = parent->key[rtsibling - 1];

    for (int k = csr->size + 1, j = 0; j < rightnode->size; j++) {

      csr->key[k] = rightnode->key[j];

    }

    for (int k = csr->size + 1, j = 0; j < rightnode->size + 1; j++) {

      csr->ptr[k] = rightnode->ptr[j];

      rightnode->ptr[j] = NULL;

    }

    csr->size += rightnode->size + 1;

    rightnode->size = 0;

    csr(parent->key[rtsibling - 1], parent, rightnode);

  }

}