前言
在《一文彻底掌握二叉查找树，非史上最全总结（多图，附代码） 》我们讲了二叉查找树，在文章的最后我们也提到了，二叉查找树查找的效率受到树的深度的影响，最坏情况是O(N)。而二叉查找树的深度是根据数据插入的顺序不同而表现出不同的。那么有没有可能让树的深度尽可能低，从而提高我们查询的效率呢？答案就是今天要讲的平衡二叉树（AVL树）。
定义
AVL树是二叉查找树的一个特例，所以上一篇文章说到的二叉查找树的定义是AVL树定义的前提。在这个前提之下，AVL树再提出了写更加严格的定义。那就是，树的任意节点的子树的高度差都小于等于1。
树的操作
由于AVL树比普通的二叉查找树有个更加苛刻的要求，要求子树的高度差小于等于1。那么在树的插入、删除等操作时将会比普通的二叉查找树更加麻烦。
插入
AVL树插入的之一步其实跟二叉查找树一样，但是插入数据后，可能会导致树失去平衡，那么这时就需要对子树进行旋转了。通过选择来使得树继续保持平衡。
树失去平衡会有四种情况：
节点的左儿子的左子树插入节点，导致左子树比右子树高（LL），如下图树插入节点1之后，6的左子树高度比右子树高2。节点的右儿子的右子树插入节点，导致右子树比左子树高（RR）节点的左儿子的右子树插入节点，导致左子树比右子树高（LR）节点的右儿子的左子树插入节点，导致左子树比右子树高（RL）AVL树失去平衡之后，可以通过旋转使其恢复平衡。四种失去平衡的情况下对应的旋转 *** 分别如下：
(a)LL的旋转，步骤如下：
将根节点的左孩子作为新根节点。将新根节点的右孩子作为原根节点的左孩子。将原根节点作为新根节点的右孩子。伪代码：
// 要旋转的节点为node，其父节点是parent Node temp = node.left; node.left = temp.right; temp.right = node; parent.left = temp;
LL 旋转示意图如下：
(b)RR的旋转，旋转 *** 与LL旋转对称，步骤如下：
将根节点的右孩子作为新根节点。将新根节点的左孩子作为原根节点的右孩子。将原根节点作为新根节点的左孩子。RR旋转示意图如下：
（c)LR的旋转：
LR失去平衡的情况，单旋转不能解决问题，需要进行两次旋转，步骤如下：
根节点的左孩子做一次RR旋转。根节点做一次LL旋转。LR的旋转示意图如下：
(d)RL的旋转：
RL旋转 *** 与LR旋转对称，步骤如下：
根节点的右孩子做一次LL旋转。根节点做一次RR旋转。RL的旋转示意图如下：
删除
平衡二叉树的节点删除操作会比较复杂，我们可以这么分析，左子树上节点的删除相当于我们在右子树上插入了一个新节点，右子树上节点的删除相当于在左子树上插入了一个新节点。我们可以根据这一点进行判断并采取对应的平衡调整操作。
具体做法需要从当前节点判断树是否失去平衡，通过计算左右子树的高度差，判断是哪种失衡。然后运用旋转，将树调整为平衡树。
排序二叉树的删除判断左右子树高度差是否小于2，判断结点是否失衡当前结点失衡，将删除视为另一侧的插入，依照插入的旋转思想进行旋转如此反复直至根节点查询
由于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)。但是我们也看到其追求完美代价，那就是各种旋转带来的性能损耗。特别是在写频繁的场景下，树的很多性能消耗在了旋转上，如果读频率不是很高的话，那就得不偿失了。那么有没有没那么完美的二叉树，既兼顾了平衡又在插入删除时没那么复杂的树呢？答案就是红黑树，鉴于篇幅的关系，改天再跟大家分享吧。
喜欢我就关注我吧，如果你觉得这篇文章帮助到你了，还请帮忙转发，让更多人看到吧。
