Binary Search Trees

For all nodes:

E.g.

We are assuming that the key values are unique.

If the key values were not unique, we could store records with the same key value in a linear linked list.

E.g.

For a set of key values (e.g. 1, 3, 5) there are many possible binary search trees:

Binary Search Tree Abstract Data Type

Each item stored in the binary search tree has a key and an info part.

The binary search tree sorts its items by ascending key values.

No two items can have the same key value.

Prototype: bool Search( /* in */ int key, /* out */ Info& info );

Purpose: Search the binary search tree for an item.

Preconditions:

Postconditions: If the item is found whose stored key == key, then Function value = true and info = item's info.
Otherwise Function value = false.

Prototype: bool Insert( /* in */ int key, /* in */ Info info );

Purpose: Insert a new item into the binary search tree at its correct position according to the binary search tree's sort order.

Preconditions: The binary search tree is not full.

Postconditions: If there was no item in the binary search tree whose stored key == key, then the new item has been inserted into the binary search tree at its correct position and Function value = true.

Otherwise, the binary search tree is unchanged and Function value = false.

Prototype: bool Delete( /* in */ int key );

Purpose: Delete an item from the binary search tree.

Preconditions: The binary search tree is not empty.

Postconditions: If there was an item in the binary search tree whose stored key == key, then it has been deleted from the binary search tree and Function value = true.

Otherwise, the binary search tree is unchanged and Function value = false.

Prototype: bool IsEmpty() const;

Purpose: Determines if the binary search tree is empty.

Preconditions:

Postconditions: Function value = true, if the binary search tree is empty, otherwise false.

Prototype: bool IsFull() const;

Purpose: Determines if the binary search tree is full.

Preconditions:

Postconditions: Function value = true, if the binary search tree is full, otherwise false.

Prototype: int Size() const;

Purpose: Return the size of the binary search tree.

Preconditions:

Postconditions: Function value = the number of items in the binary search tree.

Prototype: void Reset();

Purpose: Initialize a traversal of the binary search tree.

Preconditions: The binary search tree is not empty.

Postconditions: The list traversal cursor is positioned on the first item

Prototype: void Advance( /* out */ int& key, /* out */ Info& info );

Purpose: Return the current item, and then advance the traversal cursor to the next item in the binary search tree.

Preconditions: The traversal of the binary search tree has been initialized.
There is a current item.
There have been no intervening insertions or deletion into the binary search tree since the last traversal reset.

Postconditions: key == the stored key of the current item.
info == the stored info of the current item.

If there is a next item, the traversal cursor has advanced to it, otherwise the traversal cursor is undefined.

// BinarySearchTree.h

#ifndef BINARY_SEARCH_TREE_H

#define BINARY_SEARCH_TREE_H

#include <cstddef>

typedef int Info;

struct Node

{

int key;

Info info;

Node* left;

Node* right;

};

#include "stack.h"

class BinarySearchTree

{

public:

BinarySearchTree();

bool Search( /* in */ int key, /* out */ Info& info );

bool Insert( /* in */ int key, /* in */ Info info );

bool Delete( /* in */ int key );

bool IsEmpty() const;

bool IsFull() const;

int Size() const;

void Reset();

void Advance( /* out */ int& key, /* out */ Info& info );

private:

Node* root;

Stack current;

int size;

bool Search( /* in */ Node* ptr, /* in */ int key, /* out */ Info& info );

bool Insert( /* in */ Node* ptr, /* in */ Node* backup, /* in */ int key, /* in */ Info info );

bool Delete( /* in */ Node* ptr, /* in */ Node* backup, /* in */ int key );

void DeleteNode( /* in */ Node* ptr, /* in */ Node* backup );

void DeletePredecessorNode( /* in */ Node* ptr, /* in */ Node* backup, /* out */ int& key, /* out */ Info& info );

};

#endif

Constructor

BinarySearchTree::BinarySearchTree()

{

root = NULL;

size = 0;

}

Search

bool BinarySearchTree::Search( /* in */ int key, /* out */ Info& info )

{

return Search( root, key, info );

}

bool BinarySearchTree::Search ( /* in */ Node* ptr, /* in */ int key, /* out */ Info& info )

{

if ( ptr == NULL )

return false;

if ( key == ptr->key )

{

info = ptr->info;

return true;

}

if ( key < ptr->key )

return Search( ptr->left, key, info );

else // key > ptr->key

return Search( ptr->right, key, info );

}

Insert

A new node can be inserted into a binary search tree in several different places

E.g.

Indeed, after inserting 4, the binary search tree could become:

We will insert new nodes as leaves.

Starting from the root, traverse down the binary search tree until we find the key or reach NULL. At each node compare the search key to the stored key, to decide whether to go left or right. If we reach NULL, insert the node as a child of *backup.

bool BinarySearchTree::Insert( /* in */ int key, /* in */ Info info )

{

return Insert( root, NULL, key, info );

}

bool BinarySearchTree::Insert( /* in */ Node* ptr, /* in */ Node* backup, /* in */ int key, /* in */ Info info )

{

if ( ptr == NULL )

{

Node* newPtr = new Node;

newPtr->key = key;

newPtr->info = info;

newPtr->left = NULL;

newPtr->right = NULL;

size++;

if ( root == NULL )

root = newPtr;

else if ( key < backup->key )

backup->left = newPtr;

else

backup->right = newPtr;

return true;

}

if ( key == ptr->key )

return false;

if ( key < ptr->key )

return Insert( ptr->left, ptr, key, info);

else // key > ptr->key

return Insert( ptr->right, ptr, key, info );

}

Delete

When deleting a leaf node the parent's corresponding child pointer is assigned NULL.

When deleting a node that has exactly 1 subtree, the subtree becomes a subtree of the parent.

When deleting a node N that has 2 subtrees:

[1] find the node M with the largest key less than N's key. The M node has at most one subtree.

[2] swap the nodes N and M

[3] delete node N.

bool BinarySearchTree::Delete( /* in */ int key )

{

return Delete( root, NULL, key );

}

bool BinarySearchTree::Delete( /* in */ Node* ptr, /* in */ Node* backup, /* in */ int key )

{

if ( ptr == NULL )

return false;

if ( key == ptr->key )

{

if ( ptr->left == NULL || ptr->right == NULL )

{

DeleteNode( ptr, backup );

}

else

{

int key;

Info info;

DeletePredecessorNode( ptr->left, ptr, key, info );

ptr->key = key;

ptr->info = info;

}

size--;

return true;

}

if ( key < ptr->key )

return Delete( ptr->left, ptr, key );

else // key > ptr->key

return Delete( ptr->right, ptr, key );

}

// ----- DeletePredecessorNode -----

void BinarySearchTree::DeletePredecessorNode( /* in */ Node* ptr, /* in */ Node* backup, /* out */ int& key, /* out */ Info& info )

{

while ( ptr->right != NULL )

{

backup = ptr;

ptr = ptr->right;

}

key = ptr->key;

info = ptr->info;

DeleteNode( ptr, backup );

}

// ----- DeleteNode -----

//

// Delete the node pointed to by ptr.

// The node has 0 or 1 child nodes (but not 2 child nodes).

void BinarySearchTree::DeleteNode( /* in */ Node* ptr, /* in */ Node* backup )

{

if ( ptr == root )

{

if ( ptr->left == NULL )

root = ptr->right;

else

root = ptr->left;

}

else if ( ptr == backup->left )

{

if ( ptr->left == NULL )

backup->left = ptr->right;

else

backup->left = ptr->left;

}

else

{

if ( ptr->left == NULL )

backup->right = ptr->right;

else

backup->right = ptr->left;

}

delete ptr;

}

IsEmpty

bool BinarySearchTree::IsEmpty() const

{

return ( root == NULL );

}

IsFull

bool BinarySearchTree::IsFull() const

{

return false;

}

Size

int BinarySearchTree::Size() const

{

return size;

}

While traversing the binary search tree, we use a stack of Node* to keep track of visited nodes.

// stack.h

#ifndef STACK_H

#define STACK_H

// A stack of pointers to nodes in a binary search tree.

struct Node; // Binary search tree node

typedef Node* Item;

class Stack {

public:

Stack();

~Stack();

void Push( /* in */ Item newItem );

Item Top() const;

Item Pop();

bool IsEmpty() const;

bool IsFull() const;

private:

struct StackNode

{

Item item;

StackNode* next;

};

StackNode* top;

};

#endif

Reset

void BinarySearchTree::Reset()

{

Node* ptr = root;

while ( ptr != NULL )

{

current.Push( ptr );

ptr = ptr->left;

}

}

Advance

void BinarySearchTree::Advance(/* out */ int& key, /* out */ Info& info )

{

Node* ptr = current.Pop();

key = ptr->key;

info = ptr->info;

if ( ptr->right != NULL )

{

ptr = ptr->right;

while ( ptr != NULL )

{

current.Push( ptr );

ptr = ptr->left;

}

}

}