tree/bitree.h0100600000076400010010000000557207671527270013751 0ustar AdministratorNone #ifndef BITREE_H #define BITREE_H #include #include "ianstd.h" /** \file This software was written by Ian L. Kaplan, Chief Fat Bear, Bear Products International. Use of this software, for any purpose, is granted on two conditions:
  1. This copyright notice must be included with the software or any software derived from it.
  2. The risk of using this software is accepted by the user. No warranty as to its usefulness or functionality is provided or implied. The author and Bear Products International provides no support.
*/ /** 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) */ class binary_tree { protected: typedef struct bi_tree_struct { unsigned int key; unsigned int val; bi_tree_struct *leftptr, *rightptr; } bi_tree; public: typedef bi_tree *bi_tree_ptr; private: bi_tree_ptr root; private: // debug functions void bi_tree_print(bi_tree_ptr root, unsigned int indent); void print_spaces(unsigned int indent); void bi_tree_print_sorted(bi_tree_ptr root); unsigned int bi_tree_max_branch( bi_tree_ptr root ); unsigned int bi_tree_cnt( bi_tree_ptr root ); public: // debug functions void print_tree(void) { bi_tree_print( root, 0 ); } void print_sorted(void) { bi_tree_print_sorted( root ); } unsigned int max_branch_size(void) { return bi_tree_max_branch(root); } unsigned int count_tree(void) { return bi_tree_cnt(root); } private: bi_tree_ptr unlink(bi_tree_ptr &root); bi_tree_ptr bi_tree_init(unsigned int key, unsigned int val); void bi_tree_insert(bi_tree_ptr &root, unsigned int key, unsigned int val); unsigned int bi_tree_delete(bi_tree_ptr &root, unsigned int key ); public: binary_tree(void) { root = NULL; } void tree_insert( unsigned int key, unsigned int val ) { bi_tree_insert(root, key, val); } unsigned int tree_delete( unsigned int key ) { return bi_tree_delete(root, key ); } virtual bi_tree_ptr get_tree_mem(void); virtual void free_tree_mem( bi_tree_ptr node ); }; // class binary_tree #endif tree/bitree.cpp0100600000076400010010000002247307671527152014302 0ustar AdministratorNone #include #include "ianstd.h" #include "bitree.h" /** \file This software was written by Ian L. Kaplan, Chief Fat Bear, Bear Products International. Use of this software, for any purpose, is granted on two conditions:
  1. This copyright notice must be included with the software or any software derived from it.
  2. The risk of using this software is accepted by the user. No warranty as to its usefulness or functionality is provided or implied. The author and Bear Products International provides no support.
*/ /** binary_tree class functions This file contains class functions a the binary_tree object, which supports ordered binary tree search, insert and delete. The tree is ordered so that the left branch of a tree node contains values that are less than the current tree node, the right branch contains values that are greater. The tree does not support multiple instances of the same key. */ /** bi_tree_init Allocate and initialize a binary tree element. */ binary_tree::bi_tree_ptr binary_tree::bi_tree_init(unsigned int key, unsigned int val) { bi_tree_ptr tmp = (bi_tree_ptr)get_tree_mem(); tmp->key = key; tmp->val = val; tmp->leftptr = NULL; tmp->rightptr = NULL; return tmp; } /** 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. */ void binary_tree::bi_tree_insert(bi_tree_ptr &root, unsigned int key, unsigned int val ) { if (root == NULL) { // the tree is empty root = bi_tree_init(key, val); } else { if (root->key > key) bi_tree_insert(root->leftptr, key, val); // search down left branch else if (root->key < key) bi_tree_insert(root->rightptr, key, val); // search down right branch else { // key == root->key printf("binary_tree::bi_tree_insert: key %d already found in tree\n", key ); } } } // bi_tree_insert /** 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. */ binary_tree::bi_tree_ptr binary_tree::unlink(bi_tree_ptr &root) { bi_tree_ptr node; node = root; if (root != NULL) { if (root->leftptr != NULL) { node = unlink(root->leftptr); } else { if (root->rightptr != NULL) { // if there is a right branch child root = root->rightptr; // replace the node at the end of } // the left branch with this child. else root = NULL; // no children } } return node; } /** 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.
*/ unsigned int binary_tree::bi_tree_delete(bi_tree_ptr &root, unsigned int key ) { unsigned int retval = 0; if (root != NULL) { if (root->key > key) retval = bi_tree_delete(root->leftptr, key); else if (root->key < key) retval = bi_tree_delete(root->rightptr, key); else { // the keys are equal bi_tree_ptr node = NULL; bi_tree_ptr new_child = NULL; int num_children = 0; node = root; retval = root->val; // Count the children of the node if (root->leftptr != NULL) { num_children++; new_child = root->leftptr; } if (root->rightptr != NULL) { num_children++; new_child = root->rightptr; } switch (num_children) { case 0: root = NULL; break; case 1: root = new_child; // Replace the node with its child break; case 2: { bi_tree_ptr tmp1, tmp2; // find the next greater node in the tree and unlink it tmp1 = root->rightptr; tmp2 = unlink(tmp1); // Connect the new node to any children, but make sure that // we don't point a node at itself. if (root->leftptr != tmp2) tmp2->leftptr = root->leftptr; if (root->rightptr != tmp2) tmp2->rightptr = root->rightptr; root = tmp2; } break; } // switch free_tree_mem( node ); } // keys are equal } // root != NULL return retval; } // bi_tree_delete /* ------------------- Class functions for debugging --------------- */ /** Code for displaying the contents of the tree (mainly for debugging and verification). */ void binary_tree::print_spaces(unsigned int indent) { const int BufSize = 80; char buf[BufSize+1]; int i; if (indent > BufSize) indent = BufSize; for (i = 0; i < (int)indent; i++) { buf[i] = ' '; } buf[indent] = '\0'; printf("%s", buf); } /** bi_tree_print Print the binary tree in "landscape" form (e.g., down the length of an infinite page). */ void binary_tree::bi_tree_print(bi_tree_ptr root, unsigned int indent) { if (root != NULL) { print_spaces(indent); printf("%d\n", root->key ); if (root->leftptr != NULL) bi_tree_print(root->leftptr, indent+4); else { print_spaces(indent+4); printf("null\n"); } if (root->rightptr != NULL) bi_tree_print(root->rightptr, indent+4); else { print_spaces(indent+4); printf("null\n"); } } } /** bi_tree_print_sorted Print the contents of the binary tree in sorted, increasing, order. */ void binary_tree::bi_tree_print_sorted(bi_tree_ptr root) { if (root != NULL) { bi_tree_print_sorted(root->leftptr); printf("%d ", root->key ); bi_tree_print_sorted(root->rightptr); } } /** 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. **/ unsigned int binary_tree::bi_tree_max_branch(bi_tree_ptr root ) { unsigned int depth = 0; if (root != NULL) { unsigned int depth_left = 0; unsigned int depth_right = 0; if (root->leftptr != NULL) depth_left = bi_tree_max_branch(root->leftptr); if (root->rightptr != NULL) depth_right = bi_tree_max_branch(root->rightptr); // depth = max(depth_left, depth_right) if (depth_left > depth_right) depth = depth_left; else depth = depth_right; depth++; // Add one for the current node } return depth; } // binary_tree::bi_tree_max_branch /** 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". */ unsigned int binary_tree::bi_tree_cnt(bi_tree_ptr root) { unsigned int cnt = 0; if (root != NULL) { cnt = bi_tree_cnt(root->leftptr) + bi_tree_cnt(root->rightptr) + 1; } return cnt; } // binary_tree::bi_tree_cnt /* ------------------- Defaults for virtual functions --------------- */ /** The class derived from the binary tree object should supply memory allocation and deallocation functions. */ binary_tree::bi_tree_ptr binary_tree::get_tree_mem(void) { printf("binary_tree::get_tree_mem: no memory alloc provided for class\n"); return (bi_tree_ptr)NULL; } /** */ void binary_tree::free_tree_mem( bi_tree_ptr addr ) { printf("binary_tree::free_tree_mem: no memory dealloc provided for class\n"); }