Aaron Gadberry

Help – v. helped, help·ing, helps

Was this site helpful?
My Amazon.com Wishlist

Searching: Binary Tree (Unbalanced)

24th January 2006 - By Paradochs

Information

  • Order: O(n)
  • Best Case: O(1)
  • Average: O(n/2)

Description (from wikipedia)

In computer science, a binary search tree (BST) is a binary tree where every node has a value, every node’s left subtree contains only values less than or equal to the node’s value, and every node’s right subtree contains only values that are greater than or equal. This requires that the values have a linear order. New nodes are added as leaves. Sort algorithms and search algorithms exist for binary search trees. The values of a binary search tree can be retrieved in ascending order using an in-order traversal.

Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays. We may or may not choose to allow duplicate values in a BST; if we do, it represents a multiset, and inequalities for the left and right subtrees above are non-strict (they have or equal to). If we do not, the inequalities can be taken as strict, and insertion operations must be modified to fail if the value being inserted is already present; in this case the BST represents a set with unique values, like the mathematical set.

Searching a binary tree for a specific value is a recursive process that we can perform due to the ordering it imposes. We begin by examining the root. If the value equals the root, the value exists in the tree. If it is less than the root, then it must be in the left subtree, so we recursively search the left subtree in the same manner. Similarly, if it is greater than the root, then it must be in the right subtree, so we recursively search the right subtree in the same manner. If we reach an external node, then the item is not where it would be if it were present, so it does not lie in the tree at all. A comparison may be made with binary search, which operates in nearly the same way but using random access on an array instead of following links.

C++ Files and Code Listings

This code has a few built in functions to time the sort and count the number of comparisons.
This code was written and compiled successfully in Visual Studio .NET.

UnbalancedBinaryTree.h
/* Travis Gadberry Patrick Hesser Chris Ladewig Adapted from Open Source Code UnbalancedBinaryTree.h 21Mar05 */ #ifndef UNBALANCED_BINARY_TREE_H #define UNBALANCED_BINARY_TREE_H #include "dsexceptions.h" #include <iostream> // For NULL #include <vector> #include <time.h> using namespace std; // Binary node and forward declaration because g++ does // not understand nested classes. template <class Comparable> class UnbalancedBinaryTree; template <class Comparable> class BinariNode { Comparable element; BinariNode *left; BinariNode *right; BinariNode( const Comparable & theElement, BinariNode *lt, BinariNode *rt ) : element( theElement ), left( lt ), right( rt ) { } friend class UnbalancedBinaryTree<Comparable>; }; // UnbalancedBinaryTree class // // CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds // // ******************PUBLIC OPERATIONS********************* // void insert( x ) --> Insert x // void remove( x ) --> Remove x // Comparable find( x ) --> Return item that matches x // Comparable findMin( ) --> Return smallest item // Comparable findMax( ) --> Return largest item // boolean isEmpty( ) --> Return true if empty; else false // void makeEmpty( ) --> Remove all items // void printTree( ) --> Print tree in sorted order template <class Comparable> class UnbalancedBinaryTree { public: explicit UnbalancedBinaryTree( const Comparable & notFound ); UnbalancedBinaryTree( const UnbalancedBinaryTree & rhs ); ~UnbalancedBinaryTree( ); const Comparable & findMin( ) const; const Comparable & findMax( ) const; const Comparable & find( const Comparable & x ); bool isEmpty( ) const; void printTree( ) const; void makeEmpty( ); void insert( const Comparable & x ); void remove( const Comparable & x ); int getIncrements(); double getCreationTime(); double getSearchTime(); void insertIntArray(int *, int); void insertIntVector(vector<int>); void resetIncrements(); const UnbalancedBinaryTree & operator=( const UnbalancedBinaryTree & rhs ); private: BinariNode<Comparable> *root; const Comparable ITEM_NOT_FOUND; const Comparable & elementAt( BinariNode<Comparable> *t ) const; void insert( const Comparable & x, BinariNode<Comparable> * & t ); void remove( const Comparable & x, BinariNode<Comparable> * & t ) const; BinariNode<Comparable> * findMin( BinariNode<Comparable> *t ) const; BinariNode<Comparable> * findMax( BinariNode<Comparable> *t ) const; BinariNode<Comparable> * find( const Comparable & x, BinariNode<Comparable> *t ); void makeEmpty( BinariNode<Comparable> * & t ) const; void printTree( BinariNode<Comparable> *t ) const; BinariNode<Comparable> * clone( BinariNode<Comparable> *t ) const; int increments; double creationTime, searchTime; }; #endif
UnbalancedBinaryTree.cpp
/* Travis Gadberry Patrick Hesser Chris Ladewig Adapted from Open Source Code UnbalancedBinaryTree.cpp 21Mar05 */ #include "UnbalancedBinaryTree.h" using namespace std; /** * Implements an unbalanced binary search tree. * Note that all "matching" is based on the < method. * Note: Class makes use of interface of comparable parameter */ /** * Construct the tree. */ template <class Comparable> UnbalancedBinaryTree<Comparable>::UnbalancedBinaryTree( const Comparable & notFound ) : root( NULL ), ITEM_NOT_FOUND( notFound ) { } /** * Copy constructor. */ template <class Comparable> UnbalancedBinaryTree<Comparable>:: UnbalancedBinaryTree( const UnbalancedBinaryTree<Comparable> & rhs ) : root( NULL ), ITEM_NOT_FOUND( rhs.ITEM_NOT_FOUND ) { *this = rhs; } /** * Destructor for the tree. */ template <class Comparable> UnbalancedBinaryTree<Comparable>::~UnbalancedBinaryTree( ) { makeEmpty( ); } /** * Insert x into the tree; duplicates are ignored. */ template <class Comparable> void UnbalancedBinaryTree<Comparable>::insert( const Comparable & x ) { insert( x, root ); } /** * Remove x from the tree. Nothing is done if x is not found. */ template <class Comparable> void UnbalancedBinaryTree<Comparable>::remove( const Comparable & x ) { remove( x, root ); } /** * Find the smallest item in the tree. * Return smallest item or ITEM_NOT_FOUND if empty. */ template <class Comparable> const Comparable & UnbalancedBinaryTree<Comparable>::findMin( ) const { return elementAt( findMin( root ) ); } /** * Find the largest item in the tree. * Return the largest item of ITEM_NOT_FOUND if empty. */ template <class Comparable> const Comparable & UnbalancedBinaryTree<Comparable>::findMax( ) const { return elementAt( findMax( root ) ); } /** * Find item x in the tree. * Return the matching item or ITEM_NOT_FOUND if not found. */ template <class Comparable> const Comparable & UnbalancedBinaryTree<Comparable>:: find( const Comparable & x ) { time_t t1, t2; t1 = clock(); BinariNode<Comparable> *result = find(x,root); t2 = clock(); searchTime = (t2 - t1)/CLOCKS_PER_SEC; return elementAt(result); } /** * Make the tree logically empty. */ template <class Comparable> void UnbalancedBinaryTree<Comparable>::makeEmpty( ) { makeEmpty( root ); } /** * Test if the tree is logically empty. * Return true if empty, false otherwise. */ template <class Comparable> bool UnbalancedBinaryTree<Comparable>::isEmpty( ) const { return root == NULL; } /** * Print the tree contents in sorted order. */ template <class Comparable> void UnbalancedBinaryTree<Comparable>::printTree( ) const { if( isEmpty( ) ) cout << "Empty tree" << endl; else printTree( root ); } /** * Deep copy. */ template <class Comparable> const UnbalancedBinaryTree<Comparable> & UnbalancedBinaryTree<Comparable>:: operator=( const UnbalancedBinaryTree<Comparable> & rhs ) { if( this != &rhs ) { makeEmpty( ); root = clone( rhs.root ); } return *this; } /** * Internal method to get element field in node t. * Return the element field or ITEM_NOT_FOUND if t is NULL. */ template <class Comparable> const Comparable & UnbalancedBinaryTree<Comparable>:: elementAt( BinariNode<Comparable> *t ) const { if( t == NULL ) return ITEM_NOT_FOUND; else return t->element; } /** * Internal method to insert into a subtree. * x is the item to insert. * t is the node that roots the tree. * Set the new root. */ template <class Comparable> void UnbalancedBinaryTree<Comparable>:: insert( const Comparable & x, BinariNode<Comparable> * & t ) { if( t == NULL ) t = new BinariNode<Comparable>( x, NULL, NULL ); else if( x < t->element ) insert( x, t->left ); else if( t->element < x ) insert( x, t->right ); } /** * Internal method to remove from a subtree. * x is the item to remove. * t is the node that roots the tree. * Set the new root. */ template <class Comparable> void UnbalancedBinaryTree<Comparable>:: remove( const Comparable & x, BinariNode<Comparable> * & t ) const { if( t == NULL ) return; // Item not found; do nothing if( x < t->element ) remove( x, t->left ); else if( t->element < x ) remove( x, t->right ); else if( t->left != NULL && t->right != NULL ) // Two children { t->element = findMin( t->right )->element; remove( t->element, t->right ); } else { BinariNode<Comparable> *oldNode = t; t = ( t->left != NULL ) ? t->left : t->right; delete oldNode; } } /** * Internal method to find the smallest item in a subtree t. * Return node containing the smallest item. */ template <class Comparable> BinariNode<Comparable> * UnbalancedBinaryTree<Comparable>::findMin( BinariNode<Comparable> *t ) const { if( t == NULL ) return NULL; if( t->left == NULL ) return t; return findMin( t->left ); } /** * Internal method to find the largest item in a subtree t. * Return node containing the largest item. */ template <class Comparable> BinariNode<Comparable> * UnbalancedBinaryTree<Comparable>::findMax( BinariNode<Comparable> *t ) const { if( t != NULL ) while( t->right != NULL ) t = t->right; return t; } /** * Internal method to find an item in a subtree. * x is item to search for. * t is the node that roots the tree. * Return node containing the matched item. */ template <class Comparable> BinariNode<Comparable> * UnbalancedBinaryTree<Comparable>:: find( const Comparable & x, BinariNode<Comparable> *t ) { if(increments++, (t == NULL) ) return NULL; else if(increments++, x < t->element ) return find( x, t->left ); else if(increments++, t->element < x ) return find( x, t->right ); else return t; // Match } template <class Comparable> int UnbalancedBinaryTree<Comparable>:: getIncrements() { return increments; } template <class Comparable> double UnbalancedBinaryTree<Comparable>:: getCreationTime() { return creationTime; } template <class Comparable> double UnbalancedBinaryTree<Comparable>:: getSearchTime() { return searchTime; } template <class Comparable> void UnbalancedBinaryTree<Comparable>:: insertIntArray(int * A, int n) { time_t t1, t2; t1 = clock(); for(int j = 0; j < n; j++) insert(A[j],root); t2 = clock(); creationTime = (t2 - t1)/CLOCKS_PER_SEC; } template <class Comparable> void UnbalancedBinaryTree<Comparable>:: insertIntVector(vector<int> V) { time_t t1, t2; t1 = clock(); int n = V.size(); int * A = new int[n]; for(int i=0; i<n; i++) A[i] = V.at(i); for(int j = 0; j<n; j++) insert(A[j], root); t2 = clock(); creationTime = (t2 - t1)/CLOCKS_PER_SEC; } template <class Comparable> void UnbalancedBinaryTree<Comparable>:: resetIncrements() { increments = 0; creationTime = 0; searchTime = 0; } /****** NONRECURSIVE VERSION************************* template <class Comparable> BinariNode<Comparable> * UnbalancedBinaryTree<Comparable>:: find( const Comparable & x, BinariNode<Comparable> *t ) const { while( t != NULL ) if( x < t->element ) t = t->left; else if( t->element < x ) t = t->right; else return t; // Match return NULL; // No match } *****************************************************/ /** * Internal method to make subtree empty. */ template <class Comparable> void UnbalancedBinaryTree<Comparable>:: makeEmpty( BinariNode<Comparable> * & t ) const { if( t != NULL ) { makeEmpty( t->left ); makeEmpty( t->right ); delete t; } t = NULL; } /** * Internal method to print a subtree rooted at t in sorted order. */ template <class Comparable> void UnbalancedBinaryTree<Comparable>::printTree( BinariNode<Comparable> *t ) const { if( t != NULL ) { printTree( t->left ); cout << t->element << endl; printTree( t->right ); } } /** * Internal method to clone subtree. */ template <class Comparable> BinariNode<Comparable> * UnbalancedBinaryTree<Comparable>::clone( BinariNode<Comparable> * t ) const { if( t == NULL ) return NULL; else return new BinariNode<Comparable>( t->element, clone( t->left ), clone( t->right ) ); }
dsexceptions.h
/* Travis Gadberry Patrick Hesser Chris Ladewig Adapted from Open Source Code dsexceptions.h 21Mar05 */ #ifndef DSEXCEPTIONS_H_ #define DSEXCEPTIONS_H_ class Underflow { }; class Overflow { }; class OutOfMemory { }; class BadIterator { }; #endif

One Response to “Searching: Binary Tree (Unbalanced)”

  1. Aaron Gadberry » Blog Archive » Searching: Driver Program for Searches Says:

    […] Binary Tree (Unbalanced) […]

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>