| bl00dninja |
May 4th, 2007 4:10 AM |
AVL delete function
i can now insert at will, i can delete also...IN SOME CASES, this is the virgin remove() function. it removes (most) nodes properly, but fails to reset skews (yeah i know i'm throwing exceptions every time we remove()). it also fails to rotate. i know the throws are preventing that. does anyone have a good idea about how to fix the skews, design problems, etc. i understand that it doesn't work. maybe any of you c++ gurus can help here as, unfortunately, nobody has during this entire process. either you guys that know don't give a crap or these posts have been viewed only by weenies. this is the last stage in the program.
here is the AVL class, i know it is huge, remove is the final function. ignore the dSkews() function. if nothing else works it will be a leapfrog conclusion to the answer. i also understand thet the case of two children is left out...we must walk before we fly.
:
#include <iostream>
using namespace std;
template <class T>
class avl
{
private:
struct node
{
node * left;
node * right;
node * parent;
T key;
int skew;
int count;
};
node * head;
node * pt;
node * insert(node *, T);
void preorderPrint(node *);
void inorderPrint(node *);
void postorderPrint(node *);
node * leftRotation(node *);
node * rightRotation(node *);
node * leftSubRotation(node *);
node * rightSubRotation(node *);
node * leftrightRotation(node *);
node * rightleftRotation(node *);
node * leftrightSubRotation(node *);
node * rightleftSubRotation(node *);
node * remove(node *, T);
void dSkews(node *);
public:
avl();
void insert(T);
void preorder();
void inorder();
void postorder();
void remove(T);
};
/////////////////////////////////////////////////////////////////
template <class T>
avl<T>::avl()
{
head = NULL;
}
/////////////////////////////////////////////////////////////////////
template <class T>
void avl<T>::insert(T val)
{
head = insert(head, val);
}
/////////////////////////////////////////////////////////////////////
template <class T>
void avl<T>::remove(T val)
{
head = remove(head, val);
}
////////////////////////////////////////////////////////////////////
template <class T>
typename avl<T>::node * avl<T>::leftRotation(node * p)
{
node * temp1, * temp2, * temp3;
temp1 = p;
temp2 = temp1->right;
head = temp2;
temp2->parent = temp2;
temp3 = temp2->left;
temp2->left = temp1;
temp1->right = temp3;
temp1->parent = temp2;
if(temp1->left != NULL && temp1->right == NULL) temp1->skew -= 3;
else if(temp1->left == NULL && temp1->right != NULL) --(temp1->skew);
else temp1->skew -= 2;
--(temp2->skew);
return temp2;
}
///////////////////////////////////////////////////////////////////
template <class T>
typename avl<T>::node * avl<T>::rightRotation(node * p)
{
node * temp1, * temp2, * temp3;
temp1 = p;
temp2 = temp1->left;
head = temp2;
temp2->parent = temp2;
temp3 = temp2->right;
temp2->right = temp1;
temp1->left = temp3;
temp1->parent = temp2;
if(temp1->right != NULL && temp1->left == NULL) temp1->skew += 3;
else if(temp1->right == NULL && temp1->left != NULL) ++(temp1->skew);
else temp1->skew += 2;
++(temp2->skew);
return temp2;
}
////////////////////////////////////////////////////////////////////
template <class T>
typename avl<T>::node * avl<T>::leftSubRotation(node * p)
{
node * temp1, * temp2, * temp3, * temp4;
temp1 = p;
temp4 = temp1->parent;
temp2 = temp1->right;
temp3 = temp2->left;
temp2->left = temp1;
temp1->right = temp3;
temp4->right = temp2;
if(temp1->left != NULL && temp1->right == NULL) temp1->skew -= 3;
else if(temp1->left == NULL && temp1->right != NULL) --(temp1->skew);
else temp1->skew -= 2;
--(temp2->skew);
return temp2;
}
///////////////////////////////////////////////////////////////////
template <class T>
typename avl<T>::node * avl<T>::rightSubRotation(node * p)
{
node * temp1, * temp2, * temp3, * temp4;
temp1 = p;
temp4 = temp1->parent;
temp2 = temp1->left;
temp3 = temp2->right;
temp2->right = temp1;
temp1->left = temp3;
temp4->left = temp2;
if(temp1->right != NULL && temp1->left == NULL) temp1->skew += 3;
else if(temp1->right == NULL && temp1->left != NULL) ++(temp1->skew);
else temp1->skew += 2;
++(temp2->skew);
return temp2;
}
///////////////////////////////////////////////////////////////////
template <class T>
typename avl<T>::node * avl<T>::leftrightRotation(node * p)
{
node * temp1, * temp2, * temp3;
temp1 = p;
temp2 = temp1->left;
temp3 = temp2->right;
head = temp3;
temp3->parent = temp3;
temp3->right = temp1;
temp3->left = temp2;
temp1->left = NULL;
temp2->right = NULL;
if(temp1->right != NULL) temp1->skew += 3;
else temp1->skew += 2;
if(temp2->left != NULL) temp2->skew -= 2;
else --(temp2->skew);
temp3->skew = temp1->skew + temp2->skew;
return temp3;
}
//////////////////////////////////////////////////////////////////
template <class T>
typename avl<T>::node * avl<T>::rightleftRotation(node * p)
{
node * temp1, * temp2, * temp3;
temp1 = p;
temp2 = temp1->right;
temp3 = temp2->left;
head = temp3;
temp3->parent = temp3;
temp3->left = temp1;
temp3->right = temp2;
temp1->right = NULL;
temp2->left = NULL;
if(temp1->left != NULL) temp1->skew -= 3;
else temp1->skew -= 2;
if(temp2->right != NULL) temp2->skew += 2;
else ++(temp2->skew);
temp3->skew = temp1->skew + temp2->skew;
return temp3;
}
///////////////////////////////////////////////////////////////////
template <class T>
typename avl<T>::node * avl<T>::leftrightSubRotation(node * p)
{
node * temp1, * temp2, * temp3, * temp4;
temp1 = p;
temp4 = temp1->parent;
temp2 = temp1->left;
temp3 = temp2->right;
if(temp4->left == temp1) temp4->left = temp3;
else temp4->right = temp3;
temp3->right = temp1;
temp3->left = temp2;
temp1->left = NULL;
temp2->right = NULL;
if(temp1->right != NULL) temp1->skew += 3;
else temp1->skew += 2;
if(temp2->left != NULL) temp2->skew -= 2;
else --(temp2->skew);
temp3->skew = temp1->skew + temp2->skew;
return temp3;
}
////////////////////////////////////////////////////////////////////
template <class T>
typename avl<T>::node * avl<T>::rightleftSubRotation(node * p)
{
node * temp1, * temp2, * temp3, * temp4;
temp1 = p;
temp4 = temp1->parent;
temp2 = temp1->right;
temp3 = temp2->left;
if(temp4->left == temp1) temp4->left = temp3;
else temp4->right = temp3;
temp3->left = temp1;
temp3->right = temp2;
temp1->right = NULL;
temp2->left = NULL;
if(temp1->left != NULL) temp1->skew -= 3;
else temp1->skew -= 2;
if(temp2->right != NULL) temp2->skew += 2;
else ++(temp2->skew);
temp3->skew = temp1->skew + temp2->skew;
return temp3;
}
////////////////////////////////////////////////////////////////////
template <class T>
typename avl<T>::node * avl<T>::insert(node * p, T key)
{
node * looker;
//when we hit a NULL (bottom of tree
if(p == NULL)
{
//make a new node and set its shit up
node * temp = new node;
if(head == NULL) temp->parent = temp;
else temp->parent = pt;
temp->left = NULL;
temp->right = NULL;
temp->key = key;
temp->skew = 0;
temp->count = 1;
return temp;
}
else if(key == p->key)
{
++(p->count);
throw "";
}
//if the new key is less than the one we're looking at
//we go to the left
else if(key < p->key)
{ pt = p;
p->left = insert(p->left, key);
--(p->skew);
if(p->skew == 0) throw "";
/////////////////////////////////////////////////////////////////
looker = p->left;
if(p->skew == -2 && looker->skew == -1 && p == head)
{
p = rightRotation(p);
throw "";
}
looker = p->left;
if(p->skew == -2 && looker->skew == -1 && p != head)
{
p = rightSubRotation(p);
throw "";
}
////////////////////////////////////////////////////////////////////
if(p->skew == -2 && looker->skew == 1 && p == head)
{
/*p->left = leftRotation(p->left);
p = rightRotation(p);*/
p = leftrightRotation(p);
throw "";
}
if(p->skew == -2 && looker->skew == 1 && p != head)
{
p = leftrightSubRotation(p);
throw "";
}
}
//otherwise if it's greater than or equal to the current one
//we go to the right
else
{
pt = p;
p->right = insert(p->right, key);
++(p->skew);
if(p->skew == 0) throw "";
/////////////////////////////////////////////////////////////
looker = p->right;
if(p->skew == 2 && looker->skew == 1 && p == head)
{
p = leftRotation(p);
throw "";
}
looker = p->right;
if(p->skew == 2 && looker->skew == 1 && p != head)
{
p = leftSubRotation(p);
throw "";
}
////////////////////////////////////////////////////////////////////
if(p->skew == 2 && looker->skew == -1 && p == head)
{
p = rightleftRotation(p);
throw "";
}
if(p->skew == 2 && looker->skew == -1 && p != head)
{
p = rightleftSubRotation(p);
throw "";
}
}
//eventually return
return p;
}
//////////////////////////////////////////////////////////////////////
template <class T>
void avl<T>::preorder()
{
preorderPrint(head);
}
///////////////////////////////////////////////////////////////
template <class T>
void avl<T>::inorder()
{
inorderPrint(head);
}
////////////////////////////////////////////////////////////////
template <class T>
void avl<T>::postorder()
{
postorderPrint(head);
}
////////////////////////////////////////////////////////////////////
template <class T>
void avl<T>::preorderPrint(node * p)
{
//as long as we point at a valid memory address...
//we perform a traversal
if(p != NULL)
{
//go to the left
//uncomment for pre-order
cout<<p->key<<"\tskew "<<p->skew<<"\tcount "<<p->count<<endl;
preorderPrint(p->left);
//insert crap
//uncomment for in-order
//cout<<p->key<<" skew "<<p->skew<<endl;
//go to the right
preorderPrint(p->right);
//uncomment for post-order
//cout<<p->key<<" skew "<<p->skew<<endl;
}
}
///////////////////////////////////////////////////////////////////
template <class T>
void avl<T>::inorderPrint(node * p)
{
//as long as we point at a valid memory address...
//we perform a traversal
if(p != NULL)
{
//go to the left
//uncomment for pre-order
//cout<<p->key<<" skew "<<p->skew<<endl;
inorderPrint(p->left);
//insert crap
//uncomment for in-order
cout<<p->key<<"\tskew "<<p->skew<<"\tcount "<<p->count<<endl;
//go to the right
inorderPrint(p->right);
//uncomment for post-order
//cout<<p->key<<" skew "<<p->skew<<endl;
}
}
/////////////////////////////////////////////////////////////////////
template <class T>
void avl<T>::postorderPrint(node * p)
{
//as long as we point at a valid memory address...
//we perform a traversal
if(p != NULL)
{
//go to the left
//uncomment for pre-order
//cout<<p->key<<" skew "<<p->skew<<endl;
postorderPrint(p->left);
//insert crap
//uncomment for in-order
//cout<<p->key<<" skew "<<p->skew<<endl;
//go to the right
postorderPrint(p->right);
//uncomment for post-order
cout<<p->key<<"\tskew "<<p->skew<<"\tcount "<<p->count<<endl;
}
}
template <class T>
typename avl<T>::node * avl<T>::remove(node * p, T val)
{
node * looker;
if(val == p->key)
{
--(p->count);
if(p->count == 0)
{
node * t1, * t2, * t3, * t4;
t1 = p;
t4 = t1->parent;
t2 = t1->left;
t3 = t1->right;
if(p->left == NULL && p->right == NULL)
{
if(t4->left == p) t4->left = NULL;
else t4->right = NULL;
delete p;
throw "";
}
else if(p->left == NULL && p->right != NULL)
{
t3->parent = t4;
if(t4->left == p) t4->left = t3;
else t4->right = t3;
delete p;
throw "";
}
else if(p->left != NULL && p->right == NULL)
{
t2->parent = t4;
if(t4->left == p) t4->left = t2;
else t4->right = t2;
delete p;
throw "";
}
}
}
//if the new key is less than the one we're looking at
//we go to the left
else if(val < p->key)
{
p->left = remove(p->left, val);
++(p->skew);
//if(p->skew == 0) throw "";
/////////////////////////////////////////////////////////////////
looker = p->left;
if(p->skew == -2 && looker->skew == -1 && p == head)
{
p = rightRotation(p);
throw "";
}
looker = p->left;
if(p->skew == -2 && looker->skew == -1 && p != head)
{
p = rightSubRotation(p);
throw "";
}
////////////////////////////////////////////////////////////////////
if(p->skew == -2 && looker->skew == 1 && p == head)
{
p = leftrightRotation(p);
throw "";
}
if(p->skew == -2 && looker->skew == 1 && p != head)
{
p = leftrightSubRotation(p);
throw "";
}
}
//otherwise if it's greater than or equal to the current one
//we go to the right
else if(val > p->key)
{
p->right = remove(p->right, val);
--(p->skew);
//if(p->skew == 0) throw "";
/////////////////////////////////////////////////////////////
looker = p->right;
if(p->skew == 2 && looker->skew == 1 && p == head)
{
p = leftRotation(p);
throw "";
}
looker = p->right;
if(p->skew == 2 && looker->skew == 1 && p != head)
{
p = leftSubRotation(p);
throw "";
}
////////////////////////////////////////////////////////////////////
if(p->skew == 2 && looker->skew == -1 && p == head)
{
p = rightleftRotation(p);
throw "";
}
if(p->skew == 2 && looker->skew == -1 && p != head)
{
p = rightleftSubRotation(p);
throw "";
}
}
else throw"\n\nnode not found.";
//eventually return
return head;
}
template <class T>
void avl<T>::dSkews(node * p)
{
node * t1 = p, * t2 = p->parent;
while(p != head)
{
if(t1->left == NULL & t1->right == NULL)
}
}
here is the code for the driver
:
#include <iostream>
#include "avl.cpp"
using namespace std;
int main()
{//begin main
bool finalQuit = false;
do{
cout<<"\n\nPick a type of tree:\n"<<endl;
cout<<"1:\tint\t2:\tlong"<<endl;
cout<<"3:\tfloat\t4:\tdouble"<<endl;
cout<<"5:\tbool\t6:\tchar"<<endl;
cout<<"7:\tquit program\n"<<endl;
int mainChoice;
cin>>mainChoice;
if (mainChoice == 1)
{//type if selection
bool quit = false;
avl<int> object;
//infinite menu loop
do //while quit == false
{//begin while
int choice;
cout<<"\n\nselect from the following:\n\n"<<endl;
cout<<"1:\tinsert\t\t\t2:\tremove"<<endl;
cout<<"3:\tprint pre-order\t\t4:\tprint in-order"<<endl;
cout<<"5:\tprint post-order\t6:\tquit"<<endl;
cin>>choice;
switch (choice)
{
case 1:
{
int in;
cout<<"\n\ninsert value:\t";
cin>>in;
try
{
object.insert(in);
}
catch(char * str){}
break;
}
case 2:
{
int in;
cout<<"\n\nremove value:\t";
cin>>in;
try
{
object.remove(in);
}
catch(char * str){}
break;
}
case 3:
{
cout<<"\n\n"<<endl;
object.preorder();
break;
}
case 4:
{
cout<<"\n\n"<<endl;
object.inorder();
break;
}
case 5:
{
cout<<"\n\n"<<endl;
object.postorder();
break;
}
case 6:
{
quit = true;
break;
}
default:
{
cout<<"invalid input"<<endl;
break;
}
}//end switch
}while(quit == false);//end while
}//endif
if (mainChoice == 2)
{//type if selection
bool quit = false;
avl<long> object;
//infinite menu loop
do //while quit == false
{//begin while
int choice;
cout<<"\n\nselect from the following:\n\n"<<endl;
cout<<"1:\tinsert\t\t\t2:\tremove"<<endl;
cout<<"3:\tprint pre-order\t\t4:\tprint in-order"<<endl;
cout<<"5:\tprint post-order\t6:\tquit"<<endl;
cin>>choice;
switch (choice)
{
case 1:
{
long in;
cout<<"\n\ninsert value:\t";
cin>>in;
try
{
object.insert(in);
}
catch(char * str){}
break;
}
case 2:
{
long in;
cout<<"\n\nremove value:\t";
cin>>in;
try
{
object.remove(in);
}
catch(char * str){}
break;
}
case 3:
{
cout<<"\n\n"<<endl;
object.preorder();
break;
}
case 4:
{
cout<<"\n\n"<<endl;
object.inorder();
break;
}
case 5:
{
cout<<"\n\n"<<endl;
object.postorder();
break;
}
case 6:
{
quit = true;
break;
}
default:
{
cout<<"invalid input"<<endl;
break;
}
}//end switch
}while(quit == false);//end while
}//endif
if (mainChoice == 3)
{//type if selection
bool quit = false;
avl<float> object;
//infinite menu loop
do //while quit == false
{//begin while
int choice;
cout<<"\n\nselect from the following:\n\n"<<endl;
cout<<"1:\tinsert\t\t\t2:\tremove"<<endl;
cout<<"3:\tprint pre-order\t\t4:\tprint in-order"<<endl;
cout<<"5:\tprint post-order\t6:\tquit"<<endl;
cin>>choice;
switch (choice)
{
case 1:
{
float in;
cout<<"\n\ninsert value:\t";
cin>>in;
try
{
object.insert(in);
}
catch(char * str){}
break;
}
case 2:
{
float in;
cout<<"\n\nremove value:\t";
cin>>in;
try
{
object.remove(in);
}
catch(char * str){}
break;
}
case 3:
{
cout<<"\n\n"<<endl;
object.preorder();
break;
}
case 4:
{
cout<<"\n\n"<<endl;
object.inorder();
break;
}
case 5:
{
cout<<"\n\n"<<endl;
object.postorder();
break;
}
case 6:
{
quit = true;
break;
}
default:
{
cout<<"invalid input"<<endl;
break;
}
}//end switch
}while(quit == false);//end while
}//endif
if (mainChoice == 4)
{//type if selection
bool quit = false;
avl<double> object;
//infinite menu loop
do //while quit == false
{//begin while
int choice;
cout<<"\n\nselect from the following:\n\n"<<endl;
cout<<"1:\tinsert\t\t\t2:\tremove"<<endl;
cout<<"3:\tprint pre-order\t\t4:\tprint in-order"<<endl;
cout<<"5:\tprint post-order\t6:\tquit"<<endl;
cin>>choice;
switch (choice)
{
case 1:
{
double in;
cout<<"\n\ninsert value:\t";
cin>>in;
try
{
object.insert(in);
}
catch(char * str){}
break;
}
case 2:
{
double in;
cout<<"\n\nremove value:\t";
cin>>in;
try
{
object.remove(in);
}
catch(char * str){}
break;
}
case 3:
{
cout<<"\n\n"<<endl;
object.preorder();
break;
}
case 4:
{
cout<<"\n\n"<<endl;
object.inorder();
break;
}
case 5:
{
cout<<"\n\n"<<endl;
object.postorder();
break;
}
case 6:
{
quit = true;
break;
}
default:
{
cout<<"invalid input"<<endl;
break;
}
}//end switch
}while(quit == false);//end while
}//endif
if (mainChoice == 5)
{//type if selection
bool quit = false;
avl<bool> object;
//infinite menu loop
do //while quit == false
{//begin while
int choice;
cout<<"\n\nselect from the following:\n\n"<<endl;
cout<<"1:\tinsert\t\t\t2:\tremove"<<endl;
cout<<"3:\tprint pre-order\t\t4:\tprint in-order"<<endl;
cout<<"5:\tprint post-order\t6:\tquit"<<endl;
cin>>choice;
switch (choice)
{
case 1:
{
bool in;
cout<<"\n\ninsert value:\t";
cin>>in;
try
{
object.insert(in);
}
catch(char * str){}
break;
}
case 2:
{
bool in;
cout<<"\n\nremove value:\t";
cin>>in;
try
{
object.remove(in);
}
catch(char * str){}
break;
}
case 3:
{
cout<<"\n\n"<<endl;
object.preorder();
break;
}
case 4:
{
cout<<"\n\n"<<endl;
object.inorder();
break;
}
case 5:
{
cout<<"\n\n"<<endl;
object.postorder();
break;
}
case 6:
{
quit = true;
break;
}
default:
{
cout<<"invalid input"<<endl;
break;
}
}//end switch
}while(quit == false);//end while
}//endif
if (mainChoice == 6)
{//type if selection
bool quit = false;
avl<char> object;
//infinite menu loop
do //while quit == false
{//begin while
int choice;
cout<<"\n\nselect from the following:\n\n"<<endl;
cout<<"1:\tinsert\t\t\t2:\tremove"<<endl;
cout<<"3:\tprint pre-order\t\t4:\tprint in-order"<<endl;
cout<<"5:\tprint post-order\t6:\tquit"<<endl;
cin>>choice;
switch (choice)
{
case 1:
{
char in;
cout<<"\n\ninsert value:\t";
cin>>in;
try
{
object.insert(in);
}
catch(char * str){}
break;
}
case 2:
{
char in;
cout<<"\n\nremove value:\t";
cin>>in;
try
{
object.remove(in);
}
catch(char * str){}
break;
}
case 3:
{
cout<<"\n\n"<<endl;
object.preorder();
break;
}
case 4:
{
cout<<"\n\n"<<endl;
object.inorder();
break;
}
case 5:
{
cout<<"\n\n"<<endl;
object.postorder();
break;
}
case 6:
{
quit = true;
break;
}
default:
{
cout<<"invalid input"<<endl;
break;
}
}//end switch
}while(quit == false);//end while
}//endif
else if (mainChoice == 7) finalQuit = true;
else cout<<"invalid parameter"<<endl;
}while(finalQuit == false);//end main while
cin.get();
return 0;
}//end main
this whole post is prophylactic (spelling??) i might get it tomorrow, but in the case that i do not, i am submitting it to you.
--ben |
