AVL TREE

AVL tree is a binary search tree in which the difference of heights of left and right subtrees of any node is less than or equal to one. The technique of balancing the height of binary trees was developed by Adelson, Velskii, and Landi and hence given the short form as AVL tree or Balanced Binary Tree.

·        Height of a node:

Ø  The height of an empty subtree is 0.

Ø  The height of a leaf is 1.

Ø  The height of an internal node is the maximum height of its children plus 1.

·        Balance factor:

Ø  The difference height of its LEFT subtree and its RIGHT subtree.

·        The balance factor of all nodes in AVL tree should be at most 1.

·        INSERTION

Ø  Step 1: First, insert a new element into the tree using BST's (Binary Search Tree) insertion logic.

Ø  Step 2: After inserting the elements you have to check the Balance Factor of each node.

Ø  Step 3: When the Balance Factor of every node will be found like 0 or 1 or -1 then the algorithm will proceed for the next operation.

Ø  Step 4: When the balance factor of any node comes other than the above three values then the tree is said to be imbalanced. Then perform the suitable Rotation to make it balanced and then the algorithm will proceed for the next operation.

·        DELETION

Ø  Step 1: Firstly, find that node where k is stored

Ø  Step 2: Secondly delete those contents of the node (Suppose the node is x)

Ø  Step 3: Claim: Deleting a node in an AVL tree can be reduced by deleting a leaf. There are three possible cases:

§  When x has no children then, delete x

§  When x has one child, let x' becomes the child of x.

§  Notice: x' cannot have a child, since subtrees of T can differ in height by at most one :

v  then replace the contents of x with the contents of x'

v  then delete x' (a leaf)

Ø  Step 4:  When x has two children,

§  then find x's successor z (which has no left child)

§  then replace x's contents with z's contents, and

§  delete z

Ø  In all of the three cases, you will end up removing a leaf.