Explain carefully how to use redblack trees to compute the n

Explain carefully how to use red-black trees to compute the number of inversions in a permutation time 0(n log n). Effectively, you may need to modify the code for Algorithm 3.4 on page 439. Explain in detail any changes that you would make to method put().

Solution

The red black trees can be used to computer the number of inversions in a permutation in time O(nlogn) by:

1)The first step is to start with an empty red-black tree.

2).The second step is to insert the elements in the given sequence one by one, in the order that they occur in the sequence.

3)Now,whenever an element y in the sequence is inserted, the elements larger than y already existing in the red-black tree are inverter. It is very important to calculate this number.

4)The next step is to total up all the inversions for all elements and hence we get the total number of inversions.

5)The next step is to augment the red-black tree by keeping the size of sub-trees in the interior nodes.This will help us to   find the number of elements larger than y either during insertion or after insertions by doing a search of element y

As a result Counting the elements immediately after the insertion is done and before another insertion is to be done (in a separate function) should be the method to be followed. This will take additional O(nlogn)on the augmented tree.

There will be no changes in the put() method.