Main Page   Compound List   File List   Compound Members  

binary_tree Class Reference

binary_tree class definition. More...

#include <bitree.h>

List of all members.

Public Types

typedef bi_tree* bi_tree_ptr

Public Methods

void print_tree (void)
void print_sorted (void)
unsigned int max_branch_size (void)
unsigned int count_tree (void)
 binary_tree (void)
void tree_insert (unsigned int key, unsigned int val)
unsigned int tree_delete (unsigned int key)
virtual bi_tree_ptr get_tree_mem (void)
 The class derived from the binary tree object should supply memory allocation and deallocation functions. More...

virtual void free_tree_mem (bi_tree_ptr node)

Protected Types

typedef struct binary_tree::bi_tree_struct  bi_tree

Private Methods

void bi_tree_print (bi_tree_ptr root, unsigned int indent)
 bi_tree_print. More...

void print_spaces (unsigned int indent)
 Code for displaying the contents of the tree (mainly for debugging and verification). More...

void bi_tree_print_sorted (bi_tree_ptr root)
 bi_tree_print_sorted. More...

unsigned int bi_tree_max_branch (bi_tree_ptr root)
 bi_tree_max_branch. More...

unsigned int bi_tree_cnt (bi_tree_ptr root)
 This function returns the number of elements in the subtree "root". More...

bi_tree_ptr unlink (bi_tree_ptr &root)
 unlink. More...

bi_tree_ptr bi_tree_init (unsigned int key, unsigned int val)
 bi_tree_init. More...

void bi_tree_insert (bi_tree_ptr &root, unsigned int key, unsigned int val)
 bi_tree_insert. More...

unsigned int bi_tree_delete (bi_tree_ptr &root, unsigned int key)
 bi_tree_delete. More...


Private Attributes

bi_tree_ptr root

Detailed Description

binary_tree class definition.

This class supports insertion and deletion of elements in a simple binary tree (e.g., the tree is not self balancing). The class provides two public functions:

The class derived from this class must supply instances of two virtual functions:

Several public functions are also provided for debugging (see bitree.cpp)

Definition at line 65 of file bitree.h.

Member Typedef Documentation

typedef struct binary_tree::bi_tree_struct binary_tree::bi_tree [protected]
 

typedef bi_tree * binary_tree::bi_tree_ptr
 

Definition at line 75 of file bitree.h.

Constructor & Destructor Documentation

binary_tree::binary_tree ( void ) [inline]
 

Definition at line 104 of file bitree.h.

00104 { root = NULL; }

Member Function Documentation

unsigned int binary_tree::bi_tree_cnt ( bi_tree_ptr root ) [private]
 

This function returns the number of elements in the subtree "root".

The number of elements in the (sub)tree whose root is "root" is the count of the left branch, plus the count of the right branch, plus one (for the current node). This function can be useful in testing to make sure that no elements are "lost".

Definition at line 322 of file bitree.cpp.

Referenced by count_tree(). 

00323 {
00324   unsigned int cnt = 0;
00325 
00326   if (root != NULL) {
00327     cnt = bi_tree_cnt(root->leftptr) + bi_tree_cnt(root->rightptr) + 1;
00328   }
00329 
00330   return cnt;
00331 } // binary_tree::bi_tree_cnt

unsigned int binary_tree::bi_tree_delete ( bi_tree_ptr & root,
unsigned int key ) [private]
 

bi_tree_delete.

This function searches a binary tree for "key" and deletes the item from the tree. The ordering of the tree is maintained (see below). If "key" is found, this function deallocates the node and returns the "val" field. If "key" is not found, the function returns zero.

When the node is found in the tree there are three possible cases:

  1. The node is a leaf node (no children). In this case the node can simply be unlinked from the tree and returned.
  2. The node has one child. In this case, the node is replaced by its child node.
  3. The node has two children. In this case the node is replaced by the least value from the right branch. This value is found by taking the right branch, and then walking down the left branch (see the unlink function, above). The value found this way should be the next greatest value in the tree.

Definition at line 152 of file bitree.cpp.

Referenced by tree_delete(). 

00154 {
00155   unsigned int retval = 0;
00156 
00157   if (root != NULL) {
00158     if (root->key > key)
00159       retval = bi_tree_delete(root->leftptr, key);
00160     else
00161       if (root->key < key)
00162         retval = bi_tree_delete(root->rightptr, key);
00163       else { // the keys are equal
00164         bi_tree_ptr node = NULL;
00165         bi_tree_ptr new_child = NULL;
00166         int num_children = 0;
00167           
00168         node = root;
00169         retval = root->val;
00170 
00171         // Count the children of the node
00172         if (root->leftptr != NULL) {
00173           num_children++;
00174           new_child = root->leftptr;
00175         }
00176         if (root->rightptr != NULL) {
00177           num_children++;
00178           new_child = root->rightptr;
00179         }
00180 
00181         switch (num_children) {
00182         case 0: root = NULL;
00183           break;
00184         case 1: root = new_child;  // Replace the node with its child
00185           break;
00186         case 2: {
00187           bi_tree_ptr tmp1, tmp2;
00188             
00189           // find the next greater node in the tree and unlink it
00190           tmp1 = root->rightptr;
00191           tmp2 = unlink(tmp1);
00192           // Connect the new node to any children, but make sure that 
00193           // we don't point a node at itself.
00194           if (root->leftptr != tmp2)
00195             tmp2->leftptr = root->leftptr;
00196           if (root->rightptr != tmp2)
00197             tmp2->rightptr = root->rightptr;
00198           root = tmp2;
00199         }
00200           break;
00201         } // switch
00202         free_tree_mem( node );
00203       } // keys are equal
00204   }  // root != NULL
00205   return retval;
00206 } // bi_tree_delete

bi_tree_ptr binary_tree::bi_tree_init ( unsigned int key,
unsigned int val ) [private]
 

bi_tree_init.

Allocate and initialize a binary tree element.

Definition at line 45 of file bitree.cpp.

Referenced by bi_tree_insert(). 

00047 {
00048   bi_tree_ptr tmp = (bi_tree_ptr)get_tree_mem();
00049 
00050   tmp->key = key;
00051   tmp->val = val;
00052   tmp->leftptr = NULL;
00053   tmp->rightptr = NULL;
00054   return tmp;
00055 }

void binary_tree::bi_tree_insert ( bi_tree_ptr & root,
unsigned int key,
unsigned int val ) [private]
 

bi_tree_insert.

Insert a new value into the ordered binary tree. Note that if the element is found in the tree, it is treated as an error.

Definition at line 64 of file bitree.cpp.

Referenced by tree_insert(). 

00067 {
00068   if (root == NULL) { // the tree is empty
00069     root = bi_tree_init(key, val);
00070   }
00071   else {
00072     if (root->key > key)
00073       bi_tree_insert(root->leftptr, key, val);     // search down left branch
00074     else
00075       if (root->key < key)
00076         bi_tree_insert(root->rightptr, key, val);  // search down right branch
00077       else { // key == root->key
00078         printf("binary_tree::bi_tree_insert: key %d already found in tree\n",
00079                key );
00080       }
00081   }
00082 } // bi_tree_insert

unsigned int binary_tree::bi_tree_max_branch ( bi_tree_ptr root ) [private]
 

bi_tree_max_branch.

This binary tree is not an AVL tree (e.g., a self balancing binary tree). As a result, the shape of the tree and the efficiency of tree search is heavily dependant on the distribution of the input values. The more evenly (randomly) these values are distributed, the closer the tree shape will be to a balanced tree and the close the search time will be to log2(N). This function will return the size of the longest branch in the tree. This is useful for estimating the worst case performance for a given data set.

Definition at line 288 of file bitree.cpp.

Referenced by max_branch_size(). 

00289 {
00290   unsigned int depth = 0;
00291 
00292   if (root != NULL) {
00293     unsigned int depth_left = 0;
00294     unsigned int depth_right = 0;
00295 
00296     if (root->leftptr != NULL)
00297       depth_left = bi_tree_max_branch(root->leftptr);
00298     if (root->rightptr != NULL)
00299       depth_right = bi_tree_max_branch(root->rightptr);
00300 
00301     // depth = max(depth_left, depth_right)
00302     if (depth_left > depth_right)
00303       depth = depth_left;
00304     else
00305       depth = depth_right;
00306 
00307     depth++;  // Add one for the current node
00308   }
00309 
00310   return depth;
00311 } // binary_tree::bi_tree_max_branch

void binary_tree::bi_tree_print ( bi_tree_ptr root,
unsigned int indent ) [private]
 

bi_tree_print.

Print the binary tree in "landscape" form (e.g., down the length of an infinite page).

Definition at line 238 of file bitree.cpp.

Referenced by print_tree(). 

00239 {
00240 
00241   if (root != NULL) {
00242     print_spaces(indent);
00243     printf("%d\n", root->key );
00244     if (root->leftptr != NULL)
00245       bi_tree_print(root->leftptr, indent+4);
00246     else {
00247       print_spaces(indent+4);
00248       printf("null\n");
00249     }
00250     if (root->rightptr != NULL)
00251       bi_tree_print(root->rightptr, indent+4);
00252     else {
00253       print_spaces(indent+4);
00254       printf("null\n");
00255     }
00256   }
00257 }

void binary_tree::bi_tree_print_sorted ( bi_tree_ptr root ) [private]
 

bi_tree_print_sorted.

Print the contents of the binary tree in sorted, increasing, order.

Definition at line 265 of file bitree.cpp.

Referenced by print_sorted(). 

00266 {
00267   if (root != NULL) {
00268     bi_tree_print_sorted(root->leftptr);
00269     printf("%d ", root->key );
00270     bi_tree_print_sorted(root->rightptr);
00271   }
00272 }

unsigned int binary_tree::count_tree ( void ) [inline]
 

Definition at line 91 of file bitree.h.

00091 { return bi_tree_cnt(root); }

void binary_tree::free_tree_mem ( bi_tree_ptr node ) [virtual]
 

Definition at line 349 of file bitree.cpp.

Referenced by bi_tree_delete(). 

00350 {
00351   printf("binary_tree::free_tree_mem: no memory dealloc provided for class\n");
00352 }

bi_tree_ptr binary_tree::get_tree_mem ( void ) [virtual]
 

The class derived from the binary tree object should supply memory allocation and deallocation functions.

Definition at line 341 of file bitree.cpp.

Referenced by bi_tree_init(). 

00342 {
00343   printf("binary_tree::get_tree_mem: no memory alloc provided for class\n");
00344   return (bi_tree_ptr)NULL;
00345 }

unsigned int binary_tree::max_branch_size ( void ) [inline]
 

Definition at line 90 of file bitree.h.

00090 { return bi_tree_max_branch(root); }

void binary_tree::print_sorted ( void ) [inline]
 

Definition at line 89 of file bitree.h.

00089 { bi_tree_print_sorted( root ); }

void binary_tree::print_spaces ( unsigned int indent ) [private]
 

Code for displaying the contents of the tree (mainly for debugging and verification).

Definition at line 216 of file bitree.cpp.

Referenced by bi_tree_print(). 

00217 {
00218   const int BufSize = 80;
00219   char buf[BufSize+1];
00220   int i;
00221   
00222   if (indent > BufSize)
00223     indent = BufSize;
00224   for (i = 0; i < (int)indent; i++) {
00225     buf[i] = ' ';
00226   }
00227   buf[indent] = '\0';
00228   printf("%s", buf);
00229 }

void binary_tree::print_tree ( void ) [inline]
 

Definition at line 88 of file bitree.h.

00088 { bi_tree_print( root, 0 ); }

unsigned int binary_tree::tree_delete ( unsigned int key ) [inline]
 

Definition at line 110 of file bitree.h.

00111     { return bi_tree_delete(root, key ); }

void binary_tree::tree_insert ( unsigned int key,
unsigned int val ) [inline]
 

Definition at line 106 of file bitree.h.

00108     { bi_tree_insert(root, key, val); }

bi_tree_ptr binary_tree::unlink ( bi_tree_ptr & root ) [private]
 

unlink.

When a value is removed from an ordered binary tree and the value has children, it will be replaced by the next value in the right sub-branch which is greater. This value will be the last (terminal) value in the left branch of the right tree.

The unlink function walks down a subtree's left branch until it gets to the end. It removes the value at the end of the branch and returns it (so it can be inserted into the "hole" left the deleted value). If the value at the end of the left branch has a right branch child, replace it with the right branch child.

Definition at line 101 of file bitree.cpp.

Referenced by bi_tree_delete(). 

00102 {
00103   bi_tree_ptr node;
00104 
00105   node = root;
00106   if (root != NULL) {
00107     if (root->leftptr != NULL) {
00108       node = unlink(root->leftptr);
00109     }
00110     else {
00111       if (root->rightptr != NULL) {  // if there is a right branch child
00112         root = root->rightptr;       // replace the node at the end of
00113       }                              // the left branch with this child.
00114       else
00115         root = NULL;  // no children
00116     }
00117   }
00118   return node;
00119 }

Member Data Documentation

bi_tree_ptr binary_tree::root [private]
 

Definition at line 78 of file bitree.h.

The documentation for this class was generated from the following files:
Generated at Tue Jun 10 21:24:10 2003 for Unbalanced Binary Tree Search, Insert and Delete by doxygen1.2.8.1 written by Dimitri van Heesch, © 1997-2001