SHARE
TWEET

Untitled

a guest May 19th, 2019 55 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.ArrayList;
  2.  
  3. enum Color {
  4.     RED,
  5.     BLACK,
  6. }
  7.  
  8. class RBTree {
  9.     private class Element {
  10.         int value;
  11.         Element right, left, parent;
  12.         Color color;
  13.  
  14.         Element(int v, Color color, Element parent) {
  15.             value = v;
  16.             this.parent = parent;
  17.             right = null;
  18.             left = null;
  19.             this.color = color;
  20.         }
  21.  
  22.         public String toString() {
  23.             return (color == Color.RED ? "R" : "B") + "(" + value + ")";
  24.         }
  25.        
  26.     }
  27.  
  28.     private Element root;
  29.     private int tempLayer;
  30.  
  31.     RBTree() {
  32.         root = null;
  33.     }
  34.  
  35.     private Element parentOf(int key) {
  36.         Element current = root;
  37.  
  38.         while(current != null) {
  39.             if(current.right != null)
  40.                 if(current.right.value == key)
  41.                     return current;
  42.             if(current.left != null)
  43.                 if(current.left.value == key)
  44.                     return current;
  45.  
  46.             if(key < current.value) {
  47.                 current = current.left;
  48.             } else {
  49.                 current = current.right;
  50.             }
  51.         }
  52.         return null;
  53.     }
  54.  
  55.     private void leftRotate(Element x) {
  56.         Element y = x.right;
  57.         x.right = y.left;
  58.  
  59.         if(y.left != null) {
  60.             y.left.parent = x;
  61.         }
  62.         y.parent = x.parent;
  63.  
  64.         if(x.parent == null) {
  65.             root = y;
  66.         } else if(x == x.parent.left) {
  67.             x.parent.left = y;
  68.         } else {
  69.             x.parent.right = y;
  70.         }
  71.  
  72.         y.left = x;
  73.         x.parent = y;
  74.     }
  75.  
  76.     private void rightRotate(Element x) {
  77.         Element y = x.left;
  78.         x.left = y.right;
  79.  
  80.         if(y.right != null) {
  81.             y.right.parent = x;
  82.         }
  83.         y.parent = x.parent;
  84.  
  85.         if(x.parent == null) {
  86.             root = y;
  87.         } else if(x == x.parent.right) {
  88.             x.parent.right = y;
  89.         } else {
  90.             x.parent.left = y;
  91.         }
  92.  
  93.         y.right = x;
  94.         x.parent = y;
  95.     }
  96.  
  97.     private Element treePut(int key) {
  98.         if(root == null) {
  99.             root = new Element(key, Color.BLACK, null);
  100.             return root;
  101.         }
  102.         Element current = root;
  103.  
  104.         while(true) {
  105.             if(key < current.value) {
  106.                 if(current.left == null) {
  107.                     current.left = new Element(key, Color.RED, null);
  108.                     current = current.left;
  109.                     break;
  110.                 }
  111.                 current = current.left;
  112.             } else {
  113.                 if(current.right == null) {
  114.                     current.right = new Element(key, Color.RED, null);
  115.                     current = current.right;
  116.                     break;
  117.                 }
  118.                 current = current.right;
  119.             }
  120.         }
  121.         current.parent = parentOf(current.value);
  122.         return current;
  123.     }
  124.  
  125.     void add(int key) {
  126.        Element current = treePut(key); // standardowe dodawanie do drzewa binarnego
  127.  
  128.        // to masz od ikłilsa - obracanie tak żeby było tyle samo czarnych po 2 stronach i nie było 2
  129.        // czerwonych obok siebie
  130.        while(current != root && current.parent.color == Color.RED) {
  131.             if(current.parent == current.parent.parent.left) {
  132.                 Element y = current.parent.parent.right;
  133.                 if(y.color == Color.RED) {
  134.                     current.parent.color = Color.BLACK;
  135.                     y.color = Color.BLACK;
  136.                     current.parent.parent.color = Color.RED;
  137.                     current = current.parent.parent;
  138.                 } else {
  139.                     if(current == current.parent.right) {
  140.                         current = current.parent;
  141.                         leftRotate(current);
  142.                     }
  143.                     current.parent.color = Color.BLACK;
  144.                     current.parent.parent.color = Color.RED;
  145.                     rightRotate(current.parent.parent);
  146.                 }
  147.             }
  148.             // -------------------------------------------------------------
  149.             if(current.parent == current.parent.parent.right) {
  150.                 Element y = current.parent.parent.left;
  151.                 if(y.color == Color.RED) {
  152.                     current.parent.color = Color.BLACK;
  153.                     y.color = Color.BLACK;
  154.                     current.parent.parent.color = Color.RED;
  155.                     current = current.parent.parent;
  156.                 } else {
  157.                     if(current == current.parent.left) {
  158.                         current = current.parent;
  159.                         leftRotate(current);
  160.                     }
  161.                     current.parent.color = Color.BLACK;
  162.                     current.parent.parent.color = Color.RED;
  163.                     rightRotate(current.parent.parent);
  164.                 }
  165.             }
  166.             root.color = Color.BLACK;
  167.         }
  168.     }  
  169.  
  170.     void inorder_show() {
  171.         System.out.print("In-order: ");
  172.         inorder_show(root);
  173.         System.out.println();
  174.     }
  175.  
  176.     void preorder_show() {
  177.         System.out.print("Pre-order: ");
  178.         preorder_show(root);
  179.         System.out.println();
  180.     }
  181.  
  182.     void postorder_show() {
  183.         System.out.print("Post-order: ");
  184.         postorder_show(root);
  185.         System.out.println();
  186.     }
  187.  
  188.     private void inorder_show(Element current) {
  189.         if(current != null) {
  190.             inorder_show(current.left);
  191.  
  192.             System.out.print(current + " ");
  193.  
  194.             inorder_show(current.right);
  195.         }
  196.     }
  197.  
  198.     private void preorder_show(Element current) {
  199.         if(current != null) {
  200.             System.out.print(current + " ");
  201.  
  202.             preorder_show(current.left);
  203.             preorder_show(current.right);
  204.         }
  205.     }
  206.  
  207.     private void postorder_show(Element current) {
  208.         if(current != null) {
  209.             postorder_show(current.left);
  210.             postorder_show(current.right);
  211.  
  212.             System.out.print(current + " ");
  213.         }
  214.     }
  215.  
  216.     void rowprint() {
  217.          ArrayList<ArrayList<Element>> elements = new ArrayList<>();
  218.          rowprint(elements, root, 0);
  219.  
  220.          for(ArrayList<Element> row: elements) {
  221.              for(Element element: row) {
  222.                  System.out.print(element + " ");
  223.              }
  224.              System.out.println();
  225.          }
  226.     }
  227.  
  228.     private void rowprint(ArrayList<ArrayList<Element>> elements, Element current, int layer) {
  229.         if(current != null) {
  230.             if(elements.size() == layer) {
  231.                 elements.add(new ArrayList<>());
  232.             }
  233.             elements.get(layer).add(current);
  234.             rowprint(elements, current.left, layer+1);
  235.             rowprint(elements, current.right, layer+1);
  236.         }
  237.     }
  238.  
  239.     boolean find(int key) {
  240.         Element current = root;
  241.         System.out.print("Tree contains " + key + " ? - ");
  242.  
  243.         while(current != null) {
  244.             if(current.value == key)
  245.                 return true;
  246.  
  247.             if(key < current.value) {
  248.                 current = current.left;
  249.             } else {
  250.                 current = current.right;
  251.             }
  252.         }
  253.         return false;
  254.     }
  255.  
  256.     int nodeCount() {
  257.         return nodeCount(root);
  258.     }
  259.  
  260.     private int nodeCount(Element current) {
  261.         if(current != null) {
  262.             return 1 + nodeCount(current.left) + nodeCount(current.right);
  263.         }
  264.         return 0;
  265.     }
  266.  
  267.     int height() {
  268.         tempLayer = 0;
  269.         height(root, 0);
  270.         return tempLayer;
  271.     }
  272.  
  273.     private void height(Element current, int layer) {
  274.         if(current != null) {
  275.             height(current.left, layer + 1);
  276.             height(current.right, layer + 1);
  277.  
  278.             if (tempLayer < layer) tempLayer = layer;
  279.         }
  280.     }
  281. }
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