SHARE
TWEET

Untitled

a guest Feb 26th, 2020 82 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. import java.io.File;
  3. import java.io.FileNotFoundException;
  4. import java.util.Scanner;
  5. class Book {
  6.    int ISBN;
  7.  
  8.    public Book(int iSBN2) {
  9.        ISBN = iSBN2;
  10.    }
  11.  
  12. }
  13.  
  14. class AVLNode
  15.  
  16. {
  17.  
  18.    AVLNode left, right;
  19.  
  20.    Book book;
  21.  
  22.    int height;
  23.  
  24.    public AVLNode(Book book)
  25.  
  26.    {
  27.  
  28.        left = null;
  29.  
  30.        right = null;
  31.  
  32.        this.book = book;
  33.  
  34.        height = 0;
  35.  
  36.    }
  37.  
  38. }
  39.  
  40. class AVLTree
  41.  
  42. {
  43.  
  44.    private AVLNode root;
  45.  
  46.    public AVLTree()
  47.  
  48.    {
  49.  
  50.        root = null;
  51.  
  52.    }
  53.  
  54.    public void insert(Book book)
  55.  
  56.    {
  57.  
  58.        root = insert(book, root);
  59.  
  60.    }
  61.  
  62.    private int height(AVLNode t)
  63.  
  64.    {
  65.  
  66.        return t == null ? -1 : t.height;
  67.  
  68.    }
  69.  
  70.    private int max(int lhs, int rhs)
  71.  
  72.    {
  73.  
  74.        return lhs > rhs ? lhs : rhs;
  75.  
  76.    }
  77.  
  78.    private AVLNode insert(Book book, AVLNode top)
  79.  
  80.    {
  81.  
  82.        if (top == null)
  83.  
  84.            top = new AVLNode(book);
  85.  
  86.        else if (book.ISBN < top.book.ISBN)
  87.  
  88.        {
  89.            top.left = insert(book, top .left);
  90.  
  91.            if (height(top .left) - height(top .right) == 2) {
  92.  
  93.                System.out.print("Imbalance occurred at inserting ISBN " + book.ISBN);
  94.  
  95.                if (book.ISBN < top.left.book.ISBN) {
  96.                    System.out.println("; fixed in Left Rotation");
  97.                    top = rotateWithLeftChild(top );
  98.                }
  99.  
  100.                else {
  101.                    System.out.println("; fixed in RightLeft Rotation");
  102.                    top = doubleWithLeftChild(top);
  103.                }
  104.  
  105.            }
  106.  
  107.        }
  108.  
  109.        else if (book.ISBN > top.book.ISBN)
  110.  
  111.        {
  112.  
  113.            top.right = insert(book, top.right);
  114.  
  115.            if (height(top.right) - height(top.left) == 2) {
  116.  
  117.                System.out.print("Imbalance occurred at inserting ISBN " + book.ISBN);
  118.  
  119.                if (book.ISBN > top.right.book.ISBN) {
  120.                    System.out.println("; fixed in Right Rotation");
  121.                    top = rotateWithRightChild(top);
  122.  
  123.                } else {
  124.                    System.out.println("; fixed in LeftRight Rotation");
  125.                    top = doubleWithRightChild(top);
  126.                }
  127.  
  128.            }
  129.  
  130.        }
  131.  
  132.  
  133.        top.height = max(height(top.left), height(top.right)) + 1;
  134.  
  135.        return top;
  136.  
  137.    }
  138.  
  139.    private AVLNode rotateWithLeftChild(AVLNode k2)
  140.  
  141.    {
  142.  
  143.        AVLNode k1 = k2.left;
  144.  
  145.        k2.left = k1.right;
  146.  
  147.        k1.right = k2;
  148.  
  149.        k2.height = max(height(k2.left), height(k2.right)) + 1;
  150.  
  151.        k1.height = max(height(k1.left), k2.height) + 1;
  152.  
  153.        return k1;
  154.  
  155.    }
  156.  
  157.    private AVLNode rotateWithRightChild(AVLNode k1)
  158.  
  159.    {
  160.  
  161.        AVLNode k2 = k1.right;
  162.  
  163.        k1.right = k2.left;
  164.  
  165.        k2.left = k1;
  166.  
  167.        k1.height = max(height(k1.left), height(k1.right)) + 1;
  168.  
  169.        k2.height = max(height(k2.right), k1.height) + 1;
  170.  
  171.        return k2;
  172.  
  173.    }
  174.  
  175.    private AVLNode doubleWithLeftChild(AVLNode k3)
  176.  
  177.    {
  178.  
  179.        k3.left = rotateWithRightChild(k3.left);
  180.  
  181.        return rotateWithLeftChild(k3);
  182.  
  183.    }
  184.  
  185.    private AVLNode doubleWithRightChild(AVLNode k1)
  186.  
  187.    {
  188.  
  189.        k1.right = rotateWithLeftChild(k1.right);
  190.  
  191.        return rotateWithRightChild(k1);
  192.  
  193.    }
  194.  
  195.    public void inorder()
  196.  
  197.    {
  198.  
  199.        inorder(root);
  200.  
  201.    }
  202.  
  203.    private void inorder(AVLNode r)
  204.  
  205.    {
  206.  
  207.        if (r != null)
  208.  
  209.        {
  210.  
  211.            inorder(r.left);
  212.  
  213.            System.out.print(r.book.ISBN + " ");
  214.  
  215.            inorder(r.right);
  216.  
  217.        }
  218.  
  219.    }
  220. }
  221.  
  222. public class AVLTreeTest
  223.  
  224. {
  225.  
  226.    public static void main(String[] args) throws FileNotFoundException
  227.  
  228.    {
  229.  
  230.        Scanner in = new Scanner(new File("books.txt"));
  231.        AVLTree avlt = new AVLTree();
  232.  
  233.        while (in.hasNextLine()) {
  234.            Book book = new Book(in.nextInt());
  235.            avlt.insert(book);
  236.        }
  237.      
  238.        System.out.print("\nIn order : ");
  239.        avlt.inorder();
  240.  
  241.        in.close();
  242.  
  243.    }
  244.  
  245. }
  246.  
  247. Output
  248.  
  249. Imbalance occurred at inserting ISBN 564789; fixed in LeftRight Rotation Imbalance occurred at inserting ISBN 321590; fixed i
  250.  
  251. Books.txt data:
  252.  
  253. 123456
  254. 789456
  255. 564789
  256. 536479
  257. 321590
  258. 260640
  259. 035478
  260. 594430
  261. 979094
  262. 799830
  263. 031236
  264. 014589
  265. 239803
  266. 123659
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top