// Author : Saket Soni, MTech CS, 1st yr, roll - mtc0420
// Topic : Iterative implementation of Binary Search 2-3 Tree
// Platform : Windos, VC++ 6.0
#include
#include
using namespace std;
#include
//#define DEBUG // to enable or disable dubuging
namespace TREE23 // TREE23 namespace for the whole structure
{
class CTree23 // class for modelling the TREE23 tree
{
private:
class CTree23_Node // class for modelling the TREE23 node
{
public:
int nodeNo; // node number of the node
public:
int lKey; // left key
int rKey; // right key
public:
CTree23_Node *left; // pointer to left child
CTree23_Node *middle; // pointer to middle child
CTree23_Node *right; // pointer to right child
public:
CTree23_Node *parent; // pointer to parent
public:
void *ptrLData; // left data
void *ptrRData; // right data
public:
CTree23_Node(int lk, void * const pLData, int rk, void * const pRData, CTree23_Node *aNull)
:lKey(lk),rKey(rk),nodeNo(0),
left(aNull),middle(aNull),right(aNull),parent(aNull),ptrLData(pLData),ptrRData(pRData)
{ } // default constructor
private:
CTree23_Node(CTree23_Node &a)
{ } // use of this constructor is PROHIBITED!!!
public:
friend ostream & operator<<( ostream & o, const CTree23_Node *n) {
o << setw(4) << n->lKey << ":";
if ( n->ptrRData )
o << setw(4) << n->rKey << ":";
else
o << " 2N" << ":";
o << setw(3) << n->nodeNo << ", ";
return o;
}
private:
CTree23_Node& operator = ( const CTree23_Node & n )
{ } // use of = operator is PROHIBITED!!!
};
private:
CTree23_Node *root; // root of the tree
private:
static CTree23_Node Tree23_NullNode; // Tree23_NullNode
static CTree23_Node *NullNode; // pointer to Tree23_NullNode
private:
void preorder ( CTree23_Node *r ) { // preorder traversal of the tree
if ( r != NullNode ) {
cout << setw(4) << r->lKey << ":" << setw(4) << r->nodeNo << ",";
preorder(r->left);
if ( r->ptrRData )
cout << setw(4) << r->rKey << ":" << setw(4) << (r->nodeNo*2 + 1) << ",";
preorder(r->middle);
if ( r->ptrRData )
preorder(r->right);
}
}
void inorder ( CTree23_Node *r ) { // inorder traversal of the tree
if ( r != NullNode ) {
inorder(r->left);
cout << setw(4) << r->lKey << ":" << setw(4) << r->nodeNo << ",";
inorder(r->middle);
if ( r->ptrRData ) {
cout << setw(4) << r->rKey << ":" << setw(4) << (r->nodeNo*2 + 1) << ",";
inorder(r->right);
}
}
}
private:
void clear( CTree23_Node *r ) { // for deleting all the nodes in
if ( r != NullNode ) { // the tree, it does not deletes
clear(r->left); // the data pointed to by pointer
clear(r->middle); // ptrData within the nodes
clear(r->right);
delete r;
}
}
private:
void reCalNodeNo( CTree23_Node *r ) // for calculating the node numbers
{ // of the childrens of r, r must not
if ( r->left != NullNode ) { // be null
r->left->nodeNo = r->nodeNo * 2;
reCalNodeNo(r->left);
}
if ( r->middle != NullNode ) {
r->middle->nodeNo = ( r->nodeNo * 2 + 1 ) * 2;
reCalNodeNo(r->middle);
}
if ( r->right != NullNode ) {
r->right->nodeNo = ( r->nodeNo * 2 + 1 ) * 2 + 1;
reCalNodeNo(r->right);
}
}
public:
CTree23():root(NullNode) // tree constructor
{
Tree23_NullNode.left = NullNode;
Tree23_NullNode.middle = NullNode;
Tree23_NullNode.right = NullNode;
Tree23_NullNode.parent = NullNode;
}
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:
CTree23_Node* search(int key, CTree23_Node *& ppfather)
{ // searches for a key and its father
CTree23_Node *ptr=root, *fptr=NullNode;
while ( ptr != NullNode ) {
if ( ptr->ptrRData != NULL ) // if ptr is a 3-node
{
if ( ptr->lKey == key || ptr->rKey == key )
break;
fptr = ptr;
if ( ptr->lKey > key )
ptr = ptr->left;
else if ( ptr->rKey > key )
ptr = ptr->middle;
else
ptr = ptr->right;
}
else // if ptr is a 2-node
{
if ( ptr->lKey == key )
break;
fptr = ptr;
if ( ptr->lKey > key )
ptr = ptr->left;
else
ptr = ptr->middle;
}
}
ppfather = fptr;
return ptr;
}
CTree23_Node* search(int key) // searches for a key
{
CTree23_Node *ptr=root;
while ( ptr != NullNode ) {
if ( ptr->ptrRData != NULL ) // if ptr is a 3-node
{
if ( ptr->lKey == key || ptr->rKey == key )
break;
if ( ptr->lKey > key )
ptr = ptr->left;
else if ( ptr->rKey > key )
ptr = ptr->middle;
else
ptr = ptr->right;
}
else // if ptr is a 2-node
{
if ( ptr->lKey == key )
break;
if ( ptr->lKey > key )
ptr = ptr->left;
else
ptr = ptr->middle;
}
}
return ptr;
}
public:
bool searchKey(int key, void *& ptrData ) // searches for a key and returns
{ // a reference to its data
CTree23_Node *ptr;
ptr = search(key); // search for key
if ( ptr == NullNode ) // if key is not present
return false;
if ( ptr->lKey == key ) // if left key matches
ptrData = ptr->ptrLData;
else // else if right key matches
ptrData = ptr->ptrRData;
return true;
}
private:
void insertNode(CTree23_Node *ptr, CTree23_Node *fptr)// to insert a 2-node ptr into a 2-3 node fptr
{
CTree23_Node *gptr;
CTree23_Node *tptr;
while ( fptr != NullNode ) // while fptr is not NullNode
{
if ( fptr->ptrRData == NULL ) // if fptr is a 2-node
{
if ( ptr->lKey < fptr->lKey ) // if ptr is to be inserted as a left key
{
fptr->rKey = fptr->lKey;
fptr->ptrRData = fptr->ptrLData;
fptr->lKey = ptr->lKey;
fptr->ptrLData = ptr->ptrLData;
fptr->right = fptr->middle;
fptr->left = ptr->left;
fptr->middle = ptr->middle;
}
else // else if ptr is to be inserted as a right key
{
fptr->rKey = ptr->lKey;
fptr->ptrRData = ptr->ptrLData;
fptr->right = ptr->middle;
fptr->middle = ptr->left;
}
ptr->left->parent = fptr;
ptr->middle->parent = fptr;
if ( fptr->lKey == ptr->lKey )
reCalNodeNo(fptr);
else {
fptr->middle->nodeNo = ( fptr->nodeNo * 2 + 1 ) * 2;
fptr->right->nodeNo = fptr->middle->nodeNo + 1;
reCalNodeNo(fptr->right);
reCalNodeNo(fptr->middle);
}
delete ptr;
return;
}
else // if fptr is a 3-node
{
gptr = fptr->parent;
if ( ptr->lKey < fptr->lKey ) // if ptr is to be inserted as a left key
{
tptr = new CTree23_Node(fptr->rKey,fptr->ptrRData,0,NULL,NullNode);
tptr->middle = fptr->right;
tptr->left = fptr->middle;
fptr->right->parent = tptr;
fptr->middle->parent = tptr;
fptr->right = NullNode;
fptr->rKey = 0;
fptr->ptrRData = NULL;
fptr->middle = tptr;
fptr->left = ptr;
tptr->parent = fptr;
ptr->parent = fptr;
ptr = fptr;
fptr = gptr;
}
else if ( ptr->lKey < fptr->rKey ) // if ptr is to be inserted as a middle key
{
tptr = new CTree23_Node(fptr->rKey,fptr->ptrRData,0,NULL,NullNode);
tptr->middle = fptr->right;
fptr->right->parent = tptr;
tptr->left = ptr->middle;
ptr->middle->parent = tptr;
fptr->rKey = 0;
fptr->ptrRData = NULL;
fptr->right = NullNode;
fptr->middle = ptr->left;
ptr->left->parent = fptr;
ptr->left = fptr;
ptr->middle = tptr;
fptr->parent = ptr;
tptr->parent = ptr;
fptr = gptr; // climb up the tree
}
else // if ptr is to be inserted as a right key
{
tptr = new CTree23_Node(fptr->rKey,fptr->ptrRData,0,NULL,NullNode);
tptr->left = fptr;
tptr->middle = ptr;
fptr->parent = tptr;
ptr->parent = tptr;
fptr->rKey = 0;
fptr->ptrRData = NULL;
fptr->right = NullNode;
ptr = tptr;
fptr = gptr; // climb up the tree
}
}
}
root = ptr;
root->nodeNo = 1;
reCalNodeNo(root);
}
void reConfigureAfterDeletion( CTree23_Node *ptr )
{
CTree23_Node *fptr = ptr->parent;
CTree23_Node *tptr, *nptr;
while ( fptr != NullNode ) // while not top of tree
{
if ( fptr->ptrRData != NULL ) // if fptr is a 3-node
{
if ( fptr->right == ptr ) // if ptr is right child of fptr
{
tptr = fptr->middle; // middle child of fptr
if ( tptr->ptrRData == NULL ) // if tptr is a 2-node
{
tptr->rKey = fptr->rKey;
tptr->ptrRData = fptr->ptrRData;
tptr->right = fptr->right;
fptr->right->parent = tptr;
fptr->rKey = 0;
fptr->ptrRData = NULL;
fptr->right = NullNode;
reCalNodeNo(tptr);
return;
}
else // else if tptr is a 3-node
{
nptr = new CTree23_Node(fptr->rKey,fptr->ptrRData,0,NULL,NullNode);
nptr->middle = ptr;
ptr->parent = nptr;
nptr->left = tptr->right;
tptr->right->parent = nptr;
fptr->rKey = tptr->rKey;
fptr->ptrRData = tptr->ptrRData;
fptr->right = nptr;
nptr->parent = fptr;
tptr->rKey = 0;
tptr->ptrRData = NULL;
tptr->right = NullNode;
nptr->nodeNo = tptr->nodeNo + 1;
reCalNodeNo(nptr);
return;
}
}
else if ( fptr->middle == ptr ) // if ptr is the middle child
{
tptr = fptr->right; // right child of fptr
if ( tptr->ptrRData == NULL ) // if tptr is a 2-node
{
tptr->rKey = tptr->lKey;
tptr->right = tptr->middle;
tptr->middle = tptr->left;
tptr->ptrRData = tptr->ptrLData;
tptr->lKey = fptr->rKey;
tptr->ptrLData = fptr->ptrRData;
tptr->left = ptr;
ptr->parent = tptr;
fptr->middle = tptr;
tptr->parent = fptr;
fptr->right = NullNode;
fptr->rKey = 0;
fptr->ptrRData = NULL;
tptr->nodeNo = tptr->nodeNo - 1;
reCalNodeNo(tptr);
return;
}
else // else if tptr is a 3-node
{
nptr = new CTree23_Node(fptr->rKey,fptr->ptrRData,0,NULL,NullNode);
nptr->left = ptr;
ptr->parent = nptr;
fptr->middle = nptr;
nptr->parent = fptr;
fptr->rKey = tptr->lKey;
fptr->ptrRData = tptr->ptrLData;
nptr->middle = tptr->left;
nptr->middle->parent = nptr;
tptr->lKey = tptr->rKey;
tptr->ptrLData = tptr->ptrRData;
tptr->left = tptr->middle;
tptr->middle = tptr->right;
tptr->rKey = 0;
tptr->ptrRData = NULL;
tptr->right = NullNode;
nptr->nodeNo = tptr->nodeNo - 1;
reCalNodeNo(nptr);
return;
}
}
else // if ptr is the left child
{
tptr = fptr->middle; // middle child of fptr
if ( tptr->ptrRData == NULL ) // if tptr is a 2-node
{
tptr->rKey = tptr->lKey;
tptr->ptrRData = tptr->ptrLData;
tptr->right = tptr->middle;
tptr->middle = tptr->left;
tptr->lKey = fptr->lKey;
tptr->ptrLData = fptr->ptrLData;
tptr->left = ptr;
ptr->parent = tptr;
fptr->lKey = fptr->rKey;
fptr->ptrLData = fptr->ptrRData;
fptr->left = fptr->middle;
fptr->middle = fptr->right;
fptr->rKey = 0;
fptr->ptrRData = NULL;
fptr->right = NullNode;
reCalNodeNo(fptr);
return;
}
else // if tptr is a 3-node
{
nptr = new CTree23_Node(fptr->lKey,fptr->ptrLData,0,NULL,NullNode);
nptr->left = ptr;
ptr->parent = nptr;
nptr->middle = tptr->left;
nptr->middle->parent = nptr;
fptr->left = nptr;
nptr->parent = fptr;
fptr->lKey = tptr->lKey;
fptr->ptrLData = tptr->ptrLData;
tptr->lKey = tptr->rKey;
tptr->ptrLData = tptr->ptrRData;
tptr->left = tptr->middle;
tptr->middle = tptr->right;
tptr->rKey = 0;
tptr->ptrRData = NULL;
tptr->right = NullNode;
nptr->nodeNo = fptr->nodeNo * 2;
reCalNodeNo(nptr);
return;
}
}
}
else // else if fptr is a 2-node
{
if ( fptr->middle == ptr ) // if ptr is the right child of fptr
{
tptr = fptr->left; // left child of fptr
if ( tptr->ptrRData == NULL ) // if tptr is a 2-node
{
fptr->rKey = fptr->lKey;
fptr->ptrRData = fptr->ptrLData;
fptr->right = fptr->middle;
fptr->lKey = tptr->lKey;
fptr->ptrLData = tptr->ptrLData;
fptr->left = tptr->left;
fptr->left->parent = fptr;
fptr->middle = tptr->middle;
fptr->middle->parent = fptr;
delete tptr;
ptr = fptr;
fptr = ptr->parent;
}
else // if tptr is a 3-node
{
nptr = new CTree23_Node(fptr->lKey,fptr->ptrLData,0,NULL,NullNode);
nptr->middle = ptr;
ptr->parent = nptr;
nptr->left = tptr->right;
nptr->left->parent = nptr;
fptr->middle = nptr;
nptr->parent = fptr;
fptr->lKey = tptr->rKey;
fptr->ptrLData = tptr->ptrRData;
tptr->rKey = 0;
tptr->ptrRData = NULL;
tptr->right = NullNode;
nptr->nodeNo = tptr->nodeNo + 1;
reCalNodeNo(nptr);
return;
}
}
else // if ptr is the left child of fptr
{
tptr = fptr->middle; // right child of fptr
if ( tptr->ptrRData == NULL ) // if tptr is a 2-node
{
fptr->rKey = tptr->lKey;
fptr->ptrRData = tptr->ptrLData;
fptr->middle = tptr->left;
fptr->middle->parent = fptr;
fptr->right = tptr->middle;
fptr->right->parent = fptr;
delete tptr;
ptr = fptr;
fptr = ptr->parent;
}
else // if tptr is a 3-node
{
nptr = new CTree23_Node(fptr->lKey,fptr->ptrLData,0,NULL,NullNode);
nptr->left = ptr;
ptr->parent = nptr;
nptr->middle = tptr->left;
nptr->middle->parent = nptr;
fptr->left = nptr;
nptr->parent = fptr;
fptr->lKey = tptr->lKey;
fptr->ptrLData = tptr->ptrLData;
tptr->lKey = tptr->rKey;
tptr->ptrLData = tptr->ptrRData;
tptr->left = tptr->middle;
tptr->middle = tptr->right;
tptr->rKey = 0;
tptr->ptrRData = NULL;
tptr->right = NullNode;
nptr->nodeNo = fptr->nodeNo * 2;
reCalNodeNo(nptr);
return;
}
}
}
}
reCalNodeNo(root);
}
public:
void* replaceData(int key, void* const ptrData)
{ // replaces old data of a key with new data,
CTree23_Node *ptr; // a reference to old data is returned
void* ptrOldData = NULL;
if ( !ptrData ) // why replace with NULL DATA?
return NULL;
ptr = search(key); // search for key
if ( ptr == NullNode ) // if key not present
return NULL;
if ( ptr->lKey == key ) { // if left key matches
ptrOldData = ptr->ptrLData;
ptr->ptrLData = ptrData;
}
else { // else if right key matches
ptrOldData = ptr->ptrRData;
ptr->ptrRData = ptrData;
}
return ptrOldData;
}
bool insertKey(int key, void * const ptrData )
{ // returns false if key already exits
CTree23_Node *ptr, *fptr;
if ( !ptrData ) // why insert NULL DATA?
return false;
ptr = search(key,fptr); // search for the new key
if ( ptr != NullNode ) // if already exits then return false
return false;
ptr = new CTree23_Node(key,ptrData,0,NULL,NullNode); // create new node
if ( fptr == NullNode ) {
root = ptr;
ptr->nodeNo = 1;
}
else
insertNode(ptr,fptr);
return true;
}
bool deleteKey(int key, void *& ptrOldData)
{
CTree23_Node *ptr, *tptr;
ptr = search(key); // search for the key
if ( ptr == NullNode ) // if key dosen't exists return false
return false;
if ( ptr->lKey == key ) // if left key is to be deleted
{
ptrOldData = ptr->ptrLData;
if ( ptr->left != NullNode && ptr->middle != NullNode )// if left key has two childs
{
tptr = ptr->middle;
while ( tptr->left != NullNode ) // then search for its inorder successor
tptr = tptr->left;
ptr->lKey = tptr->lKey; // replace contents of ptr left key with that of
ptr->ptrLData = tptr->ptrLData; // tptr left key, now key to be deleted is tptr
ptr = tptr; // left key
key = tptr->lKey;
}
}
else // else if right key is to be deleted
{
ptrOldData = ptr->ptrRData;
if (ptr->middle != NullNode && ptr->right != NullNode)// if right key has two childs
{
tptr = ptr->right;
while ( tptr->left != NullNode ) // then search for its inorder successor
tptr = tptr->left;
ptr->rKey = tptr->lKey; // replace contents of ptr right key with that of
ptr->ptrRData = tptr->ptrLData; // tptr left key, now key to be deleted is tptr
ptr = tptr; // left key
key = tptr->lKey;
}
}
if ( ptr->ptrRData != NULL ) // if ptr is a 3-node
{
if ( ptr->lKey == key ) // and if left key is to be deleted
{
ptr->lKey = ptr->rKey;
ptr->ptrLData = ptr->ptrRData;
ptr->rKey = 0;
ptr->ptrRData = NULL;
return true;
}
else // else if right key is to be deleted
{
ptr->rKey = 0;
ptr->ptrRData = NULL;
return true;
}
} // otherwise ptr is a 2-node
reConfigureAfterDeletion(ptr); // reconfigure tree for possible height
// decrease after deletion of ptr
tptr = ptr->parent;
if ( tptr != NullNode )
{
if ( tptr->left == ptr ) // finally delete ptr
tptr->left = NullNode;
else if ( tptr->middle == ptr )
tptr->middle = NullNode;
else
tptr->right = NullNode;
}
else
root = NullNode;
delete ptr;
return true; // return successfull deletion
}
public:
~CTree23() { // Tree destructor, deletes the
clear(root); // tree structure, but retains the
} // data pointed to by the tree
};
CTree23::CTree23_Node CTree23::Tree23_NullNode(0,NULL,0,NULL,NULL);
CTree23::CTree23_Node* CTree23::NullNode = &CTree23::Tree23_NullNode;
}
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;
}
int main()
{
TREE23::CTree23 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()*100.0)/RAND_MAX; // generate random number
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) )
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;
#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;
}