SHARE
TWEET

Untitled

MarouaneTheViper Apr 22nd, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package Main;
  2.  
  3. import static java.lang.Math.pow;
  4.  
  5.  
  6. public class RB_Tree {
  7.     public Node root;
  8.     public static final boolean RED   = true;
  9.     public static final boolean BLACK = false;
  10.    
  11.     public boolean isRed(Node x){
  12.         if(x==null)
  13.             return false;
  14.         return x.color==RED;
  15.     }
  16.    
  17.     public int size(Node x){
  18.         if(x==null)
  19.             return 0;
  20.         return x.size;
  21.     }
  22.    
  23.     public boolean isEmpty(){
  24.         return root==null;
  25.     }
  26.    
  27.     public float generateKey(String val)
  28.     {
  29.         float key = 0;
  30.         val = val.toUpperCase();
  31.         char[] arr = val.toCharArray();
  32.         for(int i=0; i<val.length();i++)
  33.         {
  34.             System.out.println(arr[i]);
  35.             key += arr[i]/pow(10,2*i);
  36.         }
  37.         System.out.println(key);
  38.         return key;
  39.     }    
  40.    
  41.         public Node insert(Node h,int key,String val){
  42.         if(h==null)
  43.             return new Node(key,val,RED);
  44.        
  45.         int cmp= h.compareTo(key);
  46.        
  47.         if(cmp<0)
  48.             h.left=insert(h.left,key,val);
  49.         else if(cmp>0)
  50.             h.right = insert(h.right, key, val);
  51.         else
  52. <<<<<<< HEAD
  53.             h.val=val;        
  54.         return h;
  55.     }
  56.         public void delete(float key) {
  57.         if (0.0f == key) throw new IllegalArgumentException("argument to delete() is null");
  58.         if (!contains(key)) return;
  59.  
  60.         // if both children of root are black, set root to red
  61.         if (!isRed(root.left) && !isRed(root.right))
  62.             root.color = RED;
  63.  
  64.         root = delete(root, key);
  65.         if (!isEmpty()) root.color = BLACK;
  66.         // assert check();
  67.     }
  68.  
  69.     private Node delete(Node h, float key) {
  70.         if (h.compareTo(key) < 0)  {
  71.             if (!isRed(h.left) && !isRed(h.left.left))
  72.                 h = moveRedLeft(h);
  73.             h.left = delete(h.left, key);
  74.         }
  75.         else {
  76.             if (isRed(h.left))
  77.                 h = rotateRight(h);
  78.             if (h.compareTo(key) == 0 && (h.right == null))
  79.                 return null;
  80.             if (!isRed(h.right) && !isRed(h.right.left))
  81.                 h = moveRedRight(h);
  82.             if (h.compareTo(key) == 0) {
  83.                 Node x = min(h.right);
  84.                 h.key = x.key;
  85.                 h.val = x.val;
  86.                 h.right = deleteMin(h.right);
  87.             }
  88.             else h.right = delete(h.right, key);
  89.         }
  90.         return balance(h);
  91.     }
  92.    
  93.     private Node balance(Node h) {
  94.  
  95.         if (isRed(h.right))                      h = rotateLeft(h);
  96.         if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
  97.         if (isRed(h.left) && isRed(h.right))     flipColors(h);
  98.  
  99. =======
  100.             h.val=val;
  101.         if(isRed(h.right)&&!isRed(h.left)){
  102.             h=rotateLeft(h);
  103.         }
  104.         if(isRed(h.left)&&isRed(h.left.left)){
  105.             h=rotateRight(h);
  106.         }
  107.         if(isRed(h.left)&&isRed(h.right)){
  108.             flipColors(h);
  109.         }
  110. >>>>>>> parent of 256eb3e... maroooo
  111.         h.size = size(h.left) + size(h.right) + 1;
  112.        
  113.         return h;
  114.     }
  115. <<<<<<< HEAD
  116.    
  117.     private Node rotateRight(Node h) {
  118.         Node x = h.left;
  119.         h.left = x.right;
  120.         x.right = h;
  121.         x.color = x.right.color;
  122.         x.right.color = RED;
  123.         x.size = h.size;
  124.         h.size = size(h.left) + size(h.right) + 1;
  125. =======
  126.     public Node rotateLeft(Node h){
  127.         Node x=h.right;
  128.         h.right=x.left;
  129.         x.left=h;
  130.         x.color=x.left.color;
  131.         x.left.color=RED;
  132.         x.size=h.size;
  133.         h.size=size(h.left)+size(h.right)+1;
  134. >>>>>>> parent of 256eb3e... maroooo
  135.         return x;
  136.     }
  137.     public Node rotateRight(Node h){
  138.         Node x=h.left;
  139.         h.left=x.right;
  140.         x.right=h;
  141.         x.color=x.right.color;
  142.         x.right.color=RED;
  143.         x.size=h.size;
  144.         h.size=size(h.left)+size(h.right);
  145.         return x;
  146.     }
  147.     public void flipColors(Node h){
  148.         h.color=!h.color;
  149.         h.left.color=!h.left.color;
  150.         h.right.color=!h.right.color;
  151.     }
  152.    
  153.     public void insert(String val){
  154.         if(val==null){
  155.             return;
  156.         }
  157.         float key = generateKey(val);
  158.         root=insert(root,key,val);
  159.         root.color=BLACK;        
  160.     }
  161.    
  162.     public Node insert(Node h, float key, String val){
  163.         if(h==null)
  164.             return new Node(key,val,RED);
  165.        
  166.         int cmp= h.compareTo(key);
  167.        
  168.         if(cmp<0)
  169.             h.left=insert(h.left,key,val);
  170.         else if(cmp>0)
  171.             h.right = insert(h.right, key, val);
  172.         else
  173.             h.val=val;        
  174.         return h;
  175. <<<<<<< HEAD
  176.     }
  177.  public boolean isEmpty() {
  178.         return root == null;
  179.     }
  180.  public void deleteMin() {
  181.         if (isEmpty()) throw new NoSuchElementException("BST underflow");
  182.         if (!isRed(root.left) && !isRed(root.right))
  183.             root.color = RED;
  184.  
  185.         root = deleteMin(root);
  186.         if (!isEmpty()) root.color = BLACK;
  187.     }
  188.     private Node deleteMin(Node h) {
  189.         if (h.left == null)
  190.             return null;
  191.  
  192.         if (!isRed(h.left) && !isRed(h.left.left))
  193.             h = moveRedLeft(h);
  194.  
  195.         h.left = deleteMin(h.left);
  196.         return balance(h);
  197.     }
  198.     public void deleteMax() {
  199.         if (isEmpty()) throw new NoSuchElementException("BST underflow");
  200.         if (!isRed(root.left) && !isRed(root.right))
  201.             root.color = RED;
  202.  
  203.         root = deleteMax(root);
  204.         if (!isEmpty()) root.color = BLACK;
  205.        
  206.     }
  207.     private Node deleteMax(Node h) {
  208.         if (isRed(h.left))
  209.             h = rotateRight(h);
  210.  
  211.         if (h.right == null)
  212.             return null;
  213.  
  214.         if (!isRed(h.right) && !isRed(h.right.left))
  215.             h = moveRedRight(h);
  216.  
  217.         h.right = deleteMax(h.right);
  218.  
  219.         return balance(h);
  220.     }
  221.  
  222.     public float min() {
  223.         if (isEmpty()) throw new NoSuchElementException("calls min() with empty symbol table");
  224.         return min(root).key;
  225.     }
  226.     private Node min(Node x) {
  227.         if (x.left == null) return x;
  228.         else                return min(x.left);
  229.     }
  230.  
  231.     public float max() {
  232.         if (isEmpty()) throw new NoSuchElementException("calls max() with empty symbol table");
  233.         return max(root).key;
  234.     }
  235.     private Node max(Node x) {
  236.         // assert x != null;
  237.         if (x.right == null) return x;
  238.         else                 return max(x.right);
  239.     }
  240.      private int size(Node x) {
  241.         if (x == null) return 0;
  242.         return x.size;
  243.     }
  244.     public int size() {
  245.         return size(root);
  246.     }
  247.     public boolean contains(float key) {
  248.         return get(key) != null;
  249.     }
  250.      public String get(float key) {
  251.         if (0.0f == key) throw new IllegalArgumentException("argument to get() is null");
  252.         return get(root, key);
  253.     }
  254.  
  255.     private String get(Node x, float key) {
  256.         while (x != null) {
  257.             int cmp = x.compareTo(key);
  258.             if      (cmp < 0) x = x.left;
  259.             else if (cmp > 0) x = x.right;
  260.             else              return x.val;
  261.         }
  262.         return null;
  263.     }
  264. =======
  265.     }    
  266. >>>>>>> parent of 256eb3e... maroooo
  267. }
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