package com.project.my.avl;

/**
 * @see https://rosettacode.org/wiki/AVL_tree#Java
 */
public class AvlTree {
	private Node root;

	private class Node {
		private int key;
		private int balance;
		private Node left, right, parent;

		Node(int k, Node p) {
			key = k;
			parent = p;
		}
	}

	public boolean insert(int key) {
		if (root == null)
			root = new Node(key, null);
		else {
			Node n = root;
			Node parent;
			while (true) {
				if (n.key == key)
					return false;

				parent = n;

				boolean goLeft = n.key > key;
				n = goLeft ? n.left : n.right;

				if (n == null) {
					if (goLeft) {
						parent.left = new Node(key, parent);
					} else {
						parent.right = new Node(key, parent);
					}
					rebalance(parent);
					break;
				}
			}
		}
		return true;
	}

	public void delete(int delKey) {
		if (root == null)
			return;
		Node n = root;
		Node parent = root;
		Node delNode = null;
		Node child = root;

		while (child != null) {
			parent = n;
			n = child;
			child = delKey >= n.key ? n.right : n.left;
			if (delKey == n.key)
				delNode = n;
		}

		if (delNode != null) {
			delNode.key = n.key;

			child = n.left != null ? n.left : n.right;

			if (root.key == delKey) {
				root = child;
			} else {
				if (parent.left == n) {
					parent.left = child;
				} else {
					parent.right = child;
				}
				rebalance(parent);
			}
		}
	}

	public boolean search(int value) {
		Node current = root;
		while (current != null) {
			if (current.key == value) {
				return true;
			} else if (current.key < value) {
				current = current.right;
			} else
				current = current.left;
		}
		return false;
	}

	private void rebalance(Node n) {
		setBalance(n);

		if (n.balance == -2) {
			if (height(n.left.left) >= height(n.left.right))
				n = rotateRight(n);
			else
				n = rotateLeftThenRight(n);

		} else if (n.balance == 2) {
			if (height(n.right.right) >= height(n.right.left))
				n = rotateLeft(n);
			else
				n = rotateRightThenLeft(n);
		}

		if (n.parent != null) {
			rebalance(n.parent);
		} else {
			root = n;
		}
	}

	private Node rotateLeft(Node a) {

		Node b = a.right;
		b.parent = a.parent;

		a.right = b.left;

		if (a.right != null)
			a.right.parent = a;

		b.left = a;
		a.parent = b;

		if (b.parent != null) {
			if (b.parent.right == a) {
				b.parent.right = b;
			} else {
				b.parent.left = b;
			}
		}

		setBalance(a, b);

		return b;
	}

	private Node rotateRight(Node a) {

		Node b = a.left;
		b.parent = a.parent;

		a.left = b.right;

		if (a.left != null)
			a.left.parent = a;

		b.right = a;
		a.parent = b;

		if (b.parent != null) {
			if (b.parent.right == a) {
				b.parent.right = b;
			} else {
				b.parent.left = b;
			}
		}

		setBalance(a, b);

		return b;
	}

	private Node rotateLeftThenRight(Node n) {
		n.left = rotateLeft(n.left);
		return rotateRight(n);
	}

	private Node rotateRightThenLeft(Node n) {
		n.right = rotateRight(n.right);
		return rotateLeft(n);
	}

	private int height(Node n) {
		if (n == null)
			return -1;
		return 1 + Math.max(height(n.left), height(n.right));
	}

	private void setBalance(Node... nodes) {
		for (Node n : nodes)
			n.balance = height(n.right) - height(n.left);
	}

	public void printBalance() {
		printBalance(root);
	}

	private void printBalance(Node n) {
		if (n != null) {
			printBalance(n.left);
			System.out.printf("%s ", n.balance);
			printBalance(n.right);
		}
	}

	public static void main(String[] args) {
		AvlTree tree = new AvlTree();

		System.out.println("Inserting values 1 to 10");
		for (int i = 1; i <= 10; i++)
			tree.insert(i);

		System.out.print("Printing balance: ");
		tree.printBalance();
	}
}
@@ -197,16 +197,17 @@
  balance
+1
 ;%0D%0A%09%09pri
@@ -333,18 +333,16 @@
 rt(int k
-ey
 ) %7B%0D%0A%09%09i
@@ -379,18 +379,16 @@
 w Node(k
-ey
 , null);
@@ -472,18 +472,16 @@
 key == k
-ey
 )%0D%0A%09%09%09%09%09
@@ -546,18 +546,16 @@
 .key %3E k
-ey
 ;%0D%0A%09%09%09%09n
@@ -618,16 +618,17 @@
 %09%09%09%09if (
+!
 goLeft) 
@@ -639,27 +639,28 @@
 %09%09%09%09%09parent.
-lef
+righ
 t = new Node
@@ -653,34 +653,32 @@
 ght = new Node(k
-ey
 , parent);%0D%0A%09%09%09%09
@@ -693,36 +693,35 @@
 %7B%0D%0A%09%09%09%09%09%09parent.
-righ
+lef
 t = new Node(key
@@ -718,18 +718,16 @@
 w Node(k
-ey
 , parent
@@ -1781,24 +1781,25 @@
 f (n.balance
+1
  == -2) %7B%0D%0A%09
@@ -1941,16 +1941,17 @@
 .balance
+1
  == 2) %7B
@@ -3328,16 +3328,17 @@
 .balance
+1
  = heigh
@@ -3554,16 +3554,17 @@
 .balance
+1
 );%0D%0A%09%09%09p

insert changed