Code And Fun

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;        x.right =  y.left ;        // Update heights        x.height = max(height(x.left), hei

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