// // BST.java : JAVA test program embodying the ideas from the article // // "Building optimal binary search trees from sorted values in O(N) time" // submitted to the Festschrift for Ole-Johan Dahl // Jean Vaucher, // 28 august 2002 // // Use: // % javac BST.java // % java BST 17 45 // or more generally // % java BST n1 n2 n3 .... // The program will build trees with // n1 n2 n3 ... nodes class BST { static int n_nodes, iData = 0; static void resetData() { iData=0; } static int nextValue() { return ++iData; } static boolean end_of_data() { return iData == n_nodes; } public static void main (String [] args) { for (int i=0; i< args.length; i++) { n_nodes = Integer.parseInt( args[i] ); System.out.println("n_nodes: " + n_nodes); nl(); resetData(); Node T = readTree(); T.dump(); System.out.println("--------------\n" ); } } static Node readTree () // final version { int h = 0; Node tree = null, left = null; while (! end_of_data()) { left = tree; int root_value = nextValue () ; Node right = readTree2 ( h ) ; tree = new Node(root_value, left, right ) ; h ++ ; } return optimize( tree, n_nodes, h ); } static Node readTree2 ( int h ) { if (h < 1) return null ; Node left = readTree2 ( h-1 ) ; if (end_of_data()) return left ; int value = nextValue () ; Node right = readTree2 ( h-1 ) ; return new Node( value, left, right ) ; } static Node optimize ( Node root, int N, int h ) { if ( N <= 1 ) return root; int hL = h-1 ; int nR = N - (1<< (h-1)) ; int hR = BTheight( nR ); Node newRoot = root; if (hL > hR) { Node leftTree = newRoot = root.left; hL = hL-1; while (hL > hR) { leftTree = leftTree.right; hL = hL-1; } root.left = leftTree.right; leftTree.right = root; } root.right = optimize ( root.right, nR, hR ); return newRoot; } static int BTheight ( int n ) { int h = 0; for (int i=n; i>0; i=i/2) h++; return h; } static void nl() { System.out.println(); } } // --------- Auxiliary classes for the tree ---------------- class Node { int value; Node left, right; public Node (int n, Node l, Node r) { value = n; left = l; right = r; } void dump () { dump(0) ; } void dump (int h) { if (right != null) right.dump(h+1); for (int i=0; i