WallHero

AVLTree punto6

Nov 13th, 2020
596
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Node {
  2.     int key, height;
  3.     Node left, right;
  4.  
  5.     Node(int d) {
  6.         key = d;
  7.         height = 1;
  8.     }
  9. }
  10.  
  11. class AVLTree {
  12.  
  13.     Node root;
  14.     int height(Node N) {
  15.         if (N == null)
  16.             return 0;
  17.  
  18.         return N.height;
  19.     }
  20.  
  21.     int max(int a, int b) {
  22.         return (a > b) ? a : b;
  23.     }
  24.  
  25.     Node rightRotate(Node y) {
  26.         Node x = y.left;
  27.         Node T2 = x.right;
  28.         x.right = y;
  29.         y.left = T2;
  30.         y.height = max(height(y.left), height(y.right)) + 1;
  31.         x.height = max(height(x.left), height(x.right)) + 1;
  32.         System.out.println("Realizo rotación a la derecha.");
  33.         return x;
  34.     }
  35.  
  36.     Node leftRotate(Node x) {
  37.         Node y = x.right;
  38.         Node T2 = y.left;
  39.  
  40.         y.left = x;
  41.         x.right = T2;
  42.  
  43.         x.height = max(height(x.left), height(x.right)) + 1;
  44.         y.height = max(height(y.left), height(y.right)) + 1;
  45.         System.out.println("Realizo rotación a la izquierda.");
  46.         return y;
  47.     }
  48.  
  49.     int getBalance(Node N) {
  50.         if (N == null)
  51.             return 0;
  52.  
  53.         return height(N.left) - height(N.right);
  54.     }
  55.  
  56.     Node insert(Node node, int key) {
  57.         if (node == null)
  58.             return (new Node(key));
  59.  
  60.         if (key < node.key)
  61.             node.left = insert(node.left, key);
  62.         else if (key > node.key)
  63.             node.right = insert(node.right, key);
  64.         else return node;
  65.  
  66.         node.height = 1 + max(height(node.left),
  67.                               height(node.right));
  68.         int balance = getBalance(node);
  69.         if (balance > 1 && key < node.left.key)
  70.             return rightRotate(node);
  71.         if (balance < -1 && key > node.right.key)
  72.             return leftRotate(node);
  73.         if (balance > 1 && key > node.left.key) {
  74.             node.left = leftRotate(node.left);
  75.             return rightRotate(node);
  76.         }
  77.         if (balance < -1 && key < node.right.key) {
  78.             node.right = rightRotate(node.right);
  79.             return leftRotate(node);
  80.         }
  81.         return node;
  82.     }
  83. }
RAW Paste Data