Page 158 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 6: Binary Search Tree and AVL Trees

*/ Notes
AvlNode * clone( AvlNode *t ) const
{
if( t == NULL )
return NULL;
else
return new AvlNode( t->element, clone( t->left ), clone( t->right ),
t->height );
}
// Avl manipulations
/**
* Return the height of node t or -1 if NULL.
*/
int height( AvlNode *t ) const
{
return t == NULL ? -1 : t->height;
}

int max( int lhs, int rhs ) const
{
return lhs > rhs ? lhs : rhs;
}

/**
* Rotate binary tree node with left child.
* For AVL trees, this is a single rotation for case 1.
* Update heights, then set new root.
*/
void rotateWithLeftChild( AvlNode * & k2 )
{
AvlNode *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max( height( k2->left ), height( k2->right ) ) + 1;
k1->height = max( height( k1->left ), k2->height ) + 1;
k2 = k1;
}

/**
* Rotate binary tree node with right child.
* For AVL trees, this is a single rotation for case 4.

LOVELY PROFESSIONAL UNIVERSITY 153