Array-based binary tree implementations

In our previous examination of binary search trees our implementations have focused on collections of tree nodes linked by pointers.

One alternative is to have a pre-defined array to hold all the potential tree nodes, and instead of holding pointers to the right and left children each node tracks which array positions its right and left children are in.

To do this, we need to keep track of which positions in the array are already filled with tree nodes, and which ones are available (empty).

When inserting we would grab the next empty node (after making sure the tree wasn't full) and when removing nodes we would put them back in the 'available' collection.

For instance, if we inserted numeric keys 13, 77, 200, 4, and 40 in that order then our tree would logically look like this:

     13
    /  \
   4    77
       /  \
     40    200
The five values would appear in positions 0 through 4 of the array (13 in position 0, 77 in position 1, etc. The value of root would be 0 (the position where we placed 13).

For the individual nodes, their left and right fields would record the array positions of their children (using -1 when there is no left or right child).

     Key's     Left      Right
     Array     Child's   Child's
Key  Position  Position  Position
13     0         3          1
77     1         4          2
200    2        -1         -1
4      3        -1         -1
40     4        -1         -1

The logical data structure for keeping track of which spots are free would be a queue: dequeueing the front available empty spot when inserting and enqueueing an emptied spot after deleting something from the tree. In fact, since the maximum number of spots available is fixed (the number of positions in the tree's array of nodes) it would be logical to use a circular buffer as our queue implementation.

The tree class below follows exactly this style to implement a binary search tree of key/value pairs. It is provided in three parts:

  1. arrTree.h (the header file)
  2. arrTree.C (the class methods)
  3. treeEx.C (a sample application)
They can be compiled together using
g++ -Wall arrTree.C treeEx.C -o treeEx

// 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; } }