| bl00dninja |
Apr 19th, 2007 4:23 AM |
avl trees
for the anointed only:
why do i have problems with rotations? i understand the question is crap, but sometimes a hero will emerge that has the time to answer the question.
here is the avl class:
:
#include <iostream>
using namespace std;
template <class T>
class avl
{
private:
struct node
{
node * left;
node * right;
T key;
int skew;
};
node * head;
node * insert(node *, T);
void inorderPrint(node *);
node * leftRotation(node *);
node * rightRotation(node *);
public:
avl();
void insert(T);
void inorderPrint();
};
template <class T>
avl<T>::avl()
{
head = NULL;
}
template <class T>
void avl<T>::insert(T val)
{
head = insert(head, val);
}
template <class T>
typename avl<T>::node * avl<T>::leftRotation(node * thead)
{
node * temp1, * temp2;
temp1 = thead->right;
temp2 = temp1->right;
temp1->left = thead;
thead->right = temp2;
return temp1;
}
template <class T>
typename avl<T>::node * avl<T>::rightRotation(node * thead)
{
node * temp1, * temp2;
temp1 = thead->left;
temp2 = temp1->left;
temp1->right = thead;
thead->left = temp2;
return temp1;
}
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;
temp->left = NULL;
temp->right = NULL;
temp->key = key;
temp->skew = 0;
return temp;
}
//if the new key is less than the one we're looking at
//we go to the left
if(key < p->key)
{
p->left = insert(p->left, key);
--(p->skew);
if(p->skew == 0) throw "";
//looker = p->left;
//if(p->skew == -2 && looker->skew == 1)
//{
// rightRotation(p);
// //throw "";
//}
//looker = p->right;
//if(p->skew == -2 && looker->skew == 1)
//{
// rightRotation(p);
// //throw "";
//}
//looker = p->left;
//if(p->skew == -2 && looker->skew == -1)
//{
// leftRotation(looker);
// rightRotation(p);
// //throw "";
//}
//looker = p->right;
//if(p->skew == -2 && looker->skew == -1)
//{
// leftRotation(looker);
// rightRotation(p);
// //throw "";
//}
}
//otherwise if it's greater than or equal to the current one
//we go to the right
else
{
p->right = insert(p->right, key);
++(p->skew);
if(p->skew == 0) throw "";
//looker = p->left;
//if(p->skew == 2 && looker->skew == 1)
//{
// leftRotation(p);
// //throw "";
//}
/*looker = p->right;
if(p->skew == 2 && looker->skew == 1)
{
leftRotation(p);
throw "";
}*/
//looker = p->left;
//if(p->skew == 2 && looker->skew == -1)
//{
// rightRotation(looker);
// leftRotation(p);
// //throw "";
//}
//looker = p->right;
//if(p->skew == 2 && looker->skew == -1)
//{
// rightRotation(looker);
// leftRotation(p);
// //throw "";
//}
}
//eventually return
return p;
}
template <class T>
void avl<T>::inorderPrint()
{
inorderPrint(head);
}
template <class T>
void avl<T>::inorderPrint(node * head)
{
//as long as we point at a valid memory address...
//we perform a preorder traversal
if(head != NULL)
{
//go to the left
//uncomment for pre-order
cout<<head->key<<" skew "<<head->skew<<endl;
inorderPrint(head->left);
//insert crap
//uncomment for in-order
//cout<<head->key<<" skew "<<head->skew<<endl;
//go to the right
inorderPrint(head->right);
//uncomment for post-order
//cout<<head->key<<" skew "<<head->skew<<endl;
}
}
the insert works fine until we hit a skew of two. any glaring errors would be appreciated. much of the code is commented out, that is on purpose. the uncommented code is a binary search tree that holds correct skew values. is the rotation code wrong? is it in the wrong place? i do not assume anyone will answer this post unless they have time. whatever i can get is awesome.
much love,
--the bl00dninja |
