Binary Search Tree

Topics:

Overview
Data Structures
Functions
Tree Iterator

Overview

The gxBStreeNode_t, gxBStree, and gxBStreeNode classes makeup a generic binary search tree class. This tree implementation is designed to work with minimum overhead by eliminating excessive pointer manipulation and execution cycles associated with tree rotations and balancing.

A tree is a recursive data structure used to store a hierarchical collection of nodes starting at a root node pointing down to parent and child nodes to leaf nodes (nodes with no children). A node is a container used to store left and right pointers to other nodes and some type of data. Unlike linked lists, where only forward and backward movements are allowed, trees allow left and right movements. A binary search tree is a tree that uses binary nodes (nodes with no more then two children) kept in sort order, with smaller nodes on the left and larger nodes on the right. The height of a tree is maximum number of nodes that must be visited on any path from the root to a leaf. In a binary search tree the efficiency of the tree depends on the height of the tree.

Data Structures

The tree node type is a data structure used to store left and right pointers. It is a reusable base class that can be shared by multiple tree implementations regardless of the data type.

struct gxBStreeNode_t
{
  gxBStreeNode_t *left;  // Pointer to the left sub-tree
  gxBStreeNode_t *right; // Pointer to the right sub-tree
};

The generic tree node class inherits the tree node type structure and adds a data type to the node.

template<class TYPE>
class gxBStreeNode : public gxBStreeNode_t
{
public:
  gxBStreeNode() { right = left = 0; }
  gxBStreeNode(TYPE &X) : data(X) { right = left = 0; }
  ~gxBStreeNode() { }

public: // Type-casting functions
  gxBStreeNode *GetLeft() const { return (gxBStreeNode<TYPE> *)left; }
  gxBStreeNode *GetLeft() { return (gxBStreeNode<TYPE> *)left; }
  gxBStreeNode *GetRight() const { return (gxBStreeNode<TYPE> *)right; }
  gxBStreeNode *GetRight() { return (gxBStreeNode<TYPE> *)right; }
  
public:
  TYPE data; // User defined node data type
};

Functions

gxBStree::gxBStree()
gxBStree::~gxBStree()
gxBStree::Clear()
gxBStree::Delete()
gxBStree::DeleteTree()
gxBStree::DetachNode()
gxBStree::ExtractFirst()
gxBStree::ExtractLast()
gxBStree::Find()
gxBStree::FindFirst()
gxBStree::FindLast()
gxBStree::GetRoot()
gxBStree::Insert()
gxBStree::IsEmpty()

gxBStree::gxBStree() - Default class constructor.

gxBStree::gxBStree(const gxBStree<TYPE> &ob) - Private class copy constructor used to disallow copying.

void gxBStree::operator=(const gxBStree<TYPE> &ob) - Private assignment operator used to disallow assignment.

gxBStree::~gxBStree() - Class destructor responsible for clearing the tree when a tree object is destroyed.

void gxBStree::Clear() - Public member function used to clear the tree.

int gxBStree::Delete(TYPE &X) - Public member function used to delete the specified entry from the tree. Returns false if the entry does not exist.

void gxBStree::DeleteTree(gxBStreeNode<TYPE> *tree) - Private member function used to recursively clear the tree from the bottom up. NOTE: The node data must be destroyed by the TYPE destructor or the memory for the node data will not be released.

gxBStreeNode<TYPE> *gxBStree::DetachNode(TYPE &X) - Private member function used to detach the node from its current position. Returns a pointer to the detached node or a null value if the node was not found.

int gxBStree::ExtractFirst(TYPE &X) - Public queue operation used to extract the first node from the tree in sort order. Returns true if the node was extracted.

int gxBStree::ExtractLast(TYPE &X) - Public queue operation used to extract the last node from the tree in sort order. Returns true if the node was extracted.

int gxBStree::Find(TYPE &X) - Public member function used to search the tree for the specified entry. Return true if the entry was found or false if the entry does not exist.

int gxBStree::FindFirst(TYPE &X) - Public member function used to find the left most node in the tree. Returns false if the tree is empty.

int gxBStree::FindLast(TYPE &X) - Public member function used to find the right most node in the tree. Returns false if the tree is empty.

gxBStreeNode<TYPE> *gxBStree::GetRoot() - Public member function that returns a pointer to the root node.

int gxBStree::Insert(TYPE &X, int *exists = 0) - Public unbalanced tree insertion routine used to insert a node into the tree. Returns false is an error occurs or the node already exists. If the "exists" variable is initialized by the application, the "exists" variable will be set to true if this entry already exists.

int gxBStree::IsEmpty() - Public member function that returns true if the tree is empty

Binary Search Tree Iterator

The binary search tree iterator class is used for sort order tree iterations. It uses an external stack to traverse the tree in order.

Functions:
gxBStreeIterator::gxBStreeIterator(gxBStreeNode_t *node) - Class constructor used to construct and initialize a tree iterator object.

gxBStreeNode_t *gxBStreeIterator::GetNext() - Public member function that returns the next node in the tree in sort order.

void gxBStreeIterator::Reset(gxBStreeNode_t *node) - Public member function used to initialize the tree iterator object.

void gxBStreeIterator::Reset() - Public member function used to reset the tree iterator if this object has been previously initialized.

Example:

void ListInOrder(gxBStree<UString> &tree)
// List all the tree nodes using a tree iterator object.
{
  gxBStreeNode<UString> *node = tree.GetRoot();
  gxBStreeIterator tree_iterator(node);
  while((node = (gxBStreeNode<UString> *)tree_iterator.GetNext()) != 0) {
    cout << node->data << endl;
  }
  cout << endl;
}