//nlgn
public class BTree {
Node root;
public BTree(int n) {
root = makeTree(n, 0);
}
private Node makeTree(int number, int base) {
if (number == 0) return null;
Node node = new Node((number + 1) / 2 + base);
node.numOfLeftChildren = (number - 1) / 2;
node.left = makeTree(node.numOfLeftChildren, base);
node.right = makeTree(number / 2, node.value);
return node;
}
public Node remove(int index) {
return remove(root, index);
}
private Node remove(Node node, int index) {
if (node.numOfLeftChildren > index) {
//left
node.numOfLeftChildren--;
return remove(node.left, index);
}
if (node.numOfLeftChildren == index && !node.removed) {
//current
node.removed = true;
return node;
}
//right
return remove(node.right, index - node.numOfLeftChildren - (node.
removed ? 0 : 1));
}
public static int[] recover(int[] a) {
BTree list = new BTree(a.length);
int[] s = new int[a.length];
for (int i = 0; i < a.length; i++) {
s[i] = list.remove(a[i]).value;
}
return s;
}
static class Node {
int numOfLeftChildren;
int value;
Node left;
Node right;
boolean removed = false;
Node(int value) {
this.value = value;
}
}
public static void main(String[] args) {
List x = new ArrayList();
int NUM = 100;
for (int i = 0; i < NUM; i++) x.add(i + 1);
Collections.shuffle(x);
int[] a = makeSample(x.toArray());//new int[]{2,0,1,0};
System.out.println(Arrays.toString(x.toArray()));
System.out.println(Arrays.toString(a));
System.out.println(Arrays.toString(recover(a)));
}
private static int[] makeSample(Object[] x) {
int[] a = new int[x.length];
for (int i = 0; i < a.length; i++)
for (int j = i + 1; j < a.length; j++) {
if (((Integer) x[j]) < ((Integer) x[i])) a[i]++;
}
return a;
}
}
