Searching: Binary Tree (Balanced)
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++ Code
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.
Note: This is the exact same as unbalanced, except for the function that sorts and reorders the input.
BalancedBinaryTree.h
/*
Travis Gadberry
Patrick Hesser
Chris Ladewig
Adapted from Open Source Code
BalancedBinaryTree.h
21Mar05
*/
#ifndef BALANCED_BINARY_TREE_H
#define BALANCED_BINARY_TREE_H
#include "dsexceptions.h"
#include "QuickSort.h"
#include <iostream> // For NULL
#include <time.h>
#include <vector>
using namespace std;
// Binary node and forward declaration because g++ does
// not understand nested classes.
template <class Comparable>
class BalancedBinaryTree;
template <class Comparable>
class BinaryNode
{
Comparable element;
BinaryNode *left;
BinaryNode *right;
BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
: element( theElement ), left( lt ), right( rt ) { }
friend class BalancedBinaryTree<Comparable>;
};
// BalancedBinaryTree 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 BalancedBinaryTree
{
public:
explicit BalancedBinaryTree( const Comparable & notFound );
BalancedBinaryTree( const BalancedBinaryTree & rhs );
~BalancedBinaryTree( );
const Comparable & findMin( ) const;
const Comparable & findMax( ) const;
const Comparable & find( const Comparable & x );
bool isEmpty( ) const;
void printTree( ) const;
void BalancedTreeRecursion(int* A, int P, int Q);
void makeEmpty( );
void insert( const Comparable & x );
void remove( const Comparable & x );
int getIncrements();
double getCreationTime();
double getSearchTime();
void insertIntArray(int *, int);
void insertIntVector(const vector<int>);
void resetIncrements();
void rotateRight(BinaryNode<Comparable> *);
void rotateLeft(BinaryNode<Comparable> *);
int getHeight(BinaryNode<Comparable> *);
void balance(BinaryNode<Comparable> *);
const BalancedBinaryTree & operator=( const BalancedBinaryTree & rhs );
private:
BinaryNode<Comparable> *root;
const Comparable ITEM_NOT_FOUND;
const Comparable & elementAt( BinaryNode<Comparable> *t ) const;
void insert( const Comparable & x, BinaryNode<Comparable> * & t );
void remove( const Comparable & x, BinaryNode<Comparable> * & t ) const;
BinaryNode<Comparable> * findMin( BinaryNode<Comparable> *t ) const;
BinaryNode<Comparable> * findMax( BinaryNode<Comparable> *t ) const;
BinaryNode<Comparable> * find( const Comparable & x, BinaryNode<Comparable> *t );
void makeEmpty( BinaryNode<Comparable> * & t ) const;
void printTree( BinaryNode<Comparable> *t ) const;
BinaryNode<Comparable> * clone( BinaryNode<Comparable> *t ) const;
int increments;
double creationTime, searchTime;
};
#endif
BalancedBinaryTree.cpp
/*
Travis Gadberry
Patrick Hesser
Chris Ladewig
Adapted from Open Source Code
BalancedBinaryTree.cpp
21Mar05
*/
#include "BalancedBinaryTree.h"
using namespace std;
/**
* Implements an unbalanced binary search tree.
* Note that all "matching" is based on the < method.
*/
template <class Comparable>
BalancedBinaryTree<Comparable>::
BalancedBinaryTree(const Comparable & notFound) :
root(NULL), ITEM_NOT_FOUND(notFound)
{
}
template <class Comparable>
BalancedBinaryTree<Comparable>::
BalancedBinaryTree(const BalancedBinaryTree<Comparable> & rhs) :
root(NULL), ITEM_NOT_FOUND(rhs.ITEM_NOT_FOUND) {
*this = rhs;
}
template <class Comparable>
BalancedBinaryTree<Comparable>::
~BalancedBinaryTree() {
makeEmpty();
}
template <class Comparable>
void
BalancedBinaryTree<Comparable>::
insert(const Comparable & x) {
insert(x, root);
}
template <class Comparable>
void
BalancedBinaryTree<Comparable>::
remove(const Comparable & x) {
remove(x, root);
}
template <class Comparable>
const Comparable &
BalancedBinaryTree<Comparable>::
findMin() const {
return elementAt(findMin(root));
}
template <class Comparable>
const Comparable &
BalancedBinaryTree<Comparable>::
findMax() const {
return elementAt(findMax(root));
}
template <class Comparable>
const Comparable &
BalancedBinaryTree<Comparable>::
find(const Comparable & x) {
time_t t1, t2;
t1 = clock();
BinaryNode<Comparable> *result = find(x,root);
t2 = clock();
searchTime = (t2 - t1)/CLOCKS_PER_SEC;
return elementAt(result);
}
template <class Comparable>
void
BalancedBinaryTree<Comparable>::
makeEmpty() {
makeEmpty(root);
}
template <class Comparable>
bool
BalancedBinaryTree<Comparable>::
isEmpty() const {
return root == NULL;
}
template <class Comparable>
void
BalancedBinaryTree<Comparable>::
printTree() const {
if(isEmpty())
cout << "Empty tree" << endl;
else
printTree(root);
}
template <class Comparable>
const BalancedBinaryTree<Comparable> &
BalancedBinaryTree<Comparable>::
operator=(const BalancedBinaryTree<Comparable> & rhs) {
if(this != &rhs) {
makeEmpty();
root = clone(rhs.root);
}
return *this;
}
template <class Comparable>
const Comparable & BalancedBinaryTree<Comparable>::
elementAt(BinaryNode<Comparable> *t) const {
if(t == NULL)
return ITEM_NOT_FOUND;
else
return t->element;
}
template <class Comparable>
void
BalancedBinaryTree<Comparable>::
insert(const Comparable & x, BinaryNode<Comparable> * & t) {
if(t == NULL)
t = new BinaryNode<Comparable>(x, NULL, NULL);
else if(x < t->element)
insert(x, t->left);
else if(t->element < x)
insert(x, t->right);
}
template <class Comparable>
void
BalancedBinaryTree<Comparable>::
remove(const Comparable & x, BinaryNode<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
{
BinaryNode<Comparable> *oldNode = t;
t = (t->left != NULL) ? t->left : t->right;
delete oldNode;
}
}
template <class Comparable>
BinaryNode<Comparable> *
BalancedBinaryTree<Comparable>::
findMin(BinaryNode<Comparable> *t) const {
if(t == NULL)
return NULL;
if(t->left == NULL)
return t;
return findMin(t->left);
}
template <class Comparable>
BinaryNode<Comparable> *
BalancedBinaryTree<Comparable>::findMax(BinaryNode<Comparable> *t) const {
if(t != NULL)
while(t->right != NULL)
t = t->right;
return t;
}
template <class Comparable>
BinaryNode<Comparable> *
BalancedBinaryTree<Comparable>::
find(const Comparable & x, BinaryNode<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
BalancedBinaryTree<Comparable>::
getIncrements() {
return increments;
}
template <class Comparable>
double
BalancedBinaryTree<Comparable>::
getCreationTime() {
return creationTime;
}
template <class Comparable>
double
BalancedBinaryTree<Comparable>::
getSearchTime() {
return searchTime;
}
template <class Comparable>
void
BalancedBinaryTree<Comparable>::
insertIntArray(int * A, int n) {
time_t t1, t2;
t1 = clock();
QuickSort* quick = new QuickSort(A,n);
quick->sort();
int * B = quick->getArray();
BalancedTreeRecursion(B,0,n-1);
t2 = clock();
creationTime = (t2 - t1)/CLOCKS_PER_SEC;
}
template <class Comparable>
void
BalancedBinaryTree<Comparable>::
insertIntVector(const 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);
QuickSort* quick = new QuickSort(A,n);
quick->sort();
int * B = quick->getArray();
BalancedTreeRecursion(B, 0, n-1);
t2 = clock();
creationTime = (t2 - t1)/CLOCKS_PER_SEC;
}
template <class Comparable>
void
BalancedBinaryTree<Comparable>::
BalancedTreeRecursion(int* A, int P, int Q)
{
int temp = (P+Q)/2;
insert(A[temp], root);
int J = temp-1;
int K = J + 2;
if(J <= P)
{
insert(A[P],root);
}
else
BalancedTreeRecursion(A,P,J);
if(K >= Q)
{
insert(A[Q],root);
}
else
BalancedTreeRecursion(A,K,Q);
}
template <class Comparable>
void
BalancedBinaryTree<Comparable>::
resetIncrements() {
increments = 0;
creationTime = 0;
searchTime = 0;
}
/****** NONRECURSIVE VERSION*************************
template <class Comparable>
BinaryNode<Comparable> *
BalancedBinaryTree<Comparable>::
find(const Comparable & x, BinaryNode<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
}
*****************************************************/
template <class Comparable>
void
BalancedBinaryTree<Comparable>::
makeEmpty(BinaryNode<Comparable> * & t) const {
if(t != NULL) {
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
}
t = NULL;
}
template <class Comparable>
void
BalancedBinaryTree<Comparable>::
printTree(BinaryNode<Comparable> *t) const {
if(t != NULL) {
printTree(t->left);
cout << t->element << endl;
printTree(t->right);
}
}
template <class Comparable>
BinaryNode<Comparable> *
BalancedBinaryTree<Comparable>::
clone(BinaryNode<Comparable> * t) const {
if(t == NULL)
return NULL;
else
return new BinaryNode<Comparable>(t->element, clone(t->left), clone(t->right));
}
template <class Comparable>
void
BalancedBinaryTree<Comparable>::
rotateRight(BinaryNode<Comparable> *t) {
BinaryNode<Comparable> temp = t->left;
t->left = temp->right;
temp->right = t;
t = temp;
}
template <class Comparable>
void
BalancedBinaryTree<Comparable>::
rotateLeft(BinaryNode<Comparable> *t) {
BinaryNode<Comparable> temp = t->right;
t->right = temp->left;
temp->left = t;
t = temp;
}
template <class Comparable>
int
BalancedBinaryTree<Comparable>::
getHeight(BinaryNode<Comparable> *t) {
int left_height = 0;
int right_height = 0;
if(t->left)
left_height = getHeight(t->left);
if(t->right)
right_height = getHeight(t->right);
if(right_height >= left_height)
return (right_height + 1);
else
return (left_height + 1);
}
template <class Comparable>
void
BalancedBinaryTree<Comparable>::
balance(BinaryNode<Comparable> *t) {
int left_height = getHeight(t->left);
int right_height = getHeight(t->right);
if(left_height-right_height > 1) {
int next_left = getHeight(t->left->left);
int next_right = getHeight(t->left->right);
if(next_right-next_left > 1) {
rotateLeft(t->left);
balance(t->left);
}
if(next_left-next_right > 1) {
rotateRight(t->left);
balance(t->left);
}
}
if(right_height-left_height > 1) {
int next_left = getHeight(t->right->left);
int next_right = getHeight(t->right->right);
if(next_right-next_left > 1) {
rotateLeft(t->right);
balance(t->right);
}
if(next_left-next_right > 1) {
rotateRight(t->right);
balance(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
January 24th, 2006 at 9:09 pm
[...] Comments (RSS) « How To: Run a Perl script from PHP Searching: Binary Tree (Balanced) » [...]