<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">/*
 * $ java-introcs PlainBSTDraw 255 888
 * $ java-introcs PlainBSTDraw 255 888 -
 * $ java-introcs PlainBSTDraw 255 888 +
 * $ java-introcs PlainBSTDraw 255 888 Z
 * $ 
 */

public class PlainBSTDraw
{
    // assume N &gt; 0
    public static int lgfloor(int N) {
	int t = 0;
	while (N &gt; 1) {
	    t++;
	    N /= 2;
	}
	return t;
    }

    public static int bestIPL(int N) {
	int q = lgfloor(N + 1);
	return (N + 1) * q - (1 &lt;&lt; (q + 1)) + 2;
    }

    public static int[] input(String[] args) {
	int N = Integer.parseInt(args[0]);
	long seed = Long.parseLong(args[1]);
	StdRandom.setSeed(seed);

	int[] a = new int[N];	
	if (args.length &lt; 3) { // random
	    for (int i = 0; i &lt; N; i++)
		a[i] = i;
	    StdRandom.shuffle(a);
	} else if (args[2].equals("-")) // decreasing
	    for (int i = 0; i &lt; N; i++)
		a[i] = -i;
	else if (args[2].equals("+")) // increasing
	    for (int i = 0; i &lt; N; i++)
		a[i] = i;
	else if (args[2].equals("Z")) { // zigzag
	    int s = -1;
	    for (int i = 0; i &lt; N; i++) {
		a[i] = s * (N - i);
		s *= -1;
	    }
	}
	return a;
    }
    
    public static void main(String[] args)
    {
	int N = Integer.parseInt(args[0]);
	if (N &gt;= 1050) { // some ad hoc limit
	    StdOut.println("N should be less than 1050");
	    System.exit(-1);
	}
	int[] a = input(args);

	BSTDraw&lt;Integer, Integer&gt; st = new BSTDraw&lt;&gt;();	

	st.drawPrepare(800);
	StdDraw.enableDoubleBuffering();
	for (int i = 0; i &lt; N; i++) { 
	    st.put(a[i], i); 
	    int NN = i + 1; // number of nodes
	    st.draw(.95, .003, .004);
	    StdDraw.setPenColor(StdDraw.BLACK);
	    StdDraw.textLeft(0.02, 0.33, "N = " + NN);
	    StdDraw.textLeft(0.02, 0.28, "");
	    StdDraw.textLeft(0.02, 0.23,
			     String.format("Plain height = %d  (best possible = %d)",
					   st.height(), lgfloor(NN)
					   ));
	    int ipl = st.iplP();
	    StdDraw.textLeft(0.02, 0.18, "IPL = " + ipl);
	    StdDraw.textLeft(0.02, 0.13,
			     String.format("Average depth = %.4f  (best possible = %.4f)",
					   (double)ipl / (NN),
					   (double)bestIPL(NN) / NN
					   ));
	    StdDraw.textLeft(0.02, 0.08, "");
	    StdDraw.textLeft(0.02, 0.03, "");
	    StdDraw.show();
	    StdDraw.pause(100);		
	}
    }
}
</pre></body></html>