AVL (Adelson-Velskii and Landis) Trees

What is AVL Tress?

A binary tree is said to be an AVL Tree if:

• It is a binary search tree.
• For any node, the height of left subtree of node and height of right subtree of node differ by at most 1.

Minimum/Maximum number of Nodes in AVL Tree

Let the height of an AVL Tree is h and N(h) indicate the number of nodes in AVL Tree.

Minimum number of nodes with height h is: N(h) = N(h-1) + N(h-2) + 1

N(h-1) indicates the minimum number of nodes with height h-1.

N(h-2) indicates the minimum number of nodes with height h-2. 

AVL Tree Declaration

The declaration of AVL is similar to that of BST (Binary Search Tree). We include the height sldo as a part of a declaration.

public class AVLTree {

         int key, height;

         AVLTree left, right;

         AVLTree (int data) {

                key = d;

                height = 1;

         }

      

         public int findHight(AVLTree root) {

                if(root == null)

                       return -1;

                else

                       return root.height;

        }

}