Binary search tree (C Plus Plus)

From LiteratePrograms

Other implementations: C | C++ | Haskell | Java | Scheme | Standard ML

This article implements a simple binary search tree data structure in C++ with search, insert, and delete operations.

Contents 1 Node structure 2 Search 3 Insert 4 Deletion 5 Files

Node structure

We begin by defining a templated node class, which contains left and right child pointers and the node's data. The data is publically accessible but read-only to preserve the order property:

<<node class>>=
template <class T>
class BSTNode {
public:
    BSTNode method declarations
    T getData() { return data; }
private:
    T data;
    BSTNode<T>* left;
    BSTNode<T>* right;
};

We assume that T implements operator<, which we will need to order the nodes. Constructing nodes is straightforward:

<<BSTNode method declarations>>=
BSTNode(T data);
<<node constructor>>=
template <class T>
BSTNode::BSTNode(T data) {
    this->data = data;
    this->left = this->right = NULL;
}

We represent a whole tree with a class that just contains a pointer to the root node, which can be NULL for an empty tree. We make BSTNode a friend class so that the tree can access its internal child pointers but no one else can:

<<tree class>>=
template <class T>
class BinarySearchTree {
public:
    BinarySearchTree method declarations
private:
    BSTNode<T>* root;
    friend class BSTNode<T>;
};

Search

The most important operation on the tree is searching, which uses the properties of the binary search tree to traverse from the root down towards a given node. In the end it will either find the requested node or prove that it is not in the tree, in which case it returns a pointer to NULL. We return the address of the node pointer instead of just the node pointer to facilitate in-place updates.

<<BinarySearchTree method declarations>>=
BSTNode<T>** search(T data);
<<search operation>>=
template <class T>
BSTNode<T>** BinarySearchTree<T>::search(T data) {
    BSTNode<T>** node = &root;
    while (*node != NULL) {
          if (data < (*node)->data)
            node = &(*node)->left;
        else if ((*node)->data < data)
            node = &(*node)->right;
        else
            break;
    }
    return node;
}

Insert

(Warning: This section contains errors!) Inserting is now simple. We search for the node, and if it is not found, we create a new node and put it in the place the search function expected to find it, which is where it belongs in the tree. This particular insertion function does not allow duplicate values in the tree (set semantics), but one that does would be similar.

<<BinarySearchTree method declarations>>=
void insert(T data);
<<insert operation>>=
template <class T>
void BinarySearchTree<T>::insert(T data) {
    BSTNode<T>** node = search(data);
    if (*node == NULL) {
        *node = new BSTNode<T>(data);
    }
}

Deletion

Deletion is the most complicated operation. We focus on deleting nodes rather than values, since search() can be used to find a node based on a value if necessary. Deleting a node with one child or less is simple; we just replace it with its child:

<<BinarySearchTree method declarations>>=
void delete_node(BSTNode<T>** node);
<<delete operation>>=
template <class T>
void BinarySearchTree<T>::delete_node(BSTNode<T>** node) {
    BSTNode<T>* old_node = *node;
    if ((*node)->left == NULL) {
        *node = (*node)->right;
        delete old_node;
    } else if ((*node)->right == NULL) {
        *node = (*node)->left;
        delete old_node;
    } else {
        delete node with two children
    }
}

A node's inorder predecessor is the node whose value immediately precedes the node's value in sorted order. We can find this node by following right child pointers repeatedly starting at the node's left child. Similarly, the inorder successor immediately follows it in sorted order, and can be found by following left child pointers starting at the node's right child.

<<find inorder predecessor>>=
BSTNode<T>** pred = &(*node)->left;
while ((*pred)->right != NULL) {
    pred = &(*pred)->right;
}

To delete a node with two children, as shown below, we simply exchange the value of the node with either its inorder predecessor or successor, then delete the node that we exchanged with. This preserves the order properties of the tree, and the predecessor/successor nodes always have at most one child, so we already know how to delete them. In this implementation, we choose to consistently use the predecessor.

<<delete node with two children>>=
find inorder predecessor
std::swap((*pred)->data, (*node)->data);
delete_node(pred);

We need a header for std::swap:

<<header files>>=
#include <algorithm>

Files

We can place this implementation in a source and header file for reuse:

<<bst.h>>=
#ifndef _BST_H_
#define _BST_H_
node class
tree class
#endif
<<bst.cpp>>=
header files
#include "bst.h"
search operation
insert operation
delete operation

This completes the implementation.