How do I find the number of inversions using a red black tree?

Question

I'm trying to figure out a way to find the number of inversions in permutation time O(nlogn) using red black trees. Here's how I think it can be done. So if I have an algorithm that inserts a new node into a red black tree then by inserting the node if it inserts properly then it means the values are in the proper order and there's no inversions. If a value is inserted and the order property is not satisfied then we need to either rotate the tree or change the color of the branches to satisfy the order property. So I have an insert method that looks like this:

private Node put(Node h, Key key, Value val){
        if(h==null)
            return new Node(key, val, 1, RED);
        int cmp = key.compareTo(h.key);
        if (cmp < 0) h.left = put(h.left, key, val);
        else if (cmp > 0) h.right = put(h.right, key, val);
        else h.val = val;

        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)) 
            flipColors(h);

        h.N = size(h.left) + size(h.right) + 1;
        return h;
    }

Now if I declared a variable that kept count of all the inversions then at what points would I need to put it at and is there any code that is unnecessary when counting the inversions? What I'm thinking of doing is replacing all the rotations and color changes with inversion incrementing. Would doing that still give me the right number of inversions in O(nlogn) time?

Answer 1

What you are trying to do is correct. However only number of rotations will not be able to tell you anything about the inversions. The whole procedure is as follows.

You start with an empty red-black tree. Then you insert the elements in the given sequence one by one, in the order that they occur in the sequence.

Whenever an element $x$ in the sequence is inserted, the elements larger than $x$ already existing in the red-black tree are inversions. You need to calculate this number.

You total up all the inversions for all elements and you get the total number of inversions.

You need to augment the red-black tree by keeping the size of sub-trees in the interior nodes. Then you can find the number of elements larger than $x$ either during insertion or after insertions by doing a search of element $x$.

Since you are confused about the strategy, I suggest you should use the second method. Don't count the larger elements during the insertion stage. Count them immediately after the insertion is done and before another insertion is to be done (in a separate function). This will take additional $O(\log n)$ on the augmented tree.

If all your numbers are distinct then this algorithm suffices. However, if some numbers are same, then you have to modify your insertion to insert only at the rightmost possible position and/or counting only the strictly larger elements depending on your algorithm. You will need to further augment the data structure to hold the min-value and max-value of the sub-tree in the node.