With BST the problem is that it should be balanced properly so that the height of a tree with node n should be log(2)n. But since BST does not have any balancing algorithm which re-balances the tree on every insert/delete, the tree becomes unbalanced. In this case the height of the tree may go up to n (same as the number of elements n). So the worst case scenario for search is O(n) for a BST.

An AVL tree on the other hand is supposed to be balanced. Balanced means that

* Either the tree is empty

* Or for every node in a non-empty tree height(left_sub_tree) – height(right_sub_tree) newNode.key)

root.left = insertNode(root.left, newNode);

else

root.right = insertNode(root.right, newNode);

}

result = rebalanceForInsert(root);

adjustHeight(result);

}

Function rebalanceForInsert(Node)

{

h_LL = height(Node.left.left);

h_LR = height(Node.left.right);

h_R = height(Node.right);

h_RR = height(Node.right.right);

h_RL = height(Node.right.left);

h_L = height(Node.left);

if( (h_LL == h_LR) && (h_LR >= h_R) )

result = rotate_LL(Node);

else if( (h_RR == h_RL) && (h_RL >= h_L) )

result = rotate_RR(Node);

else if( (h_LR == h_LL) && (h_LL >= h_R) )

result = rotate_LR(Node);

else if( (h_RL == h_RR) && (h_RR >= h_L) )

result = rotate_RL(Node);

else result = Node;

return result;

}

Lets look at how to remove node from an AVL tree

Function Remove(key)

{

if (root==void) result = void;

else if(root.key == key)

{

result = root.data;

root = removeNode(root);

}

else

result = removeRec(root,key);

adjustHeight(root);

root = rebalanceForDel(root);

}

Function RemoveRec(node, key)

{

if(root.key > key) //remove from left subtree

{

if(root.left == void) result = void;

else if(root.left.key == key)

{

result = root.left.data;

root.left = removeNode(root.left);

}

else

{

result = removeRec(root.left, key);

adjustHeight(root.left);

root.left = rebalanceForDel(root.left);

}

}

else //remove from right subtree

{

if(root.right == void) result = void;

else if(root.right.key == key)

{

result = root.right.data;

root.right = removeNode(root.right);

}

else

{

result = removeRec(root.right, key);

adjustHeight(root.right);

root.right = rebalanceForDel(root.right);

}

return result;

}

Function removeNode(Node)

{

if(Node.left == void) result = Node.right;

else if(Node.right == void) result = Node.left;

else (child = root.left)

{

if(child.right == void)

{

Node.data = child.data;

Node.left = child.left;

}

else

Node.left = swap_and_remove_left_nbr(Node,child);

adjustHeight(Node);

result = rebalanceForDel(Node);

}

}

Function swap_and_remove_left_nbr(Parent, child)

{

if(child.right.right != void)

child.right = swap_and_remove_left_nbr(parent, child.right);

else

{

parent.data = child.right.data;

child.right = child.right.left;

}

adjustHeight(parent);

result = rebalanceForDel(parent);

}

Function rebalanceForDel(Node)

{

h_LL = height(Node.left.left);

h_LR = height(Node.left.right);

h_R = height(Node.right);

h_RR = height(Node.right.right);

h_RL = height(Node.right.left);

h_L = height(Node.left);

if( (h_LL >= h_LR) && (h_LR >= h_R) )

result = rotate_LL(Node);

else if( (h_RR >= h_RL) && (h_RL >= h_L) )

result = rotate_RR(Node);

else if( (h_LR >= h_LL) && (h_LL >= h_R) )

result = rotate_LR(Node);

else if( (h_RL >= h_RR) && (h_RR >= h_L) )

result = rotate_RL(Node);

else result = Node;

return result;

}

That is quite a lot of stuff to digest…

Happy chewing…