fork download
copy 
  1. import java.util.Random;
  2.  
  3. public class Main {
  4.     public static void main(final String[] args) {
  5.         Tree t = Tree.leaf;
  6.  
  7.         for (final int i : sfl(seq(32), new java.util.Random()))
  8.             t = t.add(i);
  9.  
  10.         t.dump();
  11.     }
  12.  
  13.     public static int[] seq(final int c) {
  14.         final int[] a = new int[c];
  15.         for (int i = 0; i < c; i++)
  16.             a[i] = i;
  17.         return a;
  18.     }
  19.  
  20.     public static int[] sfl(final int[] a, final Random r) {
  21.         for (int i = a.length; i > 0; i--)
  22.             swap(a, i - 1, r.nextInt(i));
  23.         return a;
  24.     }
  25.  
  26.     public static void swap(final int[] a, final int i, final int j) {
  27.         final int t = a[i];
  28.         a[i] = a[j];
  29.         a[j] = t;
  30.     }
  31. }
  32.  
  33. abstract class Tree {
  34.     public static final Leaf leaf = Leaf.instance;
  35.  
  36.     public abstract Tree add(int v);
  37.     public abstract Tree del(int v);
  38.     public abstract void dump();
  39.     protected abstract Result add_(int v);
  40.     protected abstract Result del_(int v);
  41.     protected abstract Tree getLeft();
  42.     protected abstract Tree getRight();
  43.     protected abstract int getValue();
  44.     protected abstract int getHeight();
  45.     protected abstract void dump_(String s);
  46. }
  47.  
  48. class Leaf extends Tree {
  49.     public static final Leaf instance = new Leaf();
  50.  
  51.     private Leaf() {
  52.  
  53.     }
  54.  
  55.     @Override
  56.     public Tree add(final int v) {
  57.         return add_(v).node;
  58.     }
  59.  
  60.     @Override
  61.     protected Result add_(final int v) {
  62.         return new Result(false, new Node(v, 1, this, this));
  63.     }
  64.  
  65.     @Override
  66.     public Tree del(final int v) {
  67.         return del_(v).node;
  68.     }
  69.  
  70.     @Override
  71.     protected Result del_(final int v) {
  72.         throw new RuntimeException("not found");
  73.     }
  74.  
  75.     @Override
  76.     protected Tree getLeft() {
  77.         throw new RuntimeException("not implement");
  78.     }
  79.  
  80.     @Override
  81.     protected Tree getRight() {
  82.         throw new RuntimeException("not implement");
  83.     }
  84.  
  85.     @Override
  86.     protected int getValue() {
  87.         throw new RuntimeException("not implement");
  88.     }
  89.  
  90.     @Override
  91.     protected int getHeight() {
  92.         return 0;
  93.     }
  94.  
  95.     @Override
  96.     public void dump() {
  97.         dump_("");
  98.     }
  99.  
  100.     @Override
  101.     protected void dump_(final String s) {
  102.     }
  103. }
  104.  
  105. class Result {
  106.     final boolean balanced;
  107.     final Tree node;
  108.  
  109.     public Result(final boolean b, final Tree n) {
  110.         balanced = b;
  111.         node = n;
  112.     }
  113. }
  114.  
  115. class Node extends Tree {
  116.     final int value;
  117.     final int height;
  118.     final Tree left;
  119.     final Tree right;
  120.  
  121.     public Node(final int v, final int h, final Tree l, final Tree r) {
  122.         value = v;
  123.         height = h;
  124.         left = l;
  125.         right = r;
  126.     }
  127.  
  128.     @Override
  129.     protected Tree getLeft() {
  130.         return left;
  131.     }
  132.  
  133.     @Override
  134.     protected Tree getRight() {
  135.         return right;
  136.     }
  137.  
  138.     @Override
  139.     protected int getValue() {
  140.         return value;
  141.     }
  142.  
  143.     @Override
  144.     protected int getHeight() {
  145.         return height;
  146.     }
  147.  
  148.     @Override
  149.     public Tree add(final int v) {
  150.         return add_(v).node;
  151.     }
  152.  
  153.     @Override
  154.     protected Result add_(final int v) {
  155.         if (v < value)
  156.             return addFixL(left.add_(v));
  157.         else if (v > value)
  158.             return addFixR(right.add_(v));
  159.         else
  160.             throw new RuntimeException("not implement");
  161.     }
  162.  
  163.     @Override
  164.     public Tree del(final int v) {
  165.         return del_(v).node;
  166.     }
  167.  
  168.     @Override
  169.     protected Result del_(final int v) {
  170.         if (value == v) {
  171.             if (left == Leaf.instance)
  172.                 return new Result(false, right);
  173.             else if (right == Leaf.instance)
  174.                 return new Result(false, left);
  175.             else
  176.                 return (new Node(((Node) right).minValue(), height, left, right)).delFixR(((Node) right).delMin());
  177.         } else if (v < value)
  178.             return delFixL(left.del_(v));
  179.         else
  180.             return delFixR(right.del_(v));
  181.     }
  182.  
  183.     private int minValue() {
  184.         if (left == Leaf.instance)
  185.             return value;
  186.         else
  187.             return ((Node) left).minValue();
  188.     }
  189.  
  190.     private Result delMin() {
  191.         if (left == Leaf.instance)
  192.             return new Result(false, right);
  193.         else
  194.             return delFixL(((Node) left).delMin());
  195.     }
  196.  
  197.     private Result addFixL(final Result r) {
  198.         final Node n = new Node(value, height, r.node, right);
  199.         if (r.balanced)
  200.             return new Result(true, n);
  201.         else {
  202.             final Node nn = n.fixL_(0, 1);
  203.             return new Result(nn.left.getHeight() == nn.right.getHeight(), nn);
  204.         }
  205.     }
  206.  
  207.     private Result addFixR(final Result r) {
  208.         final Node n = new Node(value, height, left, r.node);
  209.         if (r.balanced)
  210.             return new Result(true, n);
  211.         else {
  212.             final Node nn = n.fixR_(0, 1);
  213.             return new Result(nn.left.getHeight() == nn.right.getHeight(), nn);
  214.         }
  215.     }
  216.  
  217.     private Result delFixR(final Result r) {
  218.         final Node n = new Node(value, height, left, r.node);
  219.         if (r.balanced)
  220.             return new Result(true, n);
  221.         else {
  222.             final Node nn = n.fixL_(-1, 0);
  223.             return new Result(nn.left.getHeight() != nn.right.getHeight(), nn);
  224.         }
  225.     }
  226.  
  227.     private Result delFixL(final Result r) {
  228.         final Node n = new Node(value, height, r.node, right);
  229.         if (r.balanced)
  230.             return new Result(true, n);
  231.         else {
  232.             final Node nn = n.fixR_(-1, 0);
  233.             return new Result(nn.left.getHeight() != nn.right.getHeight(), nn);
  234.         }
  235.     }
  236.  
  237.     private Node fixR_(final int b, final int u) {
  238.         switch (right.getHeight() - left.getHeight()) {
  239.         case 0:
  240.             return new Node(value, height + b, left, right);
  241.         case 1:
  242.             return new Node(value, height + u, left, right);
  243.         case 2:
  244.             return rotateLeft();
  245.         default:
  246.             throw new RuntimeException("invalid balance");
  247.         }
  248.     }
  249.  
  250.     private Node fixL_(final int b, final int u) {
  251.         switch (left.getHeight() - right.getHeight()) {
  252.         case 0:
  253.             return new Node(value, height + b, left, right);
  254.         case 1:
  255.             return new Node(value, height + u, left, right);
  256.         case 2:
  257.             return rotateRight();
  258.         default:
  259.             throw new RuntimeException("invalid balance");
  260.         }
  261.     }
  262.  
  263.     private Node rotateRight() {
  264.         final int h = right.getHeight();
  265.         switch (left.getLeft().getHeight() - left.getRight().getHeight()) {
  266.         case 1:
  267.             return rotateRight1(h + 2, h + 1);
  268.         case -1:
  269.             return rotateRight2(h + 2, h + 1, h + 1);
  270.         case 0:
  271.             return rotateRight1(h + 3, h + 2);
  272.         default:
  273.             throw new RuntimeException("invalid balance");
  274.         }
  275.     }
  276.  
  277.     private Node rotateLeft() {
  278.         final int h = left.getHeight();
  279.         switch (right.getRight().getHeight() - right.getLeft().getHeight()) {
  280.         case 1:
  281.             return rotateLeft1(h + 2, h + 1);
  282.         case -1:
  283.             return rotateLeft2(h + 2, h + 1, h + 1);
  284.         case 0:
  285.             return rotateLeft1(h + 3, h + 2);
  286.         default:
  287.             throw new RuntimeException("invalid balance");
  288.         }
  289.     }
  290.  
  291.     private Node rotateLeft1(final int nh, final int lh) {
  292.         return new Node(right.getValue(), nh, new Node(value, lh, left, right.getLeft()), right.getRight());
  293.     }
  294.  
  295.     private Node rotateLeft2(final int nh, final int lh, final int rh) {
  296.         final Node l = new Node(value, lh, left, right.getLeft().getLeft());
  297.         final Node r = new Node(right.getValue(), rh, right.getLeft().getRight(), right.getRight());
  298.         return new Node(right.getLeft().getValue(), nh, l, r);
  299.     }
  300.  
  301.     private Node rotateRight1(final int nh, final int rh) {
  302.         return new Node(left.getValue(), nh, left.getLeft(), new Node(value, rh, left.getRight(), right));
  303.     }
  304.  
  305.     private Node rotateRight2(final int nh, final int lh, final int rh) {
  306.         final Node l = new Node(left.getValue(), lh, left.getLeft(), left.getRight().getLeft());
  307.         final Node r = new Node(value, rh, left.getRight().getRight(), right);
  308.         return new Node(left.getRight().getValue(), nh, l, r);
  309.     }
  310.  
  311.     @Override
  312.     public void dump() {
  313.         dump_("");
  314.     }
  315.  
  316.     @Override
  317.     protected void dump_(final String s) {
  318.         right.dump_(s + "  ");
  319.         System.out.println(s + value);
  320.         left.dump_(s + "  ");
  321.     }
  322. }
  323.  
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
        31
      30
        29
    28
      27
  26
      25
    24
        23
      22
        21
20
        19
      18
        17
    16
        15
      14
        13
  12
        11
          10
      9
          8
        7
          6
    5
          4
        3
          2
      1
        0
https://ideone.com/z72BlQ
language:
Java (12.0.1)
created:
11 years ago
visibility:
public

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!