Velocity Reviews > C++ > question on AVL trees

# question on AVL trees

Nobody
Guest
Posts: n/a

 12-24-2004
I have the following 2 functions done:

template <class Etype>
void S_Rotate_Left(Avl_Node<Etype> * & k2)
{
Avl_Node<Etype> *k1 = (Avl_Node<Etype>*)k2->Left;
k2->Left = k1->Right;
k1->Right = k2;
k2->Height = Max(Node_Ht(k2->Left), Node_Ht(k2->Right)) + 1;
k1->Height = Max(Node_Ht(k1->Left), k2->Height) + 1;
k2 = k1;
}

template <class Etype>
void D_Rotate_Left(Avl_Node<Etype> * & k3)
{
S_Rotate_Right((Avl_Node<Etype> * &)k3->Left);
S_Rotate_Left(k3);
}

I obviously need S_Rotate_Right and D_Rotate_Right. I am told these are
"symetrical"... whatever that means, LOL.

Are the functions below correct?

template <class Etype>
void S_Rotate_Right(Avl_Node<Etype> * & k2)
{
Avl_Node<Etype>* k1 = (Avl_Node<Etype>*)k2->Right;
k2->Right = k1->Left;
k1->Left = k2;
k2->Height = Max(Node_Ht(k2->Right), Node_Ht(k2->Left)) + 1;
k1->Height = Max(Node_Ht(k1->Right), k2->Height) + 1;
k2 = k1;
}

template <class Etype>
void D_Rotate_Right(Avl_Node<Etype> * & k3)
{
S_Rotate_Left((Avl_Node<Etype> * &)k3->Right);
S_Rotate_Right(k3);
}

Thanks for the help