AVL树的实现

public class AVLTree<T extends Comparable<T>>{
	public AVLTreeNode<T> root;
	class AVLTreeNode<T>{
		T val;
		int height;
		AVLTreeNode<T> left;
		AVLTreeNode<T> right;
		public AVLTreeNode(){}
		public AVLTreeNode(T val){
			this.val = val;
			this.height = 1;
		}
		public AVLTreeNode(T val, int height, AVLTreeNode<T> left, AVLTreeNode<T> right){
			this.val = val;
			this.height = height;
			this.left = left;
			this.right = right;
		}
	}

	public AVLTreeNode<T> add(T val){
		root = add(root, val);
		return root;
	}

	public void remove(T val){
		remove(root, val);
	}

	private AVLTreeNode<T> remove(AVLTreeNode<T> node, T val){
		if(node == null) return null;

		if(val.compareTo(node.val) < 0){
			node.left = remove(node.left, val);
			if(getHeight(node.right) - getHeight(node.left) > 1){
				if(getHeight(node.right.left) > getHeight(node.right.right)) node.left = rotateRL(node);
				else node.left = rotateRR(node);
			}
		}else if(val.compareTo(node.val) > 0){
			node.right = remove(node.right, val);
			if(getHeight(node.left) - getHeight(node.right) > 1){
				if(getHeight(node.left.right) > getHeight(node.left.left)) node.left = rotateLR(node);
				else node.left = rotateLL(node);
			}
		}else{
			if(node.left == null || node.right == null){
				node = node.left != null ? node.left : node.right;
			}else{
				AVLTreeNode<T> successor;
				if(getHeight(node.left) > getHeight(node.right)){
					successor = getMax(node.left);
					remove(node.left, successor.val);
				}else{
					successor = getMin(node.right);
					remove(node.right, successor.val);
				}
				successor.left = node.left;
				successor.right = node.right;
				node = successor;
			}
		}

		return node;
	}

	private AVLTreeNode<T> getMax(AVLTreeNode<T> node){
		if(node == null) return null;

		if(node.right != null) return getMax(node.right);
		else return node;
	}

	private AVLTreeNode<T> getMin(AVLTreeNode<T> node) {
		if (node == null) return null;

		if (node.left != null) return getMin(node.left);
		else return node;
	}

	private AVLTreeNode<T> add(AVLTreeNode<T> node, T val){
		if(node == null) return new AVLTreeNode<>(val);

		if(val.compareTo(node.val) < 0){
			node.left = add(node.left, val);
			if(getHeight(node.left) - getHeight(node.right) > 1){
				if(getHeight(node.left.left) > getHeight(node.left.right)) node = rotateLL(node);
				else node = rotateLR(node);
			}
		}else{
			node.right = add(node.right, val);
			if(getHeight(node.right) - getHeight(node.left) > 1){
				if(getHeight(node.right.right) > getHeight(node.right.left)) node = rotateRR(node);
				else node = rotateRL(node);
			}
		}
		node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
		return node;
	}

	private AVLTreeNode<T> rotateLL(AVLTreeNode<T> node){
		AVLTreeNode<T> tmp = node.left;
		node.left = tmp.right;
		tmp.right = node;
		node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
		tmp.height = Math.max(getHeight(tmp.left), getHeight(tmp.right)) + 1;
		return tmp;
	}

	private AVLTreeNode<T> rotateRR(AVLTreeNode<T> node){
		AVLTreeNode<T> tmp = node.right;
		node.right = tmp.left;
		tmp.left = node;
		node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
		tmp.height = Math.max(getHeight(tmp.left), getHeight(tmp.right)) + 1;
		return tmp;
	}

	private AVLTreeNode<T> rotateLR(AVLTreeNode<T> node){
		node.left = rotateRR(node.left);
		return rotateLL(node);
	}

	private AVLTreeNode<T> rotateRL(AVLTreeNode<T> node){
		node.right = rotateLL(node.right);
		return rotateRR(node);
	}

	private int getHeight(AVLTreeNode<T> node){
		if(node == null) return 0;
		else return node.height;
	}
}