Java Left left leaning red black tree from scratch
Maintain two balanced binary trees and store the size of subtree in every Node. Both insert and greaterCount methods perform in log(n). LLRD data structure is b
Maintain two balanced binary trees and store the size of subtree in every Node. Both insert and greaterCount methods perform in log(n). LLRD data structure is based on: https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf

# Code
```java []
class Solution {

    public int[] resultArray(int[] nums) {
        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
        LLRB leftRB = new LLRB();
        LLRB rightRB = new LLRB();
        left.add(nums[0]);
        right.add(nums[1]);
        leftRB.insert(nums[0]);
        rightRB.insert(nums[1]);

        for (int i = 2; i < nums.length; i++) {
            int num = nums[i];
            int leftGreater = leftRB.greaterThan(num);
            int rightGreater = rightRB.greaterThan(num);

            if (leftGreater > rightGreater) {
                leftRB.insert(num);
                left.add(num);
            } else if (leftGreater < rightGreater) {
                rightRB.insert(num);
                right.add(num);
            } else {
                if (left.size() < right.size()) {
                    leftRB.insert(num);
                    left.add(num);
                } else if (left.size() > right.size()) {
                    rightRB.insert(num);
                    right.add(num);
                } else {
                    leftRB.insert(num);
                    left.add(num);
                }
            }
        }

        left.addAll(right);
        return left.stream().mapToInt(Integer::intValue).toArray();
    }


    static class LLRB {
        private static final boolean RED = true;
        private static final boolean BLACK = false;
        private Node root;

        private class Node {
            private Integer key;
            private Node left, right;
            private boolean color;
            int size = 1;

            Node(Integer key) {
                this.key = key;
                this.color = RED;
            }
        }

        public int greaterThan(Integer key) {
            return greaterThan(root, key);
        }

        private int greaterThan(Node h, Integer key) {
            if (h == null) return 0;

            int cmp = key.compareTo(h.key);
            if (cmp == 0) return getSize(h.right);
            else if (cmp < 0) return greaterThan(h.left, key) + getSize(h) - getSize(h.left);
            else return greaterThan(h.right, key);
        }

        public void insert(Integer key) {
            root = insert(root, key);
            root.color = BLACK;
        }

        private Node insert(Node h, Integer key) {
            if (h == null) return new Node(key);

            int cmp = key.compareTo(h.key);
            if (cmp < 0) h.left = insert(h.left, key);
            else if (cmp > 0) h.right = insert(h.right, key);
            h.size++;

            if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
            if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
            if (isRed(h.left) && isRed(h.right)) colorFlip(h);
            return h;
        }

        boolean isRed(Node h) {
            return h != null && h.color == RED;
        }

        Node rotateLeft(Node h) {
            Node x = h.right;
            int tempXSize = getSize(x) - getSize(x.left);
            h.size -= getSize(x);
            h.size += getSize(x.left);
            h.right = x.left;
            x.left = h;
            x.size = tempXSize + getSize(h);
            x.color = h.color;
            h.color = RED;
            return x;
        }

        Node rotateRight(Node h) {
            Node x = h.left;
            int tempXSize = getSize(x) - getSize(x.right);
            h.size -= getSize(x);
            h.left = x.right;
            h.size += getSize(x.right);
            x.right = h;
            x.size = tempXSize + getSize(h);
            x.color = h.color;
            h.color = RED;
            return x;
        }

        void colorFlip(Node h) {
            h.color = !h.color;
            h.left.color = !h.left.color;
            h.right.color = !h.right.color;
        }

        int getSize(Node h) {
            return h == null ? 0 : h.size;
        }
    }
}
```
['Java']