#avl trees

Comprehensive Guide to AVL Tree in Data Structure Explore our comprehensive guide to AVL trees in data structures. Learn about their properties, operations, and balancing techniques for efficient data storage and retrieval.

View On WordPress

AVL Trees

public class AVLTree<T extends Comparable> {     AVLTree<T> parent;     AVLTree<T> left;     AVLTree<T> right;     T data;     int rightHeight;     int leftHeight;       public AVLTree(T data, AVLTree<T> left, AVLTree<T> right, AVLTree<T> parent)     {         this.data = data;         this.left = left;         this.right = right;         this.parent = parent;         rightHeight = -1;         leftHeight = -1;     }       /* psuedo for balancing:     check balance     if 2, unbalanced on LEFT         check balance on the left subtree         if -1, perform LEFT ROTATION on the LEFT CHILD of the unbalanced node, and then a RIGHT ROTATION on the unbalanced node         if 1, perform a RIGHT ROTATION on the UNBALANCED NODE     if -2, unbalanced on RIGHT         check balance on right subtree         if -1, perform LEFT ROTATION on the UNBALANCED NODE         if 1, perform RIGHT ROTATION on the RIGHT CHILD of the unbalanced node, and then a LEFT ROTATION on the unbalanced node     else balanced     */       public AVLTree<T> insert(T toInsert) //returns the root     {         if(this.data == null) //inserting the first node         {             data = toInsert;             return this;         }         else         {             AVLTree<T> temp = realInsert(toInsert);             if(temp != null)             {                 while(temp.parent != null)                     temp = temp.parent;                 return temp;             }             return this;         }     }       private AVLTree<T> rebalance(AVLTree<T> newNode)     {         for(AVLTree<T> pparent = newNode.parent; pparent != null; pparent = pparent.parent)         {             int balance = pparent.getBalance();             if(balance == 2)             {                 if(pparent.left.getBalance() == -1)                     pparent.left.rotateLeft(true);                 pparent.rotateRight(false);                 AVLTree<T> temp = this;                 while(temp.parent != null)                     temp = temp.parent;                 return temp;             }             else if(balance == -2)             {                 if(pparent.right.getBalance() == 1)                     pparent.right.rotateRight(true);                 pparent.rotateLeft(false);                 AVLTree<T> temp = this;                 while(temp.parent != null)                     temp = temp.parent;                 return temp;             }         }         AVLTree<T> temp = this;         while(temp.parent != null)             temp = temp.parent;         return temp;     }     private AVLTree<T> realInsert(T toInsert)     {         int value = toInsert.compareTo(data);         if(value < 0)         {             if(left == null)             {                 left = new AVLTree<T>(toInsert, null, null, this);                 leftHeight = 0;                 updateHeights(this);                 return rebalance(left);             }             return left.realInsert(toInsert);            }         else if(value > 0)         {             if(right == null)             {                 right = new AVLTree<T>(toInsert, null, null, this);                 rightHeight = 0;                 updateHeights(this);                 return rebalance(right);             }             return right.realInsert(toInsert);         }         return null; //value == 0; duplicate entry     }       /**      *      P            P      *      |            |      *      B            E      *     / \          / \      *    A   E   ->   B   F      *       / \      / \   \      *      D   F    A   D   G      *           \      *            G      */     private void rotateLeft(boolean isDouble)     {         AVLTree<T> E = this.right;         AVLTree<T> D = E.left;         this.right = D; //this == B         if(D != null)             D.parent = this;         E.parent = this.parent;         if(this.parent != null)             if(this == parent.left)                 parent.left = E;             else //this == parent.right                 parent.right = E;         E.left = this;         this.parent = E;                 if(this.right != null)             this.rightHeight = right.getHeight();         else             this.rightHeight = -1;         if(E.left != null)             E.leftHeight = E.left.getHeight();         else             E.leftHeight = -1;         for(AVLTree<T> temp = E.parent; temp != null; temp = temp.parent)         {             if(E == temp.left)                 temp.leftHeight = max(E.leftHeight, E.rightHeight) + 1;             else // D == temp.right                 temp.rightHeight = max(E.leftHeight, E.rightHeight) + 1;             E = temp;         }                 return;     }       /**      *       P            P      *       |            |      *       F            D      *      / \          / \      *     D   G   ->   B   F      *    / \          /   / \      *   B   E        A   E   G      *  /      * A                  */     private void rotateRight(boolean isDouble)     {         AVLTree<T> D = this.left;         AVLTree<T> E = D.right;         this.left = E; //this == F         if(E != null)             E.parent = this;         D.parent = this.parent;         if(this.parent != null)             if(this == parent.left)                 parent.left = D;             else //this == parent.right                 parent.right = D;         D.right = this;         this.parent = D;                 if(this.left != null)             this.leftHeight = left.getHeight();         else             this.leftHeight = -1;         if(D.right != null)             D.rightHeight = D.right.getHeight();         else             D.rightHeight = -1;                 for(AVLTree<T> temp = D.parent; temp != null; temp = temp.parent)         {             if(D == temp.left)                 temp.leftHeight = max(D.leftHeight, D.rightHeight) + 1;             else // D == temp.right                 temp.rightHeight = max(D.leftHeight, D.rightHeight) + 1;             D = temp;         }                         return;     }         private int getBalance()     {         return leftHeight - rightHeight;     }       private void updateHeights(AVLTree<T> node)     {         if(node == null)             return;         if(node.rightHeight - node.leftHeight == 0) //height has not changed             return;         if(node.parent != null)         {             if(node.parent.right == node) //this is a right child                 node.parent.rightHeight++;             else //this is a left child                 node.parent.leftHeight++;             updateHeights(node.parent);         }         return;     }     public AVLTree<T> find(T toFind)     {         if(this == null)             return null;         int value = toFind.compareTo(data);         if(value == 0)             return this;         if(left != null && value < 0) //go left             return left.find(toFind);         if(right != null /* && value > 0 */)//else go right             return right.find(toFind);         return null;     }       public void printTree()     {         String address = "0";         System.out.println(data + " - " + address);         printSubTree(left, address + "0");         printSubTree(right, address + "1");     }       private void printSubTree(AVLTree<T> root, String address)     {         if(root == null)             return;         System.out.println(root.data + " - " + address);         printSubTree(root.left, address + "0");         printSubTree(root.right, address + "1");     }     private int max(int left, int right)     {         if(left >= right)             return left;         return right;     }       public int nodeCount(AVLTree<T> node)     {         if(node == null)             return 0;         return 1 + nodeCount(node.left) + nodeCount(node.right);     }         private int getHeight()     {         if(this == null)             return -1;         int l = -1, r = -1;         if(left != null)             l = left.getHeight();         if(right != null)             r = right.getHeight();         return max(r, l) + 1;     } }