1. Searching in a binary search tree is efficient if the heights of both left and right sub-trees of any node are equal.However, frequent insertions and deletions in a BST are likely to make it unbalanced.

2. The efficiency of searching is ideal if the difference between left and right sub-trees of all the nodes in a binary search tree is at the most one.This is the basic approach of AVL trees.

3. An AVL tree is a binary search tree which has the following properties:-

   a. The sub-trees of every node differ in height by at most one.

   b. Every sub-tree is an AVL tree.

   c. Each node in the AVL Tree possesses any one of the following properties:

   d. A node is called left heavy, if the largest path in its left sub tree is one level larger than the largest path of its right sub tree.

   e. A node is called right heavy, if the largest path in its right sub tree is one level larger than the largest path of its left sub tree.

   f. The node is called balanced, if the largest paths in both the right and left sub trees are equal.

4. Consider the following example of AVL tree where every left subtree has a height one greater than each right subtree.

   

5. The motivation of AVL trees was to guarantee a height of log(n) so that insertions and deletions always occur at O(log(n)).

6. A balanced factor is an integer which is associated with each node of the tree. It indicates weather a tree is left-heavy (height of left subtree is greater than that of right subtree), balanced (both subtress are of the same height), or right-heavy(opposite of left-heavy).

7. Balance factor of a node = height othe left subtree - the height of the right subtree

8. Each node of an AVL tree can have a balanced factor of -1, 0 or +1 only.

9. If the balanced factor’s magnitude exceeds 1after an operation such as insertion or deletion, then balancing is required. This is done with the help of rotations.

AVL Tree

An AVL tree (Adelson-Velskii and Landis; tree, named after the inventors) is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two-child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

The balance factor is calculated as follows:

balanceFactor = height(left subtree) - height(right subtree).

For each node checked, if the balance factor remains −1, 0, or +1 then no rotations are necessary. However, if the balance factor becomes less than -1 or greater than +1, the subtree rooted at this node is unbalanced. In other words,

An AVL tree is a binary search tree that has the following properties:

1. The sub-trees of every node differ in height by at most one.
2. Every sub-tree is an AVL tree.

Insertion

To make sure that the given tree remains AVL after every insertion, we must augment the standard BST insert operation to perform some re-balancing. Following are 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

T1, T2, and T3 are subtrees of the tree rooted with y (on left side) or x (on the right side)

Steps to follow for insertion

Let the newly inserted node be w

1) Perform standard BST insert for w.

2) Starting from w, travel up and find the first unbalanced node. Let z be the first unbalanced node, y be the child of z that comes on the path from w to z and x be the grandchild of z that comes on the path from w to z.

3) Re-balance the tree by performing appropriate rotations on the subtree rooted with z. There can be 4 possible cases that need to be handled as x, y and z can be arranged in 4 ways. Following are the possible 4 arrangements: