bpdelete.cpp

来自「经典c++程序的实现」· C++ 代码 · 共 50 行

// function binaryle(A, n, K) returns the greatest value less than
//   or equal to K in array A of length n.
// function removerec(A, n, c) removes record at position c from
//   array A with n records.
// function merge_nodes(N1, N2) merges together the record arrays of
//   BPNodes N1 and N2.
// function suffle_nodes(N1, N2) copies execess records from BPNode
//   N2 to BPNode N1, so that both have an equal number of records. 
Bool BP::removehelp(BPNode* root, KEY K, KEY& retval) {
  int currec;  Bool delchild;
  KEY myretv = NOKEY;

  if (root->isLeaf()) {
    currec = binaryle(root->recarray, root->numrec, K);
    if (root->recarray[currec].key != K) ERROR;  // record not found
  }
  else { // Delete from child
    currec = binaryle(root->recarray, root->numrec, K);
    delchild = removehelp(root->recarray[currec].pointer,K,myretv);
    if (myretv != NOKEY)
      root->recarray[currec].key = myretv;
    if (!delchild) return FALSE; // Child did not collapse
  }

  // Now, remove record at position currec
  if (root->numrec > THRESHOLD) {// Just remove it
    removerec(root->recarray, rec->numrec, currec);
    return FALSE;
  }
  else {// Underflow
    if (root->leftptr == NULL) // No left neighbor
      if (root->numrec + root->rightptr->numrec <= MAXREC) {
        merge_nodes(root, root->rightptr);
        return TRUE;
      }
      else {
        shuffle_nodes(root, root->rightptr);
        retval = root->recarray[0].key;  // Key value has changed
        return FALSE;
      }
    else if (root->numrec + root->leftptr->numrec <= MAXREC) {
      merge_nodes(root, root->leftptr);
      return TRUE;
    }
    else {
      shuffle_nodes(root, root->leftptr);
      retval = root->recarray[0].key;
      return FALSE;
}}}