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.         // 1. 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; // Duplicate keys
  110.         }
  111.  
  112.         // 2. Update height
  113.         node.height = 1 + Math.max(
  114.             height(node.left),
  115.             height(node.right)
  116.         );
  117.  
  118.         // 3. Calculate balance factor
  119.         int balance = getBalance(node);
  120.  
  121.         // 4. LL Case
  122.         if (balance > 1 && key < node.left.key) {
  123.             return rightRotate(node);
  124.         }
  125.  
  126.         // 5. RR Case
  127.         if (balance < -1 && key > node.right.key) {
  128.             return leftRotate(node);
  129.         }
  130.  
  131.         // 6. LR Case
  132.         if (balance > 1 && key > node.left.key) {
  133.             node.left = leftRotate(node.left);
  134.             return rightRotate(node);
  135.         }
  136.  
  137.         // 7. RL Case
  138.         if (balance < -1 && key < node.right.key) {
  139.             node.right = rightRotate(node.right);
  140.             return leftRotate(node);
  141.         }
  142.  
  143.         // Tree is already balanced
  144.         return node;
  145.     }
  146.  
  147.     // Inorder traversal
  148.     public static void inorder(Node root) {
  149.  
  150.         if (root == null)
  151.             return;
  152.  
  153.         inorder(root.left);
  154.  
  155.         System.out.print(
  156.             root.key + "(" + root.height + ") "
  157.         );
  158.  
  159.         inorder(root.right);
  160.     }
  161.  
  162.     public static void main(String[] args) {
  163.  
  164.         int[] arr = {
  165.             50, 30, 70, 20, 40, 60, 80,
  166.             10, 5, 15, 25, 27, 26, 65,
  167.             62, 64, 90, 100, 95
  168.         };
  169.  
  170.         Node root = null;
  171.  
  172.         for (int key : arr) {
  173.             root = insert(root, key);
  174.         }
  175.  
  176.         System.out.println("Inorder traversal:");
  177.         inorder(root);
  178.  
  179.         System.out.println();
  180.  
  181.         System.out.println("Total rotations = " + rotations);
  182.  
  183.         System.out.println("Root = " + root.key);
  184.     }
  185. }
Success #stdin #stdout 0.13s 47464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Inorder traversal:
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) 
Total rotations = 13
Root = 30
https://ideone.com/hAR2U1
language:
Java (HotSpot 12)
created:
2 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!