tttree.c

经典c++程序的实现

// 2-3 Tree Class functions
#include <iostream.h>

#include "book.h"

typedef int TELEM;

#include "ttnode.h"

#include "tttree.h"

void TT::inserthelp(TTNode*& root, const TELEM& val, TELEM& retval,
                    TTNode*& retptr) { // 2-3 tree insert routine
  TELEM myretv;  TTNode* myretp = NULL;
  if (root == NULL)  // Empty tree.
    { root = new TTNode(); root->lkey = val; root->NumKeys = 1; }
  else if (root->isLeaf())  // At leaf node -- insert here
    if (root->NumKeys == 1) { // Easy case
      root->NumKeys = 2;
      if (val >= root->lkey) root->rkey = val;
      else {root->rkey = root->lkey;  root->lkey = val; }}
    else { // Hard case -- split
      retptr = new TTNode();
      if (val > root->rkey)
        { retptr->lkey = val; retval = root->rkey; }
      else {
	retptr->lkey = root->rkey;
	if (val < root->lkey)
          { retval = root->lkey; root->lkey = val; }
	else retval = val;  // Return middle value
      }
      root->NumKeys = retptr->NumKeys = 1; }
  else if (val<root->lkey)
    inserthelp(root->left, val, myretv, myretp);
  else if ((root->NumKeys == 1) || (val < root->rkey))
    inserthelp(root->center, val, myretv, myretp);
  else inserthelp(root->right, val, myretv, myretp);
  if (myretp != NULL) // Child split: receive promoted value
    if (root->NumKeys == 2) { // SPLIT node, promote middle value
      retptr = new TTNode();  root->NumKeys = retptr->NumKeys = 1;
      if (myretv < root->lkey) { // Left child split: promote
        retval = root->lkey;  root->lkey = myretv;
	retptr->lkey = root->rkey; retptr->left = root->center;
        retptr->center = root->right; root->center = myretp;
      }
      else if (myretv < root->rkey) { // Center child split: promote
        retval = myretv;  retptr->lkey = root->rkey;
	retptr->left = myretp;  retptr->center = root->right;
      }
      else { // Right child split: promote
        retval = root->rkey;  retptr->lkey = myretv;
        retptr->left = root->right;  retptr->center = myretp;
    }}
    else { // Only one key in node -- add the second
      root->NumKeys = 2;
      if (myretv < root->lkey) { // Left child has split
        root->rkey = root->lkey; root->lkey = myretv;
        root->right = root->center;  root->center = myretp;
      }
      else { root->rkey = myretv; root->right = myretp; }}}

TTNode* TT::findhelp(TTNode* root, const TELEM& val) const {
  // Return a pointer to the node containing the search key
  if (root == NULL) return NULL;      // val not found
  if (val == root->lkey) return root; // val found
  if ((root->NumKeys == 2) && (val == root->rkey)) return root;
  if (val < root->lkey)               // Search left subtree
    return findhelp(root->left, val);
  else if (root->NumKeys == 1)        // Search center subtree
    return findhelp(root->center, val);
  else if (val < root->rkey)          // Search center subtree
    return findhelp(root->center, val);
  else return findhelp(root->right, val); // Search right subtree
}

void TT::printhelp(TTNode* rt, int level) const {
  if (rt == NULL) return;
  for (int i=0; i<level; i++) cout << "   "; // indent
  cout << rt->lkey;
  if (rt->NumKeys == 2)
    cout << "  " << rt->rkey << "\n";
  else cout << "\n";
  printhelp(rt->left, level+1);
  printhelp(rt->center, level+1);
  if (rt->NumKeys == 2) printhelp(rt->right, level+1);
}