Wednesday, June 8, 2011

What is binary search trees? How to implement in C++?

This article explains the concept of binary search trees (BST) and provides a sample implementation in C++.
  • Binary Search Tree (BST) is a binary tree (has atmost 2 children). 
  • It is also referred as sorted/ ordered binary tree.
  • BST has the following properties. (notes from wikipedia)
    • The left subtree of a node contains only nodes with keys less than the node's key.
    • The right subtree of a node contains only nodes with keys greater than the node's key.
    • Both the left and right subtrees must also be binary search trees.
  • BST Operations:-
    • Searching in a BST
      • Examine the root node. If tree is NULL value doesn't exist.
      • If value equals the key in root search is successful and return.
      • If value is less than root, search the left sub-tree.
      • If value is greater than root, search the right sub-tree.
      • Continue until the value is found or the sub tree is NULL.
      • Time complexity. Average: O(log n), Worst: O(n) if the BST is unbalanced and resembles a linked list.
    • Insertion in BST
      • Insertion begin as a search.
      • Compare the key with root. If not equal search the left or right sub tre
      • When a leaf node is reached add the new node to left or right based on the value.
      • Time complexity. Average: O(log n), Worst O(n)
    • Deletion in BST
      • There are three possible cases to consider:
        • Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply remove it from the tree.
        • Deleting a node with one child: Remove the node and replace it with its child.
        • Deleting a node with two children: Call the node to be deleted N. Do not delete N. Instead, choose either its in-order successor node or its in-order predecessor node, R. Replace the value of N with the value of R, then delete R.

A sample implementation of BST using C++

#include <iostream>
using namespace std;

// A generic tree node class
class Node {
    int key;
    Node* left;
    Node* right;
    Node* parent;
public:
    Node() { key=-1; left=NULL; right=NULL; parent = NULL;};
    void setKey(int aKey) { key = aKey; };
    void setLeft(Node* aLeft) { left = aLeft; };
    void setRight(Node* aRight) { right = aRight; };
    void setParent(Node* aParent) { parent = aParent; };
    int Key() { return key; };
    Node* Left() { return left; };
    Node* Right() { return right; };
    Node* Parent() { return parent; };
};

// Binary Search Tree class
class Tree {
    Node* root;
public:
    Tree();
    ~Tree();
    Node* Root() { return root; };
    void addNode(int key);
    Node* findNode(int key, Node* parent);
    void walk(Node* node);
    void deleteNode(int key);
    Node* min(Node* node);
    Node* max(Node* node);
    Node* successor(int key, Node* parent);
    Node* predecessor(int key, Node* parent);
private:
    void addNode(int key, Node* leaf);
    void freeNode(Node* leaf);
};

// Constructor
Tree::Tree() {
    root = NULL;
}

// Destructor
Tree::~Tree() {
    freeNode(root);
}

// Free the node
void Tree::freeNode(Node* leaf)
{
    if ( leaf != NULL ) 
    {
        freeNode(leaf->Left());
        freeNode(leaf->Right());
        delete leaf;
    }
}

// Add a node [O(height of tree) on average]
void Tree::addNode(int key)
{
    // No elements. Add the root
    if ( root == NULL ) {
        cout << "add root node ... " << key << endl;
        Node* n = new Node();
        n->setKey(key);
    root = n;
    }
    else {
    cout << "add other node ... " << key << endl;
    addNode(key, root);
    }
}

// Add a node (private)
void Tree::addNode(int key, Node* leaf) {
    if ( key <= leaf->Key() )
    {
        if ( leaf->Left() != NULL )
            addNode(key, leaf->Left());
        else {
            Node* n = new Node();
            n->setKey(key);
            n->setParent(leaf);
            leaf->setLeft(n);
        }
    }
    else
    {
        if ( leaf->Right() != NULL )
            addNode(key, leaf->Right());
        else {
            Node* n = new Node();
            n->setKey(key);
            n->setParent(leaf);
            leaf->setRight(n);
        }
    }
}

// Find a node [O(height of tree) on average]
Node* Tree::findNode(int key, Node* node)
{
    if ( node == NULL )
        return NULL;
    else if ( node->Key() == key )
        return node;
    else if ( key <= node->Key() )
        findNode(key, node->Left());
    else if ( key > node->Key() )
        findNode(key, node->Right());
    else
        return NULL;
}

// Print the tree
void Tree::walk(Node* node)
{
    if ( node )
    {
        cout << node->Key() << " ";
        walk(node->Left());
        walk(node->Right());
    }
}

// Find the node with min key
// Traverse the left sub-tree recursively
// till left sub-tree is empty to get min
Node* Tree::min(Node* node)
{
    if ( node == NULL )
        return NULL;

    if ( node->Left() )
        min(node->Left());
    else
        return node;
}

// Find the node with max key
// Traverse the right sub-tree recursively
// till right sub-tree is empty to get max
Node* Tree::max(Node* node)
{
    if ( node == NULL )
        return NULL;

    if ( node->Right() )
        max(node->Right());
    else
        return node;
}

// Find successor to a node
// Find the node, get the node with max value
// for the right sub-tree to get the successor
Node* Tree::successor(int key, Node *node)
{
    Node* thisKey = findNode(key, node);
    if ( thisKey )
        return max(thisKey->Right());
}

// Find predecessor to a node
// Find the node, get the node with max value
// for the left sub-tree to get the predecessor
Node* Tree::predecessor(int key, Node *node)
{
    Node* thisKey = findNode(key, node);
    if ( thisKey )
        return max(thisKey->Left());
}

// Delete a node
// (1) If leaf just delete
// (2) If only one child delete this node and replace
// with the child
// (3) If 2 children. Find the predecessor (or successor).
// Delete the predecessor (or successor). Replace the
// node to be deleted with the predecessor (or successor).
void Tree::deleteNode(int key)
{
    // Find the node.
    Node* thisKey = findNode(key, root);

    // (1)
    if ( thisKey->Left() == NULL && thisKey->Right() == NULL )
    {
        if ( thisKey->Key() > thisKey->Parent()->Key() )
            thisKey->Parent()->setRight(NULL);
        else
            thisKey->Parent()->setLeft(NULL);

        delete thisKey;
    }

    // (2)
    if ( thisKey->Left() == NULL && thisKey->Right() != NULL )
    {
        if ( thisKey->Key() > thisKey->Parent()->Key() )
            thisKey->Parent()->setRight(thisKey->Right());
        else
            thisKey->Parent()->setLeft(thisKey->Right());

        delete thisKey;
    }
    if ( thisKey->Left() != NULL && thisKey->Right() == NULL )
    {
        if ( thisKey->Key() > thisKey->Parent()->Key() )
            thisKey->Parent()->setRight(thisKey->Left());
        else
            thisKey->Parent()->setLeft(thisKey->Left());

        delete thisKey;
    }

    // (3)
    if ( thisKey->Left() != NULL && thisKey->Right() != NULL )
    {
        Node* sub = predecessor(thisKey->Key(), thisKey);
        if ( sub == NULL )
            sub = successor(thisKey->Key(), thisKey);        

        if ( sub->Parent()->Key() <= sub->Key() )
            sub->Parent()->setRight(sub->Right());
        else
            sub->Parent()->setLeft(sub->Left());

        thisKey->setKey(sub->Key());
        delete sub;
    }
}

// Test main program
int main() {
    Tree* tree = new Tree();

    // Add nodes
    tree->addNode(300);
    tree->addNode(100);
    tree->addNode(200);
    tree->addNode(400);
    tree->addNode(500);

    // Traverse the tree
    tree->walk(tree->Root());
    cout << endl;

    // Find nodes
    if ( tree->findNode(500, tree->Root()) )
        cout << "Node 500 found" << endl;
    else
        cout << "Node 500 not found" << endl;

    if ( tree->findNode(600, tree->Root()) )
        cout << "Node 600 found" << endl;
    else
        cout << "Node 600 not found" << endl;

    // Min & Max
    cout << "Min=" << tree->min(tree->Root())->Key() << endl;
    cout << "Max=" << tree->max(tree->Root())->Key() << endl;

    // Successor and Predecessor
    cout << "Successor to 300=" <<
            tree->successor(300, tree->Root())->Key() << endl;
    cout << "Predecessor to 300=" <<
            tree->predecessor(300, tree->Root())->Key() << endl;

    // Delete a node
    tree->deleteNode(300);

    // Traverse the tree
    tree->walk(tree->Root());
    cout << endl;

    delete tree;
    return 0;
}

OUTPUT:-
add root node ... 300
add other node ... 100
add other node ... 200
add other node ... 400
add other node ... 500
300 100 200 400 500
Node 500 found
Node 600 not found
Min=100
Max=500
Successor to 300=500
Predecessor to 300=200
200 100 400

6 comments :

  1. Your implementation of sucessor is wrong. For example, what if a node doesn't have a right child? In this case, its successor would be in its ancestors. Same error for the implementation of predecessor.

    ReplyDelete
  2. From void Tree::deleteNode(int key)
    I have a question regarding part 1 of the above said function.
    Considering my B-Tree only has 1 node. won't this line give me error during compilation.
    if ( thisKey->Key() > thisKey->Parent()->Key() )
    As Node* thisKey = findNode(key, root); will set thisKey = root.
    And you are not setting any parent in this case. like, a root is a parent of it self. your addNode does not specify it anywhere.
    thisKey->Parent()->Key() might give an error.

    ReplyDelete
  3. In the function "findNode" you have forgotten the statement "return" before findNode(key, node->Left()); and findNode(key, node->Right());

    ReplyDelete
  4. Your implementation of successor is wrong. For example, what if a node doesn't have a right child? In this case, its successor would be in its ancestors.moreover,even if node x has right child ,successor of node x is leftmost node of x's right sub-tree
    so your function should be:


    Node* Tree::successor(int key, Node *node)
    {
    Node* thisKey = findNode(key, node);
    if ( thisKey )
    return min(thisKey->Right());
    }

    ReplyDelete
  5. I never understood BST.. you provided very detailed tutorial Thanks

    ReplyDelete
  6. Binary search trees and implementation is well explained. Thanks for that. You can find more here below.

    Implementation of the Binary tree in Cpp working code and tests

    ReplyDelete

Contact Form

Name

Email *

Message *

Back to Top