A Binary Search Tree Example

A Binary Tree is a tree where each node may have 0, 1 or 2 children and a Binary Search Tree is a binary tree with a special property that the value of node under discussion is less than all the nodes in its right subtree and greater than all the nodes in its left subtree.
The programs below describes the three basic operations in a binary search tree viz. search, insert and remove

1. Searching a node

  template <typename T>
  BSTNode<T>** BST<T>::find(BSTNode<T> **node, const T key)
  {
    if(*node == NULL || (*node)->key == key)
    {
      return node;
    }
    else if((*node)->key > key)
    {
      return find(&(*node)->left, key);
    }
    else
    {
      return find(&(*node)->right, key);
    }
  }

2. Inserting a node

template <typename T>
  void BST<T>::insert(T key)
  {
    BSTNode<T> **node = find(&m_root, key);
    if(*node == NULL)
    {
      *node = getNewNode(key);
    }
  }

3. Removing a node
Removing a node from binary search tree is the trickiest of all the operations. There are three cases to be considered when removing a node from a binary search tree:

Case 1. If both left and right child are null, the node can simply be deleted.

Case 2. If only one of the right child or left child is null, the address of the node is set to point to the left child or the right child which ever is not null and the current node is deleted.

Case 3. The complex of the three cases, if both left and right child are present. This requires finding the successor of the current node which is to be removed.

template <typename T>
  void BST<T>::remove(BSTNode<T> **node)
  {
    BSTNode<T> *old = *node;
    if((*node)->left == NULL)
    {
      *node = (*node)->right;
      delete old;
    }
    else if((*node)->right == NULL)
    {
      *node = (*node)->left;
      delete old;
    }
    else
    {
      BSTNode<T> **successor = getSuccessor(node);
      (*node)->key = (*successor)->key;
      remove(successor);
    }
  }

Following is the complete example showing the implementation details of the search, find and remove operations in a binary search tree.

The BST Node Class

 1 #ifndef _BSTNode_H_
 2 #define _BSTNode_H_
 3 #include <iostream>
 4 
 5 //File: BSTNode.h
 6 namespace algorithms
 7 {
 8   template <typename T>
 9   class BST;
10 
11   template <typename T>
12   class BSTNode
13   {
14   public:
15     BSTNode(T key);
16     ~BSTNode();
17 
18     friend class BST<T>;
19 
20   private:
21     BSTNode<T> *left;
22     BSTNode<T> *right;
23     T key;
24   };
25 };
26 
27 #include "BSTNode.hpp"
28 #endif //_BSTNode_H_

 1 //File: BSTNode.hpp
 2 namespace algorithms
 3 {
 4   template <typename T>
 5   BSTNode<T>::BSTNode(T key) : left(0), right(0)
 6   {
 7     this->key = key;
 8   }
 9 
10   template <typename T>
11   BSTNode<T>::~BSTNode()
12   {
13   }
14 }
15 

The Binary Search Tree Class

 1 #ifndef _BinarySearchTree_H_
 2 #define _BinarySearchTree_H_
 3 #include "BSTNode.h"
 4 
 5 //File: BST.h
 6 namespace algorithms
 7 {
 8   template <typename T>
 9   class BST
10   {
11   public:
12     BST();
13     ~BST();
14 
15     //modifiers
16     void insert(T key);
17     void remove(T key);
18     void clear();
19 
20     //accessors
21     bool find(T key);
22     bool isEmpty() const;
23 
24   private:
25     void remove(BSTNode<T> **node);
26     void clear(BSTNode<T> *node);
27     BSTNode<T>** find(BSTNode<T> **node, const T key);
28     BSTNode<T>** getSuccessor(BSTNode<T> **node);
29     BSTNode<T>* getNewNode(T key);
30 
31     //instance fields
32     BSTNode<T> *m_root;
33   };
34 };
35 
36 #include "BST.hpp"
37 #endif //_BinarySearchTree_H_

  1 //File: BST.hpp
  2 namespace algorithms
  3 {
  4   template <typename T>
  5   BST<T>::BST()
  6   {
  7     m_root = 0;
  8   }
  9 
 10   template <typename T>
 11   BST<T>::~BST()
 12   {
 13     clear();
 14   }
 15 
 16   template <typename T>
 17   void BST<T>::clear()
 18   {
 19     clear(m_root);
 20   }
 21 
 22   template <typename T>
 23   void BST<T>::clear(BSTNode<T> *node)
 24   {
 25     if(node != NULL)
 26     {
 27       clear(node->left);
 28       clear(node->right);
 29       delete node;
 30     }
 31   }
 32 
 33   template <typename T>
 34   void BST<T>::insert(T key)
 35   {
 36     BSTNode<T> **node = find(&m_root, key);
 37     if(*node == NULL)
 38     {
 39       *node = getNewNode(key);
 40     }
 41   }
 42 
 43   template <typename T>
 44   void BST<T>::remove(T key)
 45   {
 46     BSTNode<T> **node = find(&m_root, key);
 47     remove(node);
 48   }
 49 
 50   template <typename T>
 51   void BST<T>::remove(BSTNode<T> **node)
 52   {
 53     BSTNode<T> *old = *node;
 54     if((*node)->left == NULL)
 55     {
 56       *node = (*node)->right;
 57       delete old;
 58     }
 59     else if((*node)->right == NULL)
 60     {
 61       *node = (*node)->left;
 62       delete old;
 63     }
 64     else
 65     {
 66       BSTNode<T> **successor = getSuccessor(node);
 67       (*node)->key = (*successor)->key;
 68       remove(successor);
 69     }
 70   }
 71 
 72   template <typename T>
 73   BSTNode<T>** BST<T>::getSuccessor(BSTNode<T> **node)
 74   {
 75     BSTNode<T> **tmp = &(*node)->left;
 76     while((*tmp)->right != NULL)
 77     {
 78       tmp = &(*tmp)->right;
 79     }
 80     return tmp;
 81   }
 82 
 83   template <typename T>
 84   bool BST<T>::find(const T key)
 85   {
 86     BSTNode<T> **pos = find(&m_root, key);
 87     return *pos != NULL;
 88   }
 89 
 90   template <typename T>
 91   bool BST<T>::isEmpty() const
 92   {
 93     return m_root == 0;
 94   }
 95 
 96   template <typename T>
 97   BSTNode<T>** BST<T>::find(BSTNode<T> **node, const T key)
 98   {
 99     if(*node == NULL || (*node)->key == key)
100     {
101       return node;
102     }
103     else if((*node)->key > key)
104     {
105       return find(&(*node)->left, key);
106     }
107     else
108     {
109       return find(&(*node)->right, key);
110     }
111   }
112 
113   template <typename T>
114   BSTNode<T>* BST<T>::getNewNode(T key)
115   {
116     BSTNode<T> *node = new BSTNode<T>(key);
117     if(node == NULL)
118     {
119       std::cerr << "ERROR: Insufficient Memory";
120       std::cerr << std::endl;
121     }
122     return node;
123   }
124 }

The Client Program for testing the BST code above

 1 #include "BST.h"
 2 #define MAX 20
 3 using namespace algorithms;
 4 
 5 //File: Main.cpp
 6 int main(int argc, char *argv[])
 7 {
 8   int nodes[MAX] = { 50, 40, 60, 70, 80, 20, 30, 10, 90, 15, 35, 65, 75, 5, 1, 100, 110, 130, 120 };
 9   BST<int> bstInt;
10   for(int i = 0; i < MAX; ++i)
11   {
12     bstInt.insert(nodes[i]);
13   }
14 
15   std::cout << (bstInt.find(130) ? "true" : "false");
16   bstInt.remove(50);
17   std::cout << (bstInt.find(50)  ? "true" : "false");
18 
19   return 0;
20 }

Output of the run
$ ./BinarySearchTree.exe
truefalse

Read more ...

Static Library - An Introduction

Static library is a group of object files bundled together in an archive by the archiver program. The static libraries have a .a extension.

Advantages
1. The executable is not dependent on any library as the library code is included in the binary
2. In some cases performance improvement

Command for creating a static library

ar rcs -o libmylibrary.a file1.o file2.o file3.o

Steps for generating the static library libemployee.a for the Employee Program written in the previous post

1. Compiling source files to object files

g++ -Wall -c -fPIC -O -I. -o Employee.o Employee.cpp

2. Command for building the archive file libemployee.a

ar -rcs -o libemployee.a Employee.o

Read more ...

Shared Library - An Introduction

A shared library is a library required by an executable to run properly. Such executables are called incomplete executables as they call routines present in the shared library code. The executables generated from the shared library are smaller in size than the ones generated from a static library

When an executable built with shared library is run, the dynamic loader identifies the list of dependent libraries to be loaded and searches for them in the standard default locations and the locations pointed to by the environment variable LD_LIBRARY_PATH (Linux), SHLIB_PATH (HP-UX), LIBPATH (AIX)

Shown below is the Employee class which we will use to generate the shared library libemployee.so

 1 #ifndef _Employee_H_
 2 #define _Employee_H_
 3 
 4 //File: Employee.h
 5 
 6 #include <iostream>
 7 
 8 class Employee
 9 {
10   public:
11       Employee();
12       Employee(const std::string name, int age);
13       virtual ~Employee();
14 
15       //Modifiers
16       void setName(const std::string name);
17       void setAge(int age);
18 
19       //Accessors
20       const char* getName() const;
21       int getAge()          const;
22 
23   private:
24       std::string m_name;
25       int m_age;
26 };
27 
28 #endif //_Employee_H_

 1 #include "Employee.h"
 2 //File: Employee.cpp
 3 
 4 Employee::Employee()
 5 {
 6 }
 7 
 8 Employee::Employee(const std::string name, int age)
 9 {
10     m_name = name;
11     m_age = age;
12 }
13 
14 Employee::~Employee()
15 {
16 }
17 
18 void Employee::setName(const std::string name)
19 {
20     m_name = name;
21 }
22 
23 void Employee::setAge(int age)
24 {
25     m_age = age;
26 }
27 
28 const char* Employee::getName() const
29 {
30     return m_name.c_str();
31 }
32 
33 int Employee::getAge() const
34 {
35     return m_age;
36 }

Compiling the Employee source files to object files

g++ -Wall -c -fPIC -O -I. -o Employee.o Employee.cpp

Linking the object files to generate the shared library libemployee.so

gcc -o libemployee.so Employee.o -shared -fPIC -Wl,-rpath,. -L. -lstdc++

Read more ...

POSIX Threads - A simple Example

In our earlier post, we have written multithreaded program using win32 apis. This post deals with writing the multithreaded programs using POSIX thread apis. The important POSIX thread apis are namely pthread_create, pthread_exit and pthread_join

Create a thread

int pthread_create
(
    pthread_t *thread,
    const pthread_attr_t *attr,
    void *( *start_routine)(void *), 
    void *arg
);

Terminate a thread

void pthread_exit (void *retval);

Wait on a thread

int pthread_join (pthread_t thread, void **status);

The Complete Example

#include <pthread.h>
#include <iostream>

//File: SimpleThreadExample.cpp

#define MAX_THREADS 3
using namespace std;

void* func(void *args)
{
    int tp = *(int *)args * 10;
    while(tp--)
    {
        cout << *(int *) args;
        fflush(stdout);
        sleep(1);
    }

    cout << endl;
    pthread_exit((void *)10);
    return (void *)10;
}

int main(void)
{
    pthread_t tid[MAX_THREADS] = {0};
    int param[MAX_THREADS] = { 1, 2, 3 };

    int rc;
    for(int i = 0; i < MAX_THREADS; ++i)
    {
        rc = pthread_create(&tid[i], NULL, func, ¶m[i]);
        if(0 != rc)
        {
            cout << "ERROR: Thread Creation failed" << endl;
        }
        cout << "Thread[" << tid[i] << "] Created" << endl;
    }

    void *status[3];
    for(int i = 0; i < MAX_THREADS; ++i)
    {
        rc = pthread_join(tid[i], &status[i]);
    }

    for(int i = 0; i < MAX_THREADS; ++i)
    {
        cout << "Thread[" << tid[i] << "] returned with exit code=" << (long) status[i] << endl;
    }

    cout << "Main thread terminating" << endl;
    return 0;
}

The makefile for the project

#-----------------------------------------------------------------------
#                   A simple thread example
#-----------------------------------------------------------------------
PROJECT := SimpleThreadExample

SRCEXT := .h .cpp
OBJEXT := .o
EXEEXT := .exe

#compilers
CC := gcc
CXX := g++

#flags
CFLAGS := -o
CXXFLAGS := -o
LDFLAGS := -lpthread -o

#disable implicit suffix rules
.SUFFIXES:
.SUFFIXES: $(SRCEXT) $(OBJEXT) $(EXEEXT)

SRC := \
    SimpleThreadExample.cpp

OBJ := \
    $(SRC:.cpp=.o)

EXE := \
    $(PROJECT)$(EXEEXT)

#define dummy targets
.PHONY: all clean compile link

all : compile link

clean :
    @echo

    @echo "Cleaning Temporary Files..."
    $(RM) $(OBJ) $(EXE)

compile : $(OBJ)

link : $(EXE)

$(OBJ) :
    @echo
    @echo "Compiling Source Files..."
    $(CXX) $(CXXFLAGS) $(OBJ) $(SRC)

$(EXE) :
    @echo
    @echo "Linking..."
    $(LD) $(OBJ) $(LDFLAGS) $(EXE)

run :
    @echo
    @$(EXE)

Building the project. (The output is from Cygwin Environment. You may need to modify the makefile to compile it on a linux environment)

$ gmake clean all

Cleaning Temporary Files...
rm -f SimpleThreadExample.o SimpleThreadExample.exe

Compiling Source Files...
g++ -o SimpleThreadExample.o SimpleThreadExample.cpp

Linking...
ld SimpleThreadExample.o -lpthread -o SimpleThreadExample.exe

Output:
Read more ...

Command prompt and setting environment variable properties

Working on multiple projects which require different compiler versions can be a daunting task especially if you are using windows command prompt cmd.exe to build the projects. You need to export the compiler specific environment variables and set the PATH variable appropriately each time you launch the command window to build each project. Here is a small tip that can help save some time

Tip
Write a batch file which will set the necessary environment variables and the path variable before launching the command window

A simple batch script which sets JAVA_HOME to jdk1.6.0_21 and launches the command prompt window

set JAVA_HOME=
set JAVA_HOME=c:\Program Files\Java\jdk1.6.0_21

set PATH=%JAVA_HOME%\bin;%PATH%
start cmd /k

On executing the batch file, command prompt window is launched with the JAVA_HOME environment variable set to the desired version (jdk1.6.0_21)

Read more ...