// From the software distribution accompanying the textbook // "A Practical Introduction to Data Structures and Algorithm Analysis, // Third Edition (C++)" by Clifford A. Shaffer. // Source code Copyright (C) 2007-2011 by Clifford A. Shaffer. // This file gathers together all of the pieces of the 2-3 Tree implementation #include "dictionary.h" // Empty key value int EMPTYKEY = -1; #include "ttnode.h" #include "tttree.h" #include "ttprint.h" template TTNode* TTTree:: inserthelp(TTNode* rt, const Key k, const E e) { TTNode* retval; if (rt == NULL) // Empty tree: create a leaf node for root return new TTNode(k, e, EMPTYKEY, NULL, NULL, NULL, NULL); if (rt->isLeaf()) // At leaf node: insert here return rt->add(new TTNode(k, e, EMPTYKEY, NULL, NULL, NULL, NULL)); // Add to internal node if (k < rt->lkey) { retval = inserthelp(rt->left, k, e); if (retval == rt->left) return rt; else return rt->add(retval); } else if((rt->rkey == EMPTYKEY) || (k < rt->rkey)) { retval = inserthelp(rt->center, k, e); if (retval == rt->center) return rt; else return rt->add(retval); } else { // Insert right retval = inserthelp(rt->right, k, e); if (retval == rt->right) return rt; else return rt->add(retval); } } // Add a new key/value pair to the node. There might be a // subtree associated with the record being added. This // information comes in the form of a 2-3 tree node with // one key and a (possibly NULL) subtree through the // center pointer field. template TTNode* TTNode::add(TTNode* it) { if (rkey == EMPTYKEY) { // Only one key, add here if (lkey < it->lkey) { rkey = it->lkey; rval = it->lval; right = center; center = it->center; } else { rkey = lkey; rval = lval; right = center; lkey = it->lkey; lval = it->lval; center = it->center; } return this; } else if (lkey >= it->lkey) { // Add left center = new TTNode(rkey, rval, EMPTYKEY, NULL, center, right, NULL); rkey = EMPTYKEY; rval = NULL; right = NULL; it->left = left; left = it; return this; } else if (rkey < it->lkey) { // Add center it->center = new TTNode(rkey, rval, EMPTYKEY, NULL, it->center, right, NULL); it->left = this; rkey = EMPTYKEY; rval = NULL; right = NULL; return it; } else { // Add right TTNode* N1 = new TTNode(rkey, rval, EMPTYKEY, NULL, this, it, NULL); it->left = right; right = NULL; rkey = EMPTYKEY; rval = NULL; return N1; } } // Find the record that matches a given key value template E TTTree:: findhelp(TTNode* root, Key k) const { if (root == NULL) return NULL; // value not found if (k == root->lkey) return root->lval; if (k == root->rkey) return root->rval; if (k < root->lkey) // Go left return findhelp(root->left, k); else if (root->rkey == EMPTYKEY) // 2 child node return findhelp(root->center, k); // Go center else if (k < root->rkey) return findhelp(root->center, k); // Go center else return findhelp(root->right, k); // Go right }