// file arrTree.h
// ==============
#ifndef ARRTREE_H
#define ARRTREE_H
#include <string>
using namespace std;
// An array-based implementation of a binary search tree
// for key-value pairs
// Internally the tree nodes are stored in an array,
// and a circular buffer is used to track which
// array positions are currently empty
class ArrTree {
public:
// default size for the tree array
static const long DefaultMaxNodes = 31;
// create a tree with the specified maximum number of nodes
// (allocate the array of nodes and the buffer of available spots)
ArrTree(long nodes = DefaultMaxNodes);
// deallocate the tree's storage
// (the array of nodes and the buffer)
~ArrTree();
// return the current size of the tree
// (i.e. the number of key-value pairs currently stored)
long getSize();
// lookup the value associated with a key
bool lookup(string k, string &v);
// insert a new key value pair
bool insert(string k, string v);
// update the value associated with a key
bool update(string k, string v);
// remove a key value pair
bool remove(string k, string &v);
// print all key value pairs, sorted by key
void print();
protected:
// default value used to designate an empty position
static const long EMPTY = -1;
// remove a key value pair from a subtree
void print(long n);
// print all key value pairs in a subtree, sorted by key
bool remove(string k, string &v, long &n);
// the composition of individual tree nodes
struct node {
string key, value; // the actual key/value data pair
long left, right; // the positions of the nodes children
// set to EMPTY when there is no child
};
// The array of tree nodes and the size of the array
node *tree;
long numNodes;
// The index position of the root node,
// set to EMPTY when the tree is empty
long root;
// the hidden circular buffer for available spots in the array,
// indexes of the front and back positions in the buffer,
// and the number of spots available to the tree
// (i.e. the number of things enqueued in the buffer)
// when there is nothing in the buffer
// back is set to EMPTY, front is set to 0
long *Available;
long front, back, numAvail;
// methods to enqueue and dequeue indices
long dequeue();
bool enqueue(long index);
};
#endif
// file arrTree.C
// ==============
#include "arrTree.h"
#include <iostream>
// =======================================================
// An array-based implementation of a binary search tree
// for key-value pairs
// Internally the tree nodes are stored in an array,
// and a circular buffer is used to track which
// array positions are currently empty
// =======================================================
// create a tree with the specified maximum number of nodes
// (allocate the array of nodes and the buffer of available spots)
ArrTree::ArrTree(long nodes)
{
// allocate the array of nodes
if (nodes < 1) nodes = DefaultMaxNodes;
tree = new node[nodes];
if (!tree) numNodes = 0;
else numNodes = nodes;
root = EMPTY;
// allocate the circular buffer of available spots
Available = new long[numNodes];
if (!Available) {
numAvail = 0;
delete [] tree;
numNodes = 0;
front = 0;
back = EMPTY;
} else {
// initialize the queue of available spots
numAvail = numNodes;
for (long a = 0; a < numNodes; a++) Available[a] = a;
front = 0;
back = numNodes - 1;
}
}
// deallocate the tree's storage
// (the array of nodes and the buffer)
ArrTree::~ArrTree()
{
if (Available) delete [] Available;
if (tree) delete [] tree;
}
// dequeue the next available spot from the circular buffer
long ArrTree::dequeue()
{
// make sure the queue isn't empty
if (numAvail == 0) return EMPTY;
// otherwise dequeue from the front
long result = Available[front];
numAvail--;
// reset front and back if the queue is now empty
if (numAvail == 0) {
front = 0;
back = EMPTY;
}
// otherwise wrap front around if necessary
else front = (front + 1) % numNodes;
return result;
}
// enqueue a new available spot into the circular buffer
bool ArrTree::enqueue(long index)
{
// make sure the queue isn't full
if (numAvail == numNodes) return false;
// otherwise insert at the back and wrap around if needed
back = (back + 1) % numNodes;
Available[back] = index;
numAvail++;
return true;
}
// return the current size of the tree
// (i.e. the number of key-value pairs currently stored)
long ArrTree::getSize()
{
// the nodes in use is the difference between the total
// number of nodes and the number still available
return numNodes - numAvail;
}
// lookup the value associated with a key
bool ArrTree::lookup(string k, string &v)
{
// search for the target string
long current = root;
while (current != EMPTY) {
// check for a match
if (tree[current].key == k) {
v = tree[current].value;
return true;
}
// otherwise move into the left or right subtree
if (k < tree[current].key)
current = tree[current].left;
else current = tree[current].right;
}
// target key was not found
return false;
}
// insert a new key value pair, no duplicates allowed
bool ArrTree::insert(string k, string v)
{
// check if the tree is full
if (numAvail == 0) return false;
// handle the root as a special case
if (getSize() == 0) {
root = dequeue();
if (root == EMPTY) return false;
tree[root].left = EMPTY;
tree[root].right = EMPTY;
tree[root].key = k;
tree[root].value = v;
return true;
}
// search for the parent of the new node
long current = root;
while ((current != EMPTY) && (tree[current].key != k)) {
// see if the new node belong's in current's left subtree
if (k < tree[current].key) {
if (tree[current].left == EMPTY) {
// the new node should become current's child,
// get the next available spot from the buffer
// and update the tree nodes
long lchild = dequeue();
if (lchild == EMPTY) return false;
else {
tree[current].left = lchild;
tree[lchild].key = k;
tree[lchild].value = v;
tree[lchild].left = EMPTY;
tree[lchild].right = EMPTY;
return true;
}
}
// otherwise move into the left subtree
current = tree[current].left;
}
// the new node must belong in current's right subtree
else {
if (tree[current].right == EMPTY) {
// the new node should become current's child,
// get the next available spot from the buffer
// and update the tree nodes
long rchild = dequeue();
if (rchild == EMPTY) return false;
else {
tree[current].right = rchild;
tree[rchild].key = k;
tree[rchild].value = v;
tree[rchild].left = EMPTY;
tree[rchild].right = EMPTY;
return true;
}
}
// otherwise move into the right subtree
current = tree[current].right;
}
}
// could not insert
return false;
}
// update the value associated with a key
bool ArrTree::update(string k, string v)
{
// search for the target string
long current = root;
while (current != EMPTY) {
// check for a match
if (tree[current].key == k) {
tree[current].value = v;
return true;
}
// otherwise move into the left or right subtree
if (k < tree[current].key)
current = tree[current].left;
else current = tree[current].right;
}
// target key was not found
return false;
}
// print all key value pairs in the tree, sorted by key
void ArrTree::print()
{
// print overall tree stats
cout << "The tree currently contains " << getSize() << " entries\n";
cout << " with " << numAvail << " spots still available ";
cout << "(total " << numNodes << ")\n";
cout << "The current key/value pairs are:\n";
// now print the data values
print(root);
}
// print all key value pairs in a subtree, sorted by key
void ArrTree::print(long n)
{
// check if the tree is empty
if (n == EMPTY) return;
// print the left subtree, the current node, and the right subtree
print(tree[n].left);
cout << tree[n].key << ":" << tree[n].value << endl;
print(tree[n].right);
}
// remove a key value pair
bool ArrTree::remove(string k, string &v)
{
return remove(k, v, root);
}
// remove a key value pair from a subtree
bool ArrTree::remove(string k, string &v, long &n)
{
// check if the tree is empty
if (n == EMPTY) return false;
// keep searching til we find a match
if (k < tree[n].key) return remove(k, v, tree[n].left);
if (k > tree[n].key) return remove(k, v, tree[n].right);
// n is the target to remove, copy out its data
v = tree[n].value;
// handle the case where n has no children
if ((tree[n].left == EMPTY) && (tree[n].right == EMPTY)) {
// mark n as free space and (since n is the parent's
// index to the child) set it to EMPTY
if (!enqueue(n)) return false;
n = EMPTY;
return true;
}
// handle the case where n has one child
if ((tree[n].left == EMPTY) || (tree[n].right == EMPTY)) {
// mark n as free space and (since n is the parent's
// index to its child) redirect it to n's child
// (bypassing n)
if (!enqueue(n)) return false;
if (tree[n].left == EMPTY) n = tree[n].right;
else n = tree[n].left;
return true;
}
// handle the case where n has two children
// (1) find the smallest key in n's right subtree
long smallest = tree[n].right;
while (tree[smallest].left != EMPTY) smallest = tree[smallest].left;
// (2) copy the key/value from smallest to n
tree[n].key = tree[smallest].key;
tree[n].value = tree[smallest].value;
// (3) remove smallest from n's right subtree
string temp;
return remove(tree[smallest].key, temp, tree[n].right);
}
// file treeEx.C
// ==============
#include "arrTree.h"
#include <iostream>
// ============================================================
// Application prototypes and definitions
//
enum Command {
NoCmd = '-', Insert = 'I', Print = 'P',
Lookup = 'L', Update = 'U', Help = 'H',
Remove = 'R', Quit = 'Q'
};
Command GetCmd();
void PrintHelp();
void ProcessCmd(Command c, ArrTree &T);
// ============================================================
// Application main routine
//
int main()
{
// set up a tree of maximum size 15
ArrTree T(15);
Command cmd;
do {
cmd = GetCmd();
ProcessCmd(cmd, T);
} while (cmd != Quit);
}
// ============================================================
// Application function implementations
//
Command GetCmd()
{
char c;
cout << "Enter your command choice (" << (char)(Help) << " is help)" << endl;
cin >> c;
c = toupper(c);
switch (c) {
case Insert: return Insert;
case Print: return Print;
case Lookup: return Lookup;
case Remove: return Remove;
case Update: return Update;
case Help: return Help;
case Quit: return Quit;
default:
cout << "Invalid command selected: " << c << endl;
PrintHelp();
return NoCmd;
}
}
void PrintHelp()
{
cout << "Valid commands are: " << endl;
cout << " " << (char)(Insert) << ": insert" << endl;
cout << " " << (char)(Print) << ": print" << endl;
cout << " " << (char)(Lookup) << ": lookup" << endl;
cout << " " << (char)(Remove) << ": remove" << endl;
cout << " " << (char)(Update) << ": update" << endl;
cout << " " << (char)(Help) << ": help" << endl;
cout << " " << (char)(Quit) << ": quit" << endl;
}
void ProcessCmd(Command c, ArrTree &T)
{
string key, value;
switch (c) {
case Insert:
cout << "Enter the key and value to insert" << endl;
cin >> key >> value;
if (T.insert(key, value)) cout << "Insert successful" << endl;
else cout << "Insert unsuccessful" << endl;
break;
case Update:
cout << "Enter the key and value to update" << endl;
cin >> key >> value;
if (T.update(key, value)) cout << "Update successful" << endl;
else cout << "Update unsuccessful" << endl;
break;
case Remove:
cout << "Enter the key to remove" << endl;
cin >> key;
if (T.remove(key, value))
cout << "Removed " << key << ":" << value << endl;
else cout << "Remove unsuccessful" << endl;
break;
case Lookup:
cout << "Enter the key to lookup" << endl;
cin >> key;
if (T.lookup(key, value))
cout << "Found " << key << ":" << value << endl;
else cout << "Lookup unsuccessful" << endl;
break;
case Print: cout << "Current keys and values are:" << endl;
T.print();
break;
case Help: PrintHelp();
break;
default:
break;
}
}
|