/*
 * $ java-algs4 RBBSTStats 1000000 86
 * N = 1000000
 * 2-3 height = 16  (best possible = 12)
 * Plain height = 27  (best possible = 19)
 * IPL = 18591205
 * Average depth = 18.5912  (best possible = 17.9514)
 * No. red links = 253681  (25.37% of the nodes are red)
 * Average no. of red links to an external node = 3.5912
 * $ java-algs4 RBBSTStats 10000000 86
 * N = 10000000
 * 2-3 height = 18  (best possible = 14)
 * Plain height = 34  (best possible = 23)
 * IPL = 221994857
 * Average depth = 22.1995  (best possible = 21.3223)
 * No. red links = 2540703  (25.41% of the nodes are red)
 * Average no. of red links to an external node = 5.1995
 * $ 
 */

public class RBBSTStats
{
    public static void main(String[] args)
    {
	int N = Integer.parseInt(args[0]);
	int[] a = RBBSTDraw.input(args);

	RedBlackBSTDraw<Integer, Integer> st = new RedBlackBSTDraw<>();

	for (int i = 0; i < N; i++)
	    st.put(a[i], i);
	
	StdOut.println("N = " + N);
	StdOut.printf("2-3 height = %d  (best possible = %d)\n",
		      st.height23P(), RBBSTDraw.log3ceil(N) - 1);
	StdOut.printf("Plain height = %d  (best possible = %d)\n",
		      st.height(), RBBSTDraw.lgfloor(N)
		      );
	int ipl = st.iplP();
	StdOut.println("IPL = " + ipl);
	StdOut.printf("Average depth = %.4f  (best possible = %.4f)\n",
		      (double)ipl / N,
		      (double)RBBSTDraw.bestIPL(N) / N
		      );
	int reds = st.sizeRP();
	StdOut.printf("No. red links = %d  (%.2f%% of the nodes are red)\n",
		      reds, 100.0 * reds / N);
	StdOut.printf("Average no. of red links to an external node = %.4f\n",
		      st.aveRedLinks());
    }
}