AVL树

在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。

查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n)。

增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。

import java.util.LinkedList;
import java.util.Queue;

public class MyAVLTree {
	private class AVLNode {

		public AVLNode parent;
		public AVLNode leftChild, rightChild;
		public int data;
		
		public AVLNode(AVLNode parent, AVLNode leftChild, AVLNode rightChild, int data) {
			this.parent = parent;
			this.leftChild = leftChild;
			this.rightChild = rightChild;
			this.data = data;
		}
		
		public AVLNode(int data) {
			this(null, null, null, data);
		}
		
		public AVLNode(AVLNode parent, int data) {
			this.parent = parent;
			this.data = data;
		}
	}
	
	private AVLNode root;
	private final int LEFT = 1;
	private final int RIGHT = -1;
	private final int MAX_LEFT = 2;
	private final int MAX_RIGHT = -2;
	
	/**
	 * 插入节点
	 * @param data
	 */
	public void put(int data) {
		putData(root, data);
	}
	
	private boolean putData(AVLNode node, int data) {
		if(node == null) {
			node  = new AVLNode(data);
			root = node;
			return true;
		}
		int t;
		AVLNode p;
		AVLNode temp = node;
		do {
			p = temp;
			t = temp.data - data;
			if(t < 0) {
				temp = temp.rightChild;
			}
			else if(t > 0) {
				temp = temp.leftChild;
			}
			else {
				return false;
			}
		} while(temp != null);
		
		if(t < 0) {
			p.rightChild = new AVLNode(p, data);
		}
		else if(t > 0) {
			p.leftChild = new AVLNode(p, data);
		}
		rebuild(p);
		return true;
		
	}
	
	/**
	 * 平衡二叉树的方法
	 * @param node
	 */
	public void rebuild(AVLNode node) {
		while(node != null) {
			if(calcNodeBalanceValue(node) == MAX_LEFT) {
				fixAfterInsertion(node, LEFT);
			}
			else if(calcNodeBalanceValue(node) == MAX_RIGHT) {
				fixAfterInsertion(node, RIGHT);
			}
			node = node.parent;
		}
	}
	
	
	/**
	 * 调整树的结构
	 * @param node
	 * @param type
	 */
	public void fixAfterInsertion(AVLNode node, int type) {
		if(type == LEFT) {
			AVLNode leftChild = node.leftChild;
			if(leftChild.leftChild != null) {  //右旋
				rightRotation(node);
			}
			else if(leftChild.rightChild != null) {   //左右旋
				leftRotation(leftChild);
				rightRotation(node);
			}
		}
		else if(type == RIGHT) {
			AVLNode rightChild = node.rightChild;
			if(rightChild.rightChild != null) {   //左旋
				leftRotation(node);
			}
			else if(rightChild.leftChild != null) {   //右左旋
				rightRotation(rightChild);
				leftRotation(node);
			}
		}
	}
	
	
	/**
	 * 右旋
	 * @param node
	 * @return
	 */
	public AVLNode rightRotation(AVLNode node) {
		if(node != null) {
			
			AVLNode leftChild = node.leftChild;
			node.leftChild = leftChild.rightChild;
			// 如果leftChild的右节点存在，则需将该右节点的父节点指给node节点
			if(leftChild.rightChild != null) {  
				leftChild.rightChild.parent = node;
			}
			leftChild.parent = node.parent;
			if(node.parent == null) {
				this.root = leftChild;
			}
			else if(node.parent.rightChild == node) {  // 即node节点在它原父节点的右子树中
				node.parent.rightChild = leftChild;
			}
			else if(node.parent.leftChild == node) {
				node.parent.leftChild = leftChild;
			}
			
			leftChild.rightChild = node;
			node.parent = leftChild;
			return leftChild;
		}
		
		return null;
	}
	
	/**
	 * 左旋
	 * @param node
	 * @return
	 */
	public AVLNode leftRotation(AVLNode node) {
		
		if(node != null) {
			AVLNode rightChild = node.rightChild;
			node.rightChild = rightChild.leftChild;
			if(rightChild.leftChild != null) {
				rightChild.leftChild.parent = node;
			}
			rightChild.parent = node.parent;
			if(node.parent == null) {
				this.root = rightChild;
			}
			else if(node.parent.rightChild == node) {
				node.parent.rightChild = rightChild;
			}
			else if(node.parent.leftChild == node) {
				node.parent.leftChild = rightChild;
			}
			rightChild.leftChild = node;
			node.parent = rightChild;
			return rightChild;
		}
		
		return null;
	}
	
	/**
	 * 计算node节点的BF值
	 * @param node
	 * @return
	 */
	public int calcNodeBalanceValue(AVLNode node) {
		if(node != null) {
			return getHeightByNode(node);
		}
		return 0;
	}
	
	private int getHeightByNode(AVLNode node) {
		if(node == null) {
			return 0;
		}
		return getChildDepth(node.leftChild) - getChildDepth(node.rightChild);
	}
	
	private int getChildDepth(AVLNode node) {
		if(node == null) {
			return 0;
		}
		return 1 + Math.max(getChildDepth(node.leftChild), getChildDepth(node.rightChild));
	}
	
	
	/**
	 * 中序遍历
	 */
	public void middOrderErgodic() {
		this.middOrderErgodic(this.root);
	}
	public void middOrderErgodic(AVLNode node) {
		if(node != null) {
			this.middOrderErgodic(node.leftChild);
			System.out.print(node.data + ", ");
			this.middOrderErgodic(node.rightChild);
		}
	}
	
	
	/**
	 * 删除指定val值的节点
	 * @param val
	 * @return
	 */
	public boolean delete(int val) {
		AVLNode node = getNode(val);
		if(node == null) {
			return false;
		}
		boolean flag = false;
		AVLNode p = null;
		AVLNode parent = node.parent;
		AVLNode leftChild = node.leftChild;
		AVLNode rightChild = node.rightChild;
		if(leftChild == null && rightChild == null) {
			if(parent != null) {
				if(parent.leftChild == node) {
					parent.leftChild = null;
				}
				else if(parent.rightChild == node) {
					parent.rightChild = null;
				}
			}
			else {
				this.root = null;
			}
			
			p = parent;
			node = null;
			flag = true;
		}
		else if(leftChild == null && rightChild != null) {
			if(parent != null && parent.data > val) {
				parent.leftChild = rightChild;
			}
			else if(parent != null && parent.data < val) {
				parent.rightChild = rightChild;
			}
			else {
				this.root = rightChild;
			}
			p = parent;
			node = null;
			flag = true;
		}
		else if(leftChild != null && rightChild == null) {
			if(parent != null &&  parent.data > val) {
				parent.leftChild = leftChild;
			}
			else if(parent != null && parent.data < val) {
				parent.rightChild = leftChild;
			}
			else {
				this.root = leftChild;
			}
			
			p = parent;
			node = null;
			flag = true;
		}
		else if(leftChild != null && rightChild != null) {
			AVLNode successor = getSuccessor(node);
			int tempData = successor.data;
			if(delete(tempData)) {
				node.data = tempData;
			}
			p = successor;
			successor = null;
			flag = true;
		}
		
		if(flag) {
			this.rebuild(p);
		}
		return flag;	
	}
	
	
	/**
	 * 获得指定节点
	 * @param key
	 * @return
	 */
	public AVLNode getNode(int key) {
	
		AVLNode node = root;
		int t;
		do {
			t = node.data - key;
			if(t > 0) {
				node = node.leftChild;
			}
			else if(t < 0) {
				node = node.rightChild;
			}
			else {
				return node;
			}
		} while(node != null);
		return null;
	}
	
	
	/***
	 * 获得指定节点的后继
	 * 找到node节点的后继节点
     * 1、先判断该节点有没有右子树，如果有，则从右节点的左子树中寻找后继节点，没有则进行下一步
     * 2、查找该节点的父节点，若该父节点的右节点等于该节点，则继续寻找父节点，
     *   直至父节点为Null或找到不等于该节点的右节点。
     * 理由，后继节点一定比该节点大，若存在右子树，则后继节点一定存在右子树中，这是第一步的理由
     *      若不存在右子树，则也可能存在该节点的某个祖父节点(即该节点的父节点，或更上层父节点)的右子树中，
     *      对其迭代查找，若有，则返回该节点，没有则返回null
	 * @param node
	 * @return
	 */
	public AVLNode getSuccessor(AVLNode node) {
		if(node.rightChild != null) {
			AVLNode rightChild=  node.rightChild;
			while(rightChild.leftChild != null) {
				rightChild = rightChild.leftChild;
			}
			return rightChild;
		}
		AVLNode parent = node.parent;
		while(parent != null && (node == parent.rightChild)) {
			node = parent;
			parent = parent.parent;
		}
		return parent;
	}
	
	
	/**
	 * 层序遍历
	 */
	public void sequenceErgodic() {
		if(this.root == null) {
			return;
		}
		Queue<AVLNode> queue = new LinkedList<>();
		AVLNode temp = null;
		queue.add(this.root);
		while(!queue.isEmpty()) {
			temp = queue.poll();
			System.out.println("当前节点值：" + temp.data + ", BF：" + calcNodeBalanceValue(temp));
			if(temp.leftChild != null) {
				queue.add(temp.leftChild);
			}
			if(temp.rightChild != null) {
				queue.add(temp.rightChild);
			}
		}
	}
	
	public static void main(String[] args) {
		MyAVLTree bbt = new MyAVLTree();
        bbt.put(3);
        bbt.put(2);
        bbt.put(1);
        bbt.put(4);
        bbt.put(5);
        bbt.put(6);
        bbt.put(7);
        bbt.put(10);
        bbt.put(9);
        bbt.middOrderErgodic();
        System.out.println();
        System.out.println("-----各节点平衡状况-----");
        bbt.sequenceErgodic();
        System.out.println();
        bbt.delete(5);
        bbt.delete(2);
        bbt.middOrderErgodic();
        System.out.println();
        System.out.println("-----各节点平衡状况-----");
        bbt.sequenceErgodic();
        System.out.println();
        
	}
}