fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5.     static int rotations = 0;
  6.  
  7.     static class Node {
  8.         int key;
  9.         Node left;
  10.         Node right;
  11.         int height;
  12.  
  13.         Node(int key) {
  14.             this.key = key;
  15.             this.left = null;
  16.             this.right = null;
  17.             this.height = 1;
  18.         }
  19.     }
  20.  
  21.     // Create a new node
  22.     public static Node createNode(int key) {
  23.         return new Node(key);
  24.     }
  25.  
  26.     // Return stored height
  27.     public static int height(Node node) {
  28.         if (node == null)
  29.             return 0;
  30.  
  31.         return node.height;
  32.     }
  33.  
  34.     // Calculate balance factor
  35.     public static int getBalance(Node node) {
  36.         if (node == null)
  37.             return 0;
  38.  
  39.         return height(node.left) - height(node.right);
  40.     }
  41.  
  42.     // Right Rotation
  43.     public static Node rightRotate(Node y) {
  44.  
  45.         rotations++;
  46.  
  47.         Node x = y.left;
  48.         Node T2 = x.right;
  49.  
  50.         // Rotation
  51.         x.right = y;
  52.         y.left = T2;
  53.  
  54.         // Update heights
  55.         y.height = 1 + Math.max(
  56.             height(y.left),
  57.             height(y.right)
  58.         );
  59.  
  60.         x.height = 1 + Math.max(
  61.             height(x.left),
  62.             height(x.right)
  63.         );
  64.  
  65.         return x;
  66.     }
  67.  
  68.     // Left Rotation
  69.     public static Node leftRotate(Node x) {
  70.  
  71.         rotations++;
  72.  
  73.         Node y = x.right;
  74.         Node T2 = y.left;
  75.  
  76.         // Rotation
  77.         y.left = x;
  78.         x.right = T2;
  79.  
  80.         // Update heights
  81.         x.height = 1 + Math.max(
  82.             height(x.left),
  83.             height(x.right)
  84.         );
  85.  
  86.         y.height = 1 + Math.max(
  87.             height(y.left),
  88.             height(y.right)
  89.         );
  90.  
  91.         return y;
  92.     }
  93.  
  94.     // AVL Insertion
  95.     public static Node insert(Node node, int key) {
  96.  
  97.         //  Normal BST insertion
  98.         if (node == null) {
  99.             return createNode(key);
  100.         }
  101.  
  102.         if (key < node.key) {
  103.             node.left = insert(node.left, key);
  104.         }
  105.         else if (key > node.key) {
  106.             node.right = insert(node.right, key);
  107.         }
  108.         else {
  109.             return node; // for Duplicate keys
  110.         }
  111.  
  112.         //  Update height
  113.         node.height = 1 + Math.max(
  114.             height(node.left),
  115.             height(node.right)
  116.         );
  117.  
  118.         // Calculate balance factor
  119.         int balance = getBalance(node);
  120.  
  121.         // LL Case
  122.         if (balance > 1 && key < node.left.key) {
  123.             return rightRotate(node);
  124.         }
  125.  
  126.         // RR Case
  127.         if (balance < -1 && key > node.right.key) {
  128.             return leftRotate(node);
  129.         }
  130.  
  131.         // LR Case
  132.         if (balance > 1 && key > node.left.key) {
  133.             node.left = leftRotate(node.left);
  134.             return rightRotate(node);
  135.         }
  136.  
  137.         //  RL Case
  138.         if (balance < -1 && key < node.right.key) {
  139.             node.right = rightRotate(node.right);
  140.             return leftRotate(node);
  141.         }
  142.  
  143.         return node;
  144.     }
  145.  
  146.     // Find the node with the smallest key in a subtree
  147.     public static Node minValueNode(Node node) {
  148.         Node current = node;
  149.  
  150.         while (current.left != null) {
  151.             current = current.left;
  152.         }
  153.  
  154.         return current;
  155.     }
  156.  
  157.     // AVL Deletion
  158.     public static Node deleteNode(Node root, int key) {
  159.  
  160.         // normal BST deletion
  161.         if (root == null) {
  162.             return null;
  163.         }
  164.  
  165.         if (key < root.key) {
  166.             root.left = deleteNode(root.left, key);
  167.         }
  168.         else if (key > root.key) {
  169.             root.right = deleteNode(root.right, key);
  170.         }
  171.         else {
  172.  
  173.             //Node has no child or only a right child
  174.             if (root.left == null) {
  175.                 return root.right;
  176.             }
  177.  
  178.             // Node has only a left child
  179.             else if (root.right == null) {
  180.                 return root.left;
  181.             }
  182.  
  183.             //Node has two children
  184.             Node successor = minValueNode(root.right);
  185.  
  186.             //inorder successor's key
  187.             root.key = successor.key;
  188.  
  189.             // Delete the inorder successor
  190.             root.right = deleteNode(root.right, successor.key);
  191.         }
  192.  
  193.         root.height = 1 + Math.max(
  194.             height(root.left),
  195.             height(root.right)
  196.         );
  197.  
  198.         //balance factor
  199.         int balance = getBalance(root);
  200.  
  201.         // LL Case
  202.         if (balance > 1 && getBalance(root.left) >= 0) {
  203.             return rightRotate(root);
  204.         }
  205.  
  206.         // LR Case
  207.         if (balance > 1 && getBalance(root.left) < 0) {
  208.             root.left = leftRotate(root.left);
  209.             return rightRotate(root);
  210.         }
  211.  
  212.         //  RR Case
  213.         if (balance < -1 && getBalance(root.right) <= 0) {
  214.             return leftRotate(root);
  215.         }
  216.  
  217.         // RL Case
  218.         if (balance < -1 && getBalance(root.right) > 0) {
  219.             root.right = rightRotate(root.right);
  220.             return leftRotate(root);
  221.         }
  222.  
  223.         return root;
  224.     }
  225.  
  226.  
  227.     // Inorder traversal
  228.     public static void inorder(Node root) {
  229.  
  230.         if (root == null)
  231.             return;
  232.  
  233.         inorder(root.left);
  234.  
  235.         System.out.print(
  236.             root.key + "(" + root.height + ") "
  237.         );
  238.  
  239.         inorder(root.right);
  240.     }
  241.  
  242.  
  243.     public static void main(String[] args) {
  244.  
  245.         int[] arr = {
  246.            50, 30, 70, 20, 40, 60, 80,
  247.            10, 5, 15, 25, 27, 26, 65,
  248.            62, 64, 90, 100, 95
  249.         };
  250.  
  251.         Node root = null;
  252.  
  253.     // Insert all elements
  254.         for (int key : arr) {
  255.             root = insert(root, key);
  256.         }
  257.  
  258.  
  259.         int insertionRotations = rotations;
  260.  
  261.         System.out.println("After AVL insertion:");
  262.  
  263.         System.out.print("Inorder: ");
  264.         inorder(root);
  265.         System.out.println();
  266.  
  267.         if (root != null) {
  268.             System.out.println("Root = " + root.key);
  269.         } 
  270.         else {
  271.             System.out.println("Root = null");
  272.         }
  273.  
  274.         System.out.println("Insertion rotations = " + insertionRotations);
  275.  
  276.        // Reset counter
  277.        rotations = 0;
  278.  
  279.        //Delete keys
  280.        int[] deleteKeys = {70, 20, 50, 10, 90};
  281.  
  282.        for (int key : deleteKeys) {
  283.  
  284.           root = deleteNode(root, key);
  285.  
  286.           System.out.println("\nAfter deleting " + key + ":");
  287.  
  288.           System.out.print("Inorder: ");
  289.           inorder(root);
  290.           System.out.println();
  291.  
  292.           if (root == null) {
  293.               System.out.println("Root = null");
  294.           }
  295.           else {
  296.               System.out.println("Root = " + root.key);
  297.           }  
  298.  
  299.           System.out.println("Rotations so far = " + rotations);
  300.     }
  301.  
  302.         // Final deletion rotation count
  303.         System.out.println("\nTotal deletion rotations = " + rotations);
  304. } 
  305.  
  306. }
Success #stdin #stdout 0.15s 36304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
After AVL insertion:
Inorder: 5(1) 10(2) 15(1) 20(3) 25(1) 26(2) 27(1) 30(5) 40(1) 50(2) 60(3) 62(1) 64(2) 65(1) 70(4) 80(1) 90(3) 95(1) 100(2) 
Root = 30
Insertion rotations = 13

After deleting 70:
Inorder: 5(1) 10(2) 15(1) 20(3) 25(1) 26(2) 27(1) 30(5) 40(1) 50(2) 60(3) 62(1) 64(2) 65(1) 80(4) 90(1) 95(2) 100(1) 
Root = 30
Rotations so far = 2

After deleting 20:
Inorder: 5(1) 10(2) 15(1) 25(3) 26(2) 27(1) 30(5) 40(1) 50(2) 60(3) 62(1) 64(2) 65(1) 80(4) 90(1) 95(2) 100(1) 
Root = 30
Rotations so far = 2

After deleting 50:
Inorder: 5(1) 10(2) 15(1) 25(3) 26(2) 27(1) 30(5) 40(1) 60(3) 62(1) 64(2) 65(1) 80(4) 90(1) 95(2) 100(1) 
Root = 30
Rotations so far = 2

After deleting 10:
Inorder: 5(1) 15(2) 25(3) 26(2) 27(1) 30(5) 40(1) 60(3) 62(1) 64(2) 65(1) 80(4) 90(1) 95(2) 100(1) 
Root = 30
Rotations so far = 2

After deleting 90:
Inorder: 5(1) 15(2) 25(3) 26(2) 27(1) 30(5) 40(1) 60(3) 62(1) 64(2) 65(1) 80(4) 95(2) 100(1) 
Root = 30
Rotations so far = 2

Total deletion rotations = 2
https://ideone.com/JjRfLD
language:
Java (HotSpot 12)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!