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.


Image result for avl tree image
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;
        }
} 
Location: India

Comments

Post a Comment

Popular posts from this blog

How to Build REST API Using PHP

-
Image
Create REST API in PHP API stands for Application Programming Interface and the idea behind API is to connect different applications irrespective of their platforms to share information. Generally, API takes requests from different applications, processes it and gives back the response. What is REST API? REST stands for Representational State Transfer and it means that the request and the response should contain a representation of the information i.e., should be in a certain format. So basically, the requests must use proper HTTP methods and the response must be in a proper format like JSON or XML instead of plain text. REST API is nothing but a normal API with a set of principles. We need to follow a set of rules while creating and consuming REST API. The rules include the following : 1. Use appropriate HTTP methods while performing API calls. The following are the four primary HTTP methods which should be used to send and receive API requests.     ...
Read more

AVL Tree Rotations

-
Image
Rotations When the tree structure changes, we need to modify the tree to restore the AVL tree property. This can be done using single or double rotations. Types of Violations Let us assume the node that must be rebalanced in X. Violations might occur in four cases: Insertion into the left subtree of the left child of X. Insertion into the right subtree of the right child of X.  Insertion into the right subtree of the left child of X. Insertion into the left subtree of the right child of X. Single Rotation Left Left Rotation (LL Rotation) [Case 1]: Rotation does not have to be done at the root of a tree. In general, we start at the node inserted and travel up the tree, updating the balance information at every node on the path. public AVLTree rotateLeft (AVLTree x) {        AVLTree  y = x.right;        // Perform rotation            y.left = x;    ...
Read more

Disjoint Set (Union-Find)

-
A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of non-overlapping subsets. Union-Find Algorithm is an algorithm which performs two operations: Find: Determine which subset a particular element is in. Union: Join two subsets into a single subset.   Source code in java import java.util.*; import java.lang.*; import java.io.*; class Graph { int V, E; // V-> no. of vertices & E->no.of edges Edge edge[]; // /collection of all edges class Edge { int src, dest; }; // Creates a graph with V vertices and E edges Graph(int v,int e) { V = v; E = e; edge = new Edge[E]; for (int i=0; i<e; ++i) edge[i] = new Edge(); } // A utility function to find the subset of an element i int find(int parent[], int i) { if (parent[i] == -1) return i; return find(parent, parent[i]); } // A uti...
Read more