前言

在《一文彻底掌握二叉查找树，非史上最全总结（多图，附代码） 》我们讲了二叉查找树，在文章的最后我们也提到了，二叉查找树查找的效率受到树的深度的影响，最坏情况是O(N)。而二叉查找树的深度是根据数据插入的顺序不同而表现出不同的。那么有没有可能让树的深度尽可能低，从而提高我们查询的效率呢？答案就是今天要讲的平衡二叉树（AVL树）。

定义

AVL树是二叉查找树的一个特例，所以上一篇文章说到的二叉查找树的定义是AVL树定义的前提。在这个前提之下，AVL树再提出了写更加严格的定义。那就是，树的任意节点的子树的高度差都小于等于1。

树的操作

由于AVL树比普通的二叉查找树有个更加苛刻的要求，要求子树的高度差小于等于1。那么在树的插入、删除等操作时将会比普通的二叉查找树更加麻烦。

插入

AVL树插入的第一步其实跟二叉查找树一样，但是插入数据后，可能会导致树失去平衡，那么这时就需要对子树进行旋转了。通过选择来使得树继续保持平衡。

树失去平衡会有四种情况：

1. 节点的左儿子的左子树插入节点，导致左子树比右子树高（LL），如下图树插入节点1之后，6的左子树高度比右子树高2。
2. 节点的右儿子的右子树插入节点，导致右子树比左子树高（RR）
3. 节点的左儿子的右子树插入节点，导致左子树比右子树高（LR）
4. 节点的右儿子的左子树插入节点，导致左子树比右子树高（RL）

AVL树失去平衡之后，可以通过旋转使其恢复平衡。四种失去平衡的情况下对应的旋转方法分别如下：

(a)LL的旋转，步骤如下：

1. 将根节点的左孩子作为新根节点。
2. 将新根节点的右孩子作为原根节点的左孩子。
3. 将原根节点作为新根节点的右孩子。

伪代码：

// 要旋转的节点为node，其父节点是parent

Node temp = node.left;

node.left = temp.right;

temp.right = node;

parent.left = temp;

LL 旋转示意图如下：

(b)RR的旋转，旋转方法与LL旋转对称，步骤如下：

1. 将根节点的右孩子作为新根节点。
2. 将新根节点的左孩子作为原根节点的右孩子。
3. 将原根节点作为新根节点的左孩子。

RR旋转示意图如下：

（c)LR的旋转：

LR失去平衡的情况，单旋转不能解决问题，需要进行两次旋转，步骤如下：

1. 根节点的左孩子做一次RR旋转。
2. 根节点做一次LL旋转。

LR的旋转示意图如下：

(d)RL的旋转：

RL旋转方法与LR旋转对称，步骤如下：

1. 根节点的右孩子做一次LL旋转。
2. 根节点做一次RR旋转。

RL的旋转示意图如下：

删除

平衡二叉树的节点删除操作会比较复杂，我们可以这么分析，左子树上节点的删除相当于我们在右子树上插入了一个新节点，右子树上节点的删除相当于在左子树上插入了一个新节点。我们可以根据这一点进行判断并采取对应的平衡调整操作。

具体做法需要从当前节点判断树是否失去平衡，通过计算左右子树的高度差，判断是哪种失衡。然后运用旋转，将树调整为平衡树。

1. 排序二叉树的删除
2. 判断左右子树高度差是否小于2，判断结点是否失衡
3. 当前结点失衡，将删除视为另一侧的插入，依照插入的旋转思想进行旋转
4. 如此反复直至根节点

查询

由于AVL树本身就是一颗二叉查找树，所以其节点查询与普通的二叉树没什么两样，这里就不赘述了。如果有不清楚的同学，可以翻看我的上篇文章。

代码

代码我在上篇文章的基础上进行修改，Node类上加入字段height标识子树的高度，比在insert、delete方法上加上判断结构和旋转

public class AVLTree {
	private Node root;

	public void insert(int value) {

		root = insert(root, value);
	}

	private Node insert(Node x, int value) {
		if (x == null) {// 首次插入
			return new Node(value, 1);
		}
		int xVal = x.value;

		if (value < xVal) {
			x.left = insert(x.left, value);

			if (getHeight(x.left) - getHeight(x.right) > 1) {// left
				if (getHeight(x.left.left) > getHeight(x.left.right)) {// left
					x = leftLeftRotation(x);
				} else {
					x = leftRightRotation(x);

				}
			}

		} else if (value > xVal) {
			x.right = insert(x.right, value);

			if (getHeight(x.right) - getHeight(x.left) > 1) {// right
				if (getHeight(x.right.right) > getHeight(x.right.left)) {// right
					x = rightRightRotation(x);
				} else {
					x = rightLeftRotation(x);
				}
			}
		} else {
			// 重复数据 do nothing
		}

		x.height = reCalcHeight(x);

		return x;

	}

	public Node select(int value) {
		return select(root, value);// work when BST is empty
	}

	private Node select(Node x, int value) {

		if (x == null)
			return null;

		int xVal = x.value;

		if (value < xVal)
			return select(x.left, value);
		else if (value > xVal)
			return select(x.right, value);
		else
			return x;
	}

	public void delete(int value) {
		root = delete(root, value);
	}

	private Node delete(Node x, int value) {

		if (x == null) {
			return null;
		}

		int xVal = x.value;

		if (value < xVal)
			x.left = delete(x.left, value);// 左子树
		else if (value > xVal)
			x.right = delete(x.right, value);// 右子树
		else {
			if (x.right == null) {
				return x.left;
			}
			if (x.left == null) {
				return x.right;
			}

			Node temp = x;// 要被删除的节点，先拿着
			x = min(temp.right); // 获取右子树最小的节点
			x.right = deleteMin(temp.right);// 删除右子树最小节点，并将删除后的树作为x的右子树
			x.left = temp.left;// 原来的左子树保持，作为新根节点的左子树
		}

		// 删除完成，调整平衡性
		x.height = reCalcHeight(x);

		// 失衡
		if (getHeight(x.left) - getHeight(x.right) >= 2) {
			// 删除发生在右子树，模拟插入发生在左子树
			if (getHeight(x.left.left) > getHeight(x.left.right)) {
				// 插入发生在左子树，LL旋转
				return leftLeftRotation(x);
			} else {
				// LR旋转
				return leftRightRotation(x);
			}
		} else if (getHeight(x.left) - getHeight(x.right) <= -2) {
			// 删除发生在左子树，模拟插入发生在右子树
			if (getHeight(x.right.left) > getHeight(x.right.right)) {
				// RL旋转
				return rightLeftRotation(x);
			} else {
				// RR旋转
				return rightRightRotation(x);
			}
		}
		// 未失衡，不做操作
		return x;
	}

	private Node min(Node x) {
		if (x.left == null)
			return x;
		return min(x.left);
	}

	private Node deleteMin(Node x) {

		if (x.left == null)
			return x.right;

		x.left = deleteMin(x.left);

		return x;
	}

	private int getHeight(Node n) {
		if (n == null) {
			return 0;
		}
		return n.height;
	}

	private int reCalcHeight(Node x) {
		return Math.max(getHeight(x.left), getHeight(x.right)) + 1;
	}

	private Node leftLeftRotation(Node x) {// LL旋转
		Node left = x.left;
		x.left = left.right;
		left.right = x;
		x.height = reCalcHeight(x);// 挂了新的子节点，重新计算高度
		left.height = reCalcHeight(left);// 挂了新的子节点，重新计算高度
		return left;
	}

	private Node rightRightRotation(Node x) {// RR旋转
		Node right = x.right;
		x.right = right.left;
		right.left = x;
		x.height = reCalcHeight(x);// 挂了新的子节点，重新计算高度
		right.height = reCalcHeight(right);// 挂了新的子节点，重新计算高度
		return right;
	}

	private Node leftRightRotation(Node x) {// LR旋转，先将左儿子RR旋转，再将根节点LL旋转
		x.left = rightRightRotation(x.left);
		return leftLeftRotation(x);
	}

	private Node rightLeftRotation(Node x) {// RL旋转，先将右儿子LL旋转，再将根节点RR旋转
		x.right = leftLeftRotation(x.right);
		return rightRightRotation(x);
	}

	private class Node {

		private int value;
		private Node left;
		private Node right;
		private int height;

		public Node(int value, int height) {
			super();
			this.height = height;
			this.value = value;
			left = right = null;
		}

		@Override
		public String toString() {
			return +value + "=>{" + left + "," + right + "}";
		}
	}
}

分析

平衡二叉树是一种完美的平衡树，它的查询效率非常的高，为O(N)。但是我们也看到其追求完美代价，那就是各种旋转带来的性能损耗。特别是在写频繁的场景下，树的很多性能消耗在了旋转上，如果读频率不是很高的话，那就得不偿失了。那么有没有没那么完美的二叉树，既兼顾了平衡又在插入删除时没那么复杂的树呢？答案就是红黑树，鉴于篇幅的关系，改天再跟大家分享吧。

喜欢我就关注我吧，如果你觉得这篇文章帮助到你了，还请帮忙转发，让更多人看到吧。