Worst Case number of rotations for BST to AVL algorithm?
- by spacker_lechuck
I have a basic algorithm below and I know that the worst case input BST is one that has degenerated to a linked list from inserts to only one side.
How would I compute the worst case complexity in terms of number of rotations for this BST to AVL conversion algorithm?
IF tree is right heavy
{
IF tree's right subtree is left heavy
{
Perform Double Left rotation
}
ELSE
{
Perform Single Left rotation
}
}
ELSE IF tree is left heavy
{
IF tree's left subtree is right heavy
{
Perform Double Right rotation
}
ELSE
{
Perform Single Right rotation
}
}
