import java.util.ArrayDeque;
import java.util.Deque;

// Binary Search Tree
public class BinarySearchTree {
	private Node root;
	private int NodeCount = 0;

	// insert a node
	public void insert(int value) {
		Node node = new Node(value);
		NodeCount++;
		if (root == null) {
			root = node;
			return;
		}
		insertRecord(root, node);
	}

	private void insertRecord(Node latestRoot, Node node) {

		if (latestRoot.value > node.value) {

			if (latestRoot.left == null) {
				node.parent = latestRoot;
				latestRoot.left = node;
				return;
			} else {
				insertRecord(latestRoot.left, node);
			}
		} else {
			if (latestRoot.right == null) {
				node.parent = latestRoot;
				latestRoot.right = node;
				return;
			} else {
				insertRecord(latestRoot.right, node);
			}
		}
	}

	// search a node by value and return the node
	public Node search(int value) {
		return searchRecord(root, value);
	}

	private Node searchRecord(Node latestRoot, int value) {
		if (latestRoot == null)
			return null;
		int cmp = value - latestRoot.value;
		if (cmp < 0)
			return searchRecord(latestRoot.left, value);
		else if (cmp > 0)
			return searchRecord(latestRoot.right, value);
		else
			return latestRoot;
	}

	// balance this tree
	public void balance() {
		if (NodeCount <= 1) {
			return;
		} else {
			// Start to balance
			a();
			b();
		}
		return;
	}

	private void a() {
		Deque<Node> stack = new ArrayDeque<Node>();
		Node cur = root, front = null, tail = null;

		// In-order traversal via a stack (after Carrano)

		while (true) // Infinite loop exited via break Carrano code is
						// equivalent in behavior to a "while"
		{
			while (cur != null) {
				stack.push(cur);
				cur = cur.left;
			}
			// What follows would be under Carrano's "else"
			if (stack.isEmpty())
				break; // Exit the processing loop
			else {
				cur = stack.pop();
				if (front == null)
					front = tail = cur;
				else
					tail = tail.right = cur;
				cur.left = null;
				cur = cur.right;
			}
		}
		root = front;
		return;
	}

	private void b() {
		// FORM BALANCED TREE --- after Stout and Warren

		// Pseudo-root used; real root to the right
		Node pseudo = new Node(-1);
		int m, nBack = NodeCount - 1;

		pseudo.right = root;
		for (m = nBack / 2; m > 0; m = nBack / 2) {
			int j = 0;
			Node scanner = pseudo;

			for (j = 0; j < m; j++) {// leftward rotation
				Node child = scanner.right;
				scanner.right = child.right;
				scanner = scanner.right;
				child.right = scanner.left;
				scanner.left = child;
			} // end for j . . .
			nBack = nBack - m - 1;
		} // end for m . . .
		root = pseudo.right;
		return;
	}

}

@@ -1220,16 +1220,51 @@
 is tree%0A
+%09// based on Colin Day's Algorithm%0A
 %09public 
@@ -1356,17 +1356,32 @@
 %0A%09%09%09
-a();%0A%09%09%09b
+traversal();%0A%09%09%09rotation
 ();%0A
@@ -1412,17 +1412,25 @@
 te void 
-a
+traversal
 () %7B%0A%09%09D
@@ -1587,16 +1587,25 @@
  (true) 
+%0A%09%09%7B%09%0A%09%09%09
 // Infin
@@ -1646,19 +1646,16 @@
 code is%0A
-%09%09%09
 %09%09%09// eq
@@ -1690,17 +1690,16 @@
 hile%22%0A%09%09
-%7B
 %0A%09%09%09whil
@@ -2091,17 +2091,24 @@
 te void 
-b
+rotation
 () %7B%0A%09%09/
@@ -2155,17 +2155,16 @@
  Warren%0A
-%0A
 %09%09// Pse
@@ -2402,16 +2402,21 @@
 ; j++) %7B
+%0A%09%09%09%09
 // leftw

update BST