Basic Operations of AVL TREES Adelson Velenskii and Landis

Searching :

An AVL Tree can be searched for a key by visiting nodes starting from the root. The visited node is checked for the presence of K. If found, then the search stops otherwise if the value of K is less then the key value of the visited node, then the left subtree else the right subtree is searched. the algorithm for an AVL Tree is given below.

Algorithm searchAVL (Tree, K) {
 if (DATA (Tree) == K)
prompt "search successful"; Stop;
 if (DATA (Tree) < K)
searchAVL (leftChild (Tree), K);
 else
searchAVL (rightChild (Tree), K);
}

Inserting and deleting a node in an AVL Tree :

To make sure that the tree remains AVL after every operation, we must add the standard BST insert operation to perform some re-balancing. There two basic operations that can be performed to re-balance a BST without violating the BST property (keys(left) < key(root) < keys(right)).
1.  Left Rotation
2.  Right Rotation.

Steps to follow for insertion :

Let the newly inserted node be a
1) Perform BST insert for a.
2) Starting from a, travel up and find the first unbalanced node. Let b be the first unbalanced node, c be the child of b that comes on the path from a to b and d be the grandchild of b that comes on the path from a to b.
3) Balance the tree by performing appropriate rotations on the subtree rooted with b. There can be 4 possible cases that need to be handled as d, c and b can be arranged in 4 ways. Following are the possible 4 cases:
a) c is left child of b and d is left child of c (Left Left Case).
b) c is left child of b and d is right child of c (Left Right Case).
c) c is right child of b and d is right child of c (Right Right Case).
d) c is right child of b and d is left child of c (Right Left Case).

Steps to follow for deletion :

Let a be the node to be deleted
1) Perform BST delete for a.
2) Starting from a, travel up and find the first unbalanced node. Let b be the first unbalanced node, c be the larger height child of b, and d be the larger height child of c. Note that the definitions of d and c are different from insertion here.
3) Balance the tree by performing appropriate rotations on the subtree rooted with b. There can be 4 possible cases that need to be handled as d, c and b can be arranged in 4 ways. Following are the possible 4 cases:
a) c is left child of b and d is left child of c (Left Left Case).
b) c is left child of b and d is right child of c (Left Right Case).
c) c is right child of b and d is right child of c (Right Right Case).
d) c is right child of b and d is left child of c (Right Left Case).

Time Complexity:

Rotation operations (right and left rotate) take constant time as only a few pointers are being changed there. Height and the balance factor also takes constant time. So we can say the time complexity of AVL insert remains same as BST insert which is O(h) where h is the height of the tree. If the tree is AVL tree, the height is O(Logn) and time complexity of AVL insert is O(Logn).