// Author : Saket Soni, MTech CS, 1st yr, roll - mtc0420
// Topic : Iterative implementation of Binary Search AVL tree
// Platform : Windos, VC++ 6.0
#include
#include
using namespace std;
#include
//#define DEBUG // to enable or disable dubuging
namespace AVL // AVL namespace for the whole structure
{
class AVL_Tree // class for modelling the AVL tree
{
public:
enum Balance_Factor_type { // balance factor constants
LeftHigh = 1,
Equal = 0,
RightHigh = -1
};
private:
class AVL_Node // class for modelling the AVL node
{
public:
static int mode; // for display mode
int nodeNo; // node number of the node
public:
int key; // key
Balance_Factor_type bf; // balance factor
AVL_Node *left; // pointer to left child
AVL_Node *right; // pointer to right child
AVL_Node *parent; // pointer to parent
void *ptrData;
public:
AVL_Node(int k, void * const pData, AVL_Node *aNull):key(k),bf(Equal),
nodeNo(0),left(aNull),right(aNull),parent(aNull),ptrData(pData)
{ } // default constructor
private:
AVL_Node(AVL_Node &a):key(a.key),bf(Equal),nodeNo(0),
left(NULL),right(NULL),parent(NULL),ptrData(NULL)
{ } // use of this constructor is PROHIBITED!!!
public:
friend ostream & operator<<( ostream & o, const AVL_Node *n) {
if ( mode ) { // to print the node
o << setw(3) << n->key << ":";
switch( n->bf )
{
case LeftHigh: o << " LH" << ", "; break;
case Equal: o << " EQ" << ", "; break;
case RightHigh: o << " RH" << ", "; break;
}
}
else
o << setw(3) << n->key << ":" << setw(3) << n->nodeNo << ", ";
return o;
}
private:
AVL_Node& operator = ( const AVL_Node & n ) {
key = n.key; // use of this operator is PROHIBITED!!!
if ( ptrData )
delete[] ptrData;
ptrData = n.ptrData;
return *this;
}
};
private:
AVL_Node *root; // root of the tree
private:
static AVL_Node AVL_NullNode; // AVL_NullNode
static AVL_Node *NullNode; // pointer to AVL_NullNode
private:
void preorder ( AVL_Node *r ) { // preorder traversal of the tree
if ( r != NullNode ) {
cout << r;
preorder(r->left);
preorder(r->right);
}
}
void inorder ( AVL_Node *r ) { // inorder traversal of the tree
if ( r != NullNode ) {
inorder(r->left);
cout << r;
inorder(r->right);
}
}
private:
void clear( AVL_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->right); // ptrData within the nodes
delete r;
}
}
private:
void reCalNodeNo( AVL_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->right != NullNode ) {
r->right->nodeNo = r->nodeNo * 2 + 1;
reCalNodeNo(r->right);
}
}
public:
AVL_Tree():root(NullNode) // tree constructor
{
AVL_NullNode.left = NullNode;
AVL_NullNode.right = NullNode;
AVL_NullNode.parent = NullNode;
}
public:
void show() { // prints the tree
cout << "Tree :" << endl;
cout << "preorder with balance factors ..." << endl; AVL_Node::mode = 1;
preorder(root); cout << endl;
cout << "inorder with node numbers ... " << endl; AVL_Node::mode = 0;
inorder (root); cout << endl;
}
private:
AVL_Node* search(int key, AVL_Node *& ppfather)
{ // searches for a key and returns
AVL_Node *ptr=root, *fptr=NullNode; // a pointer to it, also stores the
while ( ptr != NullNode ) { // address of the father at location
fptr = ptr; // ppfather, the function is private
if ( ptr->key < key ) // because it is to be used only with
ptr = ptr->right; // in the class
else if ( ptr->key > key )
ptr = ptr->left;
else {
ppfather = fptr;
return ptr;
}
}
ppfather = fptr;
return NullNode;
}
AVL_Node* search(int key) // same as the previous function, except
{ // it dosen't tell the address of the
AVL_Node *ptr= root; // parent of the ptr, hence you can not
while ( ptr != NullNode ) { // use this function to find the location
if ( ptr->key < key ) // where the new node is to be inserted!
ptr = ptr->right;
else if ( ptr->key > key )
ptr = ptr->left;
else
return ptr;
}
return NullNode;
}
void linkWithParent(AVL_Node *ptr, AVL_Node *optr )// links the parent of ptr with ptr, ptr
{ // must have the address of its parent and ptr
if ( ptr->parent != NullNode ) // must not be null, if parent of ptr is null,
{ // then root is set to ptr. Here 'optr' is the
if ( ptr->parent->left == optr ) { // previous child of the now parent of ptr
ptr->parent->left = ptr;
ptr->nodeNo = ptr->parent->nodeNo * 2; // if left child
}
else {
ptr->parent->right = ptr;
ptr->nodeNo = ptr->parent->nodeNo * 2 + 1; // if right child
}
}
else {
root = ptr;
ptr->nodeNo = 1;
}
}
void rotateLeft( AVL_Node *fptr ) // rotates fptr left
{
AVL_Node *ptr = fptr->right;
ptr->parent = fptr->parent;
fptr->right = ptr->left;
ptr->left = fptr;
fptr->right->parent = fptr;
fptr->parent = ptr;
linkWithParent(ptr,fptr); // to link with the parent
}
void rotateRight( AVL_Node *fptr ) // rotates fptr right
{
AVL_Node *ptr = fptr->left;
ptr->parent = fptr->parent;
fptr->left = ptr->right;
ptr->right = fptr;
fptr->left->parent = fptr;
fptr->parent = ptr;
linkWithParent(ptr,fptr); // to link with the parent
}
private:
void balanceHeightIncreased( AVL_Node* ptr )
{ // rebalances parent of ptr after insertion
AVL_Node *fptr = ptr->parent; // in subtree rooted at ptr
while ( fptr != NullNode )
{
if ( fptr->right == ptr ) // if ptr is right child
{
switch( fptr->bf )
{
case LeftHigh: // if fptr is LeftHigh
fptr->bf = Equal;
return;
case Equal: // if fptr is Equal
fptr->bf = RightHigh;
break;
case RightHigh: // if fptr is RightHigh
if ( ptr->bf == RightHigh ) {
rotateLeft(fptr); // if right child ptr is RightHigh
reCalNodeNo(ptr); // then rotate left
fptr->bf = Equal;
ptr->bf = Equal;
return;
}
else { // if right child ptr is LeftHigh
rotateRight(ptr); // then double rotate left
rotateLeft(fptr);
reCalNodeNo(ptr->parent);
if ( ptr->parent->bf == Equal ) {
ptr->bf = Equal;
fptr->bf = Equal;
}
else if ( ptr->parent->bf == LeftHigh ) {
ptr->bf = RightHigh;
fptr->bf = Equal;
}
else {
ptr->bf = Equal;
fptr->bf = LeftHigh;
}
ptr->parent->bf = Equal;
return;
}
}
}
else // else if ptr is left child
{
switch( fptr->bf )
{
case RightHigh: // if fptr is RightHigh
fptr->bf = Equal;
return;
case Equal: // if fptr is Equal
fptr->bf = LeftHigh;
break;
case LeftHigh: // if fptr is LeftHigh
if ( ptr->bf == LeftHigh ) {
rotateRight(fptr); // if left child ptr is LeftHigh
reCalNodeNo(ptr); // then rotate right
fptr->bf = Equal;
ptr->bf = Equal;
return;
}
else { // if left child ptr is RightHigh
rotateLeft(ptr); // then double rotate right
rotateRight(fptr);
reCalNodeNo(ptr->parent);
if ( ptr->parent->bf == Equal ) {
ptr->bf = Equal;
fptr->bf = Equal;
}
else if ( ptr->parent->bf == RightHigh ) {
ptr->bf = LeftHigh;
fptr->bf = Equal;
}
else {
ptr->bf = Equal;
fptr->bf = RightHigh;
}
ptr->parent->bf = Equal;
return;
}
}
}
ptr = fptr; // climb up the tree
fptr = fptr->parent;
}
}
void balanceHeightDecreased( AVL_Node *ptr)
{ // rebalances parent of ptr after deletion
AVL_Node *fptr = ptr->parent; // in subtree rooted at ptr
AVL_Node *ptrTemp;
while ( fptr != NullNode )
{
if ( fptr->right == NullNode && fptr->left == NullNode )
fptr->bf = Equal;
else if ( fptr->right == ptr ) // if ptr is right child
{
switch( fptr->bf )
{
case LeftHigh: // if fptr is LeftHigh
if ( fptr->left->bf== RightHigh ) // if left child of fptr is
{ // RightHigh, the double rotate right
ptrTemp = fptr->left->right;
rotateLeft(ptrTemp->parent);
rotateRight(fptr);
switch( ptrTemp->bf )
{
case Equal:
fptr->bf = ptrTemp->left->bf = Equal;
break;
case RightHigh:
fptr->bf = Equal;
ptrTemp->left->bf = LeftHigh;
break;
case LeftHigh:
fptr->bf = RightHigh;
ptrTemp->left->bf = Equal;
break;
}
ptrTemp->bf = Equal;
}
else { // else rotate right
ptrTemp = fptr->left;
rotateRight(fptr);
if ( ptrTemp->bf == LeftHigh ) {
fptr->bf = Equal;
ptrTemp->bf = Equal;
}
else {
ptrTemp->bf = RightHigh;
reCalNodeNo(ptrTemp);
return; // because height is unchanged
}
}
fptr = ptrTemp;
break;
case Equal: // if fptr is Equal
fptr->bf = LeftHigh;
reCalNodeNo(ptr);
return;
case RightHigh: // if fptr is RightHigh
fptr->bf = Equal;
break;
}
}
else // else if ptr is left child
{
switch( fptr->bf )
{
case RightHigh: // if fptr is RightHigh
if ( fptr->right->bf== LeftHigh ) // if right child of fptr is
{ // LeftHigh, the double rotate left
ptrTemp = fptr->right->left;
rotateRight(ptrTemp->parent);
rotateLeft(fptr);
switch( ptrTemp->bf )
{
case Equal:
fptr->bf = ptrTemp->right->bf = Equal;
break;
case LeftHigh:
fptr->bf = Equal;
ptrTemp->right->bf = RightHigh;
break;
case RightHigh:
fptr->bf = LeftHigh;
ptrTemp->right->bf = Equal;
break;
}
ptrTemp->bf = Equal;
}
else { // else rotate left
ptrTemp = fptr->right;
rotateLeft(fptr);
if ( ptrTemp->bf == RightHigh ) {
fptr->bf = Equal;
ptrTemp->bf = Equal;
}
else {
ptrTemp->bf = LeftHigh;
reCalNodeNo(ptrTemp);
return; // because height is unchanged
}
}
fptr = ptrTemp;
break;
case Equal: // if fptr is Equal
fptr->bf = RightHigh;
reCalNodeNo(ptr);
return;
case LeftHigh: // if fptr is LeftHigh
fptr->bf = Equal;
break;
}
}
ptr = fptr; // climb up the tree
fptr = fptr->parent;
}
reCalNodeNo(ptr);
}
public:
bool searchKey(int key, void *& ptrData ) // searches for a key and returns
{ // a reference to its data
AVL_Node *ptr;
if ( (ptr=search(key)) != NullNode ) { // search for 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,
AVL_Node *ptr; // a reference to old data is returned
void* ptrOldData = NULL;
if ( !ptrData ) // why replace with NULL DATA?
return NULL;
if ( (ptr=search(key)) != NullNode ) { // search for key
ptrOldData = ptr->ptrData; // return old data
ptr->ptrData = ptrData; // replace with new data
}
return ptrOldData;
}
bool insertKey(int key, void * const ptrData )
{ // returns false if key already exits
AVL_Node *ptr, *fptr;
if ( !ptrData ) // why insert NULL DATA?
return false;
if ( search(key,fptr) != NullNode ) // search for new key and find
return false; // where to insert it
ptr = new AVL_Node(key,ptrData,NullNode); // create new node
ptr->parent = fptr; // and insert as a left or
if ( fptr != NullNode ) { // right child of the father
if ( fptr->key < key ) {
fptr->right = ptr;
ptr->nodeNo = fptr->nodeNo * 2 + 1;
}
else {
fptr->left = ptr;
ptr->nodeNo = fptr->nodeNo * 2;
}
}
else { // if father is null
root = ptr; // then the new node is the root
root->nodeNo = 1;
return true;
}
balanceHeightIncreased(ptr); // rebalance height after insertion
return true;
}
bool deleteKey(int key, void *& ptrOldData)
{
AVL_Node *ptr, *tptr;
if ( (ptr = search(key)) == NullNode ) // if key dosn't exits return false
return false;
ptrOldData = ptr->ptrData;
if ( ptr->left != NullNode && ptr->right != NullNode )// if ptr has two children
{
tptr = ptr->right;
while ( tptr->left != NullNode ) // then search for its inorder successor
tptr = tptr->left;
ptr->key = tptr->key; // replace contents of ptr with that of
ptr->ptrData = tptr->ptrData; // tptr
ptr = tptr; // now node to be deleted is tptr
}
tptr = ( ptr->left != NullNode ) ? ptr->left : ptr->right;
tptr->parent = ptr->parent;
if ( ptr == root ) {
root = tptr;
root->nodeNo = 1;
reCalNodeNo(root);
}
else
{
if ( tptr->parent->left == ptr ) {
tptr->parent->left = tptr;
tptr->nodeNo = tptr->parent->nodeNo * 2;
}
else {
tptr->parent->right = tptr;
tptr->nodeNo = tptr->parent->nodeNo * 2 + 1;
}
balanceHeightDecreased(tptr);
}
delete ptr;
return true;
}
public:
~AVL_Tree() { // Tree destructor, deletes the
clear(root); // tree structure, but retains the
} // data pointed to by the tree
};
int AVL_Tree::AVL_Node::mode = 0;
AVL_Tree::AVL_Node AVL_Tree::AVL_NullNode(0,NULL,NULL);
AVL_Tree::AVL_Node* AVL_Tree::NullNode = &AVL_Tree::AVL_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()
{
AVL::AVL_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()*1000.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;
}