// Author : Saket Soni, MTech CS, 1st yr, roll - mtc0420
// Topic : Iterative implementation of Binary Search Digital tree
// Platform : Windos, VC++ 6.0
#include
#include
using namespace std;
#include
#include
//#define DEBUG // to enable or disable dubuging
namespace Digital // Digital namespace for the whole structure
{
class Digital_Tree // class for modelling the Digital tree
{
private:
class Digital_Node // class for modelling the Digital node
{
public:
int nodeNo; // node number of the node
public:
int key; // key
Digital_Node *left; // pointer to left child
Digital_Node *right; // pointer to right child
void *ptrData;
public:
Digital_Node(int k, void * const pData):key(k),
nodeNo(0),left(NULL),right(NULL),ptrData(pData)
{ } // default constructor
private:
Digital_Node(Digital_Node &a):key(a.key),nodeNo(0),
left(NULL),right(NULL),ptrData(NULL)
{ } // use of this constructor is PROHIBITED!!!
public:
friend ostream & operator<<( ostream & o, const Digital_Node *n) {
o << setw(11) << n->key << ":"; // to print the node
if ( n->left )
o << " I " << ":";
else
o << " E " << ":";
o << setw(3) << n->nodeNo << ",";
return o;
}
private:
Digital_Node& operator = ( const Digital_Node & n ) {
key = n.key; // use of this operator is PROHIBITED!!!
if ( ptrData )
delete[] ptrData;
ptrData = n.ptrData;
return *this;
}
};
private:
Digital_Node *root; // root of the tree
private:
int KeyLength;
private:
static int errno; // error number
public:
static void showErrMsg(); // shows error message
static void resetError(); // reset errno
static int getErrorNo(); // gets errno
private:
void preorder ( Digital_Node *r ) { // preorder traversal of the tree
if ( r ) {
cout << r;
preorder(r->left);
preorder(r->right);
}
}
void inorder ( Digital_Node *r ) { // inorder traversal of the tree
if ( r ) {
inorder(r->left);
cout << r;
inorder(r->right);
}
}
private:
void clear( Digital_Node *r ) { // for deleting all the nodes in
if ( r ) { // the tree, it does not deletes
clear(r->left); // the data pointed to by pointer
clear(r->right); // ptrData within the nodes
delete r;
}
}
private:
void reCalNodeNo( Digital_Node *r ) // for calculating the node numbers
{ // of the childrens of r, r must not
if ( r->left ) { // be null
r->left->nodeNo = r->nodeNo * 2;
reCalNodeNo(r->left);
}
if ( r->right ) {
r->right->nodeNo = r->nodeNo * 2 + 1;
reCalNodeNo(r->right);
}
}
public:
Digital_Tree():root(NULL) // tree constructor
{
KeyLength = sizeof(int)*8;
}
public:
void show() { // prints the tree
cout << "Tree :" << endl;
cout << "preorder traversal ..." << endl;
preorder(root); cout << endl;
cout << "inorder traversal ... " << endl;
inorder (root); cout << endl;
}
private:
bool FindBit(int k, int key) { // return the kth bit of key
return ( 1 << (KeyLength-k) ) & key ? true : false ;
}
Digital_Node* search(int key, Digital_Node *& ppfather)
{ // to find a similar key and its father
Digital_Node *ptr = root, *fptr = NULL;
if ( root == NULL )
return NULL;
while ( true ) {
if ( ptr->left == NULL ) // if ptr is an external node
break;
fptr = ptr;
if ( FindBit(ptr->key,key) )
ptr = ptr->right;
else
ptr = ptr->left;
}
ppfather = fptr;
return ptr;
}
Digital_Node* search(int key) // to just find a similar key
{
Digital_Node *ptr = root;
if ( root == NULL )
return NULL;
while ( true ) {
if ( ptr->left == NULL )
break;
if ( FindBit(ptr->key,key) )
ptr = ptr->right;
else
ptr = ptr->left;
}
return ptr;
}
public:
bool searchKey(int key, void *& ptrData ) // searches for a key and returns
{ // a reference to its data
Digital_Node *ptr;
ptr = search(key); // search for key
if ( ptr && ptr->key == key ) {
ptrData = ptr->ptrData; // return reference to data
return true;
}
return false;
}
void* replaceData(int key, void* const ptrData)
{ // replaces old data of a key with new data,
Digital_Node *ptr; // a reference to old data is returned
void* ptrOldData = NULL;
if ( !ptrData ) // why replace with NULL DATA?
return NULL;
ptr = search(key);
if ( ptr && ptr->key == key ) { // search for key
ptrOldData = ptr->ptrData; // return old data
ptr->ptrData = ptrData; // replace with new data
}
return ptrOldData;
}
private:
int FindLeastDiffBit(int k1, int k2, int &ld )
{
int andMask = ( 1 << (KeyLength - 1) );
for ( int i = 0 ; i < KeyLength ; i++ ) {
if ( (k1 & andMask) != (k2 & andMask) ) {
ld = i+1;
break;
}
andMask = (andMask >> 1)&(0x7fffffff);
}
return (k1 & andMask) ? true : false ;
}
public:
bool insertKey(int key, void * const ptrData )
{ // returns false if key already exits
Digital_Node *ptr, *fptr, *ptrIA, *fptrIA;
Digital_Node *ptr_NewInternal, *ptr_NewExternal;
int leastDiffBit, ptrZero;
unsigned int andMask;
if ( KeyLength == 32 )
andMask = 0;
else
andMask = (0xffffffff << KeyLength);
if ( andMask & key ) { // key length larger than allowed
errno = 3; // so return false
return false;
}
if ( !ptrData ) // why insert NULL DATA?
return false;
ptr_NewExternal = new Digital_Node(key,ptrData); // create node for insertion
if ( root == NULL ) { // if tree is empty insert as root
root = ptr_NewExternal;
root->nodeNo = 1;
return true;
}
ptr = search(key,fptr); // search for new key
if ( ptr->key == key ) // cannot insert dulicate key
{
delete ptr_NewExternal;
return false;
}
ptrZero = FindLeastDiffBit(ptr->key,key,leastDiffBit); // find the least bit number
// where they differ
ptr_NewInternal = new Digital_Node(leastDiffBit,NULL); // create new internal node
if ( fptr == NULL ) { // if fptr is null, then the new
root = ptr_NewInternal; // internal node has to inserted as
if ( ptrZero == 0 ) { // the root
ptr_NewInternal->left = ptr;
ptr_NewInternal->right = ptr_NewExternal;
}
else {
ptr_NewInternal->right = ptr;
ptr_NewInternal->left = ptr_NewExternal;
}
root->nodeNo = 1; // set root's node number to 1
}
else if ( leastDiffBit > fptr->key ) // if leastDiffBit is greater than
{ // father's key, then the new internal
if ( fptr->left == ptr ) { // node has to be inserted as a child
fptr->left = ptr_NewInternal; // of the fptr
ptr_NewInternal->nodeNo = fptr->nodeNo * 2;
}
else {
fptr->right = ptr_NewInternal;
ptr_NewInternal->nodeNo = fptr->nodeNo * 2 + 1;
}
if ( ptrZero == 0 ) {
ptr_NewInternal->left = ptr;
ptr_NewInternal->right = ptr_NewExternal;
}
else {
ptr_NewInternal->right = ptr;
ptr_NewInternal->left = ptr_NewExternal;
}
}
else { // else if leastDiffBit is less than the
ptrIA = root; // father's key, then the new internal
fptrIA = NULL; // node has to be inserted above the fptr
while ( true )
{
if ( ptrIA->key > leastDiffBit ) // find the pos to insert the new
break; // internal key
fptrIA = ptrIA;
if ( FindBit(ptrIA->key,key) )
ptrIA = ptrIA->right;
else
ptrIA = ptrIA->left;
}
if ( fptrIA == NULL ) { // i.e. the new internal key has to be
root = ptr_NewInternal; // inserted as the root
if ( ptrZero == 0 ) {
ptr_NewInternal->left = ptrIA;
ptr_NewInternal->right = ptr_NewExternal;
}
else {
ptr_NewInternal->right = ptrIA;
ptr_NewInternal->left = ptr_NewExternal;
}
root->nodeNo = 1;
}
else if ( fptrIA->left == ptrIA ) { // else if not as root, and as left of fptrIA
fptrIA->left = ptr_NewInternal;
ptr_NewInternal->nodeNo = fptrIA->nodeNo * 2;
}
else { // else if as right of fptrIA
fptrIA->right = ptr_NewInternal;
ptr_NewInternal->nodeNo = fptrIA->nodeNo * 2 + 1;
}
if ( ptrZero == 0 ) { // if ptrZero is 0 then insert new external key
ptr_NewInternal->left = ptrIA; // as left of new internal node
ptr_NewInternal->right = ptr_NewExternal;
}
else { // otherwise as right of new internal node
ptr_NewInternal->right = ptrIA;
ptr_NewInternal->left = ptr_NewExternal;
}
}
reCalNodeNo(ptr_NewInternal); // re-calculate node nos.
return true;
}
bool deleteKey(int key, void *& ptrOldData) // searches for a key and deletes it
{
Digital_Node *ptr, *tptr, *fptr, *gptr;
if ( root == NULL ) // if tree is empty return false
return false;
if ( root->key == key && root->left == NULL ) // if this happens then there is only
{ // one element in the tree
ptrOldData = root->ptrData;
delete root;
root = NULL;
return true;
}
fptr = root; // initialize for iteration
gptr = NULL;
if ( FindBit(root->key,key) == 0 )
ptr = root->left;
else
ptr = root->right;
while ( true ) { // find the key, its father, and its
if ( ptr->left == NULL ) // grandfather
break;
gptr = fptr;
fptr = ptr;
if ( FindBit(ptr->key,key) == 0 )
ptr = ptr->left;
else
ptr = ptr->right;
}
if ( ptr->key != key ) // if key not found return false
return false;
if ( fptr->left == ptr ) // else set tptr to brother of ptr
tptr = fptr->right;
else
tptr = fptr->left;
if ( gptr == NULL ) { // if gptr is null, then tptr becomes
root = tptr; // new root,
root->nodeNo = 1;
}
else if ( gptr->left == fptr ) { // other update gptr accordingly
gptr->left = tptr;
tptr->nodeNo = gptr->nodeNo * 2;
}
else {
gptr->right = tptr;
tptr->nodeNo = gptr->nodeNo * 2 + 1;
}
ptrOldData = ptr->ptrData;
delete ptr; // delete ptr, the external node
delete fptr; // delete fptr, the internal node
return true; // return successful
}
public:
~Digital_Tree() { // Tree destructor, deletes the
clear(root); // tree structure, but retains the
} // data pointed to by the tree
};
int Digital_Tree::errno; // error number
void Digital_Tree::showErrMsg() { // shows error message
switch( errno )
{
case 0: cout << "No Error." << endl; break;
case 1: cout << "Error : cannot insert element, element already exits!" << endl; break;
case 2: cout << "Error : cannot delete element, element does not exit!" << endl; break;
case 3: cout << "Error : cannot insert element, keylengh of key is larger than allowed!" << endl; break;
default: cout << "Error : undefined error!" << endl; break;
}
}
void Digital_Tree::resetError() { // reset errno
errno = 0;
}
int Digital_Tree::getErrorNo() { // gets errno
return errno;
}
}
int menu() // to present a menu to the user
{ // and to read his option
int option;
while ( true )
{
cout << "Menu" << endl
<< "1. Insert elements randomly" << endl
<< "2. Insert elements manualy" << endl
<< "3. Delete elements" << endl
<< "4. Show Tree" << endl
<< "5. Exit" << endl
<< "Enter option : ";
if ( cin >> option )
break;
else {
cin.clear(); // for typographical errors
while ( cin.get() != '\n' );
}
}
return option;
}
using namespace Digital;
int main()
{
Digital::Digital_Tree tree; // tree object
int dummy = 0; // dummy data
int n, k, key;
void *ptr; // pointer to dummy data
srand(time(0)); // initializing randomizer
while ( true )
{
switch( menu() ) // read from menu
{
case 1: // for random insertion
while ( true ) {
cout << "Enter number of elements to enter : ";
cin >> n;
if ( cin.fail() ) { // for typographical errors
cin.clear();
while ( cin.get() != '\n' );
}
else break;
}
cout << "Inserting ..." << endl;
for ( k = 0 ; k < n ; ) {
key = rand(); // generate random number
if ( key < RAND_MAX )
if ( tree.insertKey(key,(void*)&dummy) ) {
cout << setw(8) << key;
k++; // increment only if insert succeeds,
} // i.e. key does not already exist
}
cout << endl;
break;
case 2: // for manual insertion
cout << "Enter elements (quit input with \'x\') : " << endl;
while ( cin >> key ) {
#ifdef DEBUG
cout << "Inserting ... " << key << endl;
#endif
if ( !tree.insertKey(key,(void*)&dummy) ) {
if ( Digital_Tree::getErrorNo() == 3 ) {
cout << "Error: Cannot insert element : " << key
<< ", keylength is larger than allowed!" << endl;
Digital_Tree::resetError();
}
else
cout << "Error : Cannot insert element : " << key
<< ", element already exist!" << endl;
}
#ifdef DEBUG
tree.show();
#endif
}
cin.clear(); // for typographical errors
while ( cin.get() != '\n' );
break;
case 3: // for deletion
cout << "Enter elements (quit input with \'x\') : " << endl;
while ( cin >> key ) {
#ifdef DEBUG
cout << "Deleting ... " << key << endl;
#endif
if ( !tree.deleteKey(key,ptr) ) // if key dosen't exist show error
cout << "Error : Cannot delete element : " << key
<< ", element dosen't exist!" << endl
<< "Remember ... you can only delete external nodes." << endl;
#ifdef DEBUG
tree.show();
#endif
}
cin.clear(); // for typographical errors
while ( cin.get() != '\n' );
break;
case 4:
tree.show(); // for displaying tree
break;
case 5: // for exiting program
return 0;
default:
cout << "Incorrect Input!!" << endl; // for incorrect option
break;
}
}
return 0;
}