fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main
  4. {
  5.  
  6.    class CountingBST<Key extends Comparable<Key>, Value>
  7.    {
  8.  
  9.       // --------------------------------------------------------------------------
  10.       public class Node
  11.       {
  12.          Key key;
  13.          Value value;
  14.          Node left, right;
  15.          int count;
  16.  
  17.          public Node(Key key, Value value, int count)
  18.          {
  19.             this.key = key;
  20.             this.value = value;
  21.             this.left = this.right = null;
  22.             this.count = count;
  23.          }
  24.       }
  25.  
  26.       private Node root;
  27.  
  28.       // --------------------------------------------------------------------------
  29.       public void put(Key key, Value val)
  30.       {
  31.          root = put(root, key, val);
  32.       }
  33.  
  34.       // --------------------------------------------------------------------------
  35.       private Node put(Node x, Key key, Value val)
  36.       {
  37.          if (x == null)
  38.             return new Node(key, val, 1);
  39.          int cmp = key.compareTo(x.key);
  40.          if (cmp < 0)
  41.             x.left = put(x.left, key, val);
  42.          else if (cmp > 0)
  43.             x.right = put(x.right, key, val);
  44.          else if (cmp == 0)
  45.             x.value = val;
  46.          x.count = 1 + size(x.left) + size(x.right);
  47.          return x;
  48.       }
  49.  
  50.       // --------------------------------------------------------------------------
  51.       public Value get(Key key)
  52.       {
  53.          Node x = root;
  54.          while (x != null)
  55.          {
  56.             int cmp = key.compareTo(x.key);
  57.             if (cmp < 0)
  58.                x = x.left;
  59.             else if (cmp > 0)
  60.                x = x.right;
  61.             else if (cmp == 0)
  62.                return x.value;
  63.          }
  64.          return null;
  65.       }
  66.  
  67.       // --------------------------------------------------------------------------
  68.       public int size()
  69.       {
  70.          return size(root);
  71.       }
  72.  
  73.       // --------------------------------------------------------------------------
  74.       private int size(Node x)
  75.       {
  76.          if (x == null)
  77.             return 0;
  78.          return x.count;
  79.       }
  80.  
  81.       // --------------------------------------------------------------------------
  82.       public Node min()
  83.       {
  84.          return min(root);
  85.       }
  86.  
  87.       // --------------------------------------------------------------------------
  88.       private Node min(Node x)
  89.       {
  90.          if (x != null)
  91.          {
  92.             if (x.left == null)
  93.             {
  94.                return x;
  95.             }
  96.             return min(x.left);
  97.          }
  98.          return null;
  99.       }
  100.  
  101.       // --------------------------------------------------------------------------
  102.       public Node max()
  103.       {
  104.          return max(root);
  105.       }
  106.  
  107.       // --------------------------------------------------------------------------
  108.       private Node max(Node x)
  109.       {
  110.          if (x != null)
  111.          {
  112.             if (x.right == null)
  113.             {
  114.                return x;
  115.             }
  116.             return max(x.right);
  117.          }
  118.          return null;
  119.       }
  120.  
  121.       // --------------------------------------------------------------------------
  122.      /* public void deleteMin()
  123.       {
  124.          root = deleteMin(root);
  125.       }*/
  126.  
  127.       // --------------------------------------------------------------------------
  128.       private Node deleteMin(Node x)
  129.       {
  130.          if (x != null)
  131.          {
  132.             if (x.left == null)
  133.                return x.right;
  134.             x.left = deleteMin(x.left);
  135.             x.count = 1 + size(x.left) + size(x.right);
  136.             return x;
  137.          }
  138.          return null;
  139.       }
  140.  
  141.       // --------------------------------------------------------------------------
  142.       public void delete(Key key)
  143.       {
  144.          root = delete(root, key);
  145.       }
  146.  
  147.       // --------------------------------------------------------------------------
  148.       private Node delete(Node x, Key key)
  149.       {
  150.          if (x == null)
  151.             return null;
  152.          int cmp = key.compareTo(x.key);
  153.          if (cmp < 0)
  154.             x.left = delete(x.left, key);
  155.          else if (cmp > 0)
  156.             x.right = delete(x.right, key);
  157.          else
  158.          {
  159.             if (x.right == null)
  160.                return x.left;
  161.             if (x.left == null)
  162.                return x.right;
  163.             Node t = x;
  164.             x = min(t.right);
  165.             x.right = deleteMin(t.right);
  166.             x.left = t.left;
  167.          }
  168.          x.count = size(x.left) + size(x.right) + 1;
  169.          return x;
  170.       }
  171.  
  172.       // --------------------------------------------------------------------------
  173.       private void print(Node node, int level)
  174.       {
  175.          if (node != null)
  176.          {
  177.             for (int i = 0; i < level; i++)
  178.             {
  179.                System.out.print(".");
  180.             }
  181.             System.out.printf("L%d: (", level);
  182.             System.out.print(node.key);
  183.             System.out.print("->");
  184.             System.out.print(node.value);
  185.             System.out.print(")");
  186.             System.out.printf("/%d", node.count);
  187.             System.out.println();
  188.  
  189.             print(node.left, level + 1);
  190.             print(node.right, level + 1);
  191.          }
  192.       }
  193.  
  194.       // --------------------------------------------------------------------------
  195.       public void print()
  196.       {
  197.          print(root, 0);
  198.       }
  199.  
  200.       // also maxKey, minKey,
  201.  
  202.    }
  203.  
  204.    // parse text line into tokens, e.g. "put salary 120.22" to "put" "salary"
  205.    // "120.22"
  206.    public static Vector<String> parseTextToTokens(String text)
  207.    {
  208.       Vector<String> tokens = new Vector<String>();
  209.       StringTokenizer st = new StringTokenizer(text);
  210.       while (st.hasMoreTokens())
  211.       {
  212.          tokens.add(st.nextToken());
  213.       }
  214.       return tokens;
  215.    }
  216.  
  217.    // helper function: converts string to double if possible or returns null
  218.    public static Double strToDouble(String s)
  219.    {
  220.       Double x = null;
  221.       try
  222.       {
  223.          x = Double.parseDouble(s);
  224.       }
  225.       catch (NumberFormatException e)
  226.       {
  227.       }
  228.       return x;
  229.    }
  230.  
  231.    // print content of one node into human readable form
  232.    public static void printTreeNode(CountingBST<String, Double>.Node node)
  233.    {
  234.       if (node != null)
  235.       {
  236.          System.out.print("(");
  237.          System.out.print(node.key);
  238.          System.out.print("->");
  239.          System.out.print(node.value);
  240.          System.out.print(")/");
  241.          System.out.print(node.count);
  242.          System.out.println();
  243.       }
  244.       else
  245.       {
  246.          System.out.println("null");
  247.       }
  248.    }
  249.  
  250.    // main method with command line interpreter
  251.    public static void main(String[] args)
  252.    {
  253.       Main obj = new Main();
  254.  
  255.       CountingBST<String, Double> tree = obj.new CountingBST<String, Double>();
  256.  
  257.       Scanner in = new Scanner(System.in);
  258.  
  259.       for (;;)
  260.       {
  261.          String inputLine = in.nextLine();
  262.          if (inputLine.isEmpty())
  263.          {
  264.             continue;
  265.          }
  266.  
  267.          String cmd = null;
  268.          String arg1 = null;
  269.          String arg2 = null;
  270.  
  271.          {
  272.             Vector<String> inputTokens = parseTextToTokens(inputLine);
  273.             if (inputTokens.size() > 0)
  274.                cmd = inputTokens.get(0);
  275.             if (inputTokens.size() > 1)
  276.                arg1 = inputTokens.get(1);
  277.             if (inputTokens.size() > 2)
  278.                arg2 = inputTokens.get(2);
  279.          }
  280.  
  281.          if (cmd.equals("exit"))
  282.          {
  283.             break;
  284.          }
  285.          else if (cmd.equals("print"))
  286.          {
  287.             tree.print();
  288.          }
  289.          else if (cmd.equals("size"))
  290.          {
  291.             System.out.println(tree.size());
  292.          }
  293.          else if (cmd.equals("put"))
  294.          {
  295.             String key = (arg1 != null && !arg1.isEmpty()) ? arg1 : null;
  296.             Double value = (arg2 != null) ? strToDouble(arg2) : null;
  297.             if (key == null || value == null)
  298.             {
  299.                System.out.printf("*** ERROR: wrong arguments: <%s> <%s> <%s>\n", cmd, arg1, arg2);
  300.                continue;
  301.             }
  302.             tree.put(key, value);
  303.             System.out.println("Ok");
  304.          }
  305.          else if (cmd.equals("get"))
  306.          {
  307.             String key = (arg1 != null && !arg1.isEmpty()) ? arg1 : null;
  308.             if (key == null)
  309.             {
  310.                System.out.printf("*** ERROR: wrong arguments: <%s> <%d>\n", cmd, arg1);
  311.                continue;
  312.             }
  313.             Double value = tree.get(key);
  314.             System.out.println(value);
  315.          }
  316.          else if (cmd.equals("delete"))
  317.          {
  318.             String key = (arg1 != null && !arg1.isEmpty()) ? arg1 : null;
  319.             if (key == null)
  320.             {
  321.                System.out.printf("*** ERROR: wrong arguments: <%s> <%d>\n", cmd, arg1);
  322.                continue;
  323.             }
  324.             tree.delete(key);
  325.             System.out.println("Ok");
  326.          }
  327.          else if (cmd.equals("min"))
  328.          {
  329.             printTreeNode(tree.min());
  330.          }
  331.          else if (cmd.equals("max"))
  332.          {
  333.             printTreeNode(tree.max());
  334.          }
  335.  
  336.       }
  337.  
  338.       in.close();
  339.  
  340.    }
  341.  
  342. }
  343.  
Success #stdin #stdout 0.15s 321344KB
comments (?)
stdin
copy 
put S 11.11
put E 22.22
put A 33.33
put R 44.44
put H 55.55
put C 66.66
put X 77.77
put M 88.88
size
min
max
print
delete E
size
min
max
print
exit
stdout
copy 
Ok
Ok
Ok
Ok
Ok
Ok
Ok
Ok
8
(A->33.33)/2
(X->77.77)/1
L0: (S->11.11)/8
.L1: (E->22.22)/6
..L2: (A->33.33)/2
...L3: (C->66.66)/1
..L2: (R->44.44)/3
...L3: (H->55.55)/2
....L4: (M->88.88)/1
.L1: (X->77.77)/1
Ok
7
(A->33.33)/2
(X->77.77)/1
L0: (S->11.11)/7
.L1: (H->55.55)/5
..L2: (A->33.33)/2
...L3: (C->66.66)/1
..L2: (R->44.44)/2
...L3: (M->88.88)/1
.L1: (X->77.77)/1
https://ideone.com/b0xrPX
language:
Java (12.0.1)
created:
9 years ago
visibility:
secret

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!