什么是平衡二叉树
前言
上篇文章里面，我们已经学习了二叉搜索树的相关内容，二叉搜索树有一个缺点，在插入数据是有序的序列（包括升序和降序），会导致二叉树退化成链表，从而导致在查找，删除，添加时的性能均从O（logN）降低为O（N），这是不能接受的。如下图：
究其原因，是因为二叉搜索树退化成链表的时候，树的高度与节点的个数相等，也就是成正比，所以为了优化这种情况，就出现了具有平衡能力的二叉搜索树，其中AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O（logN）。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。
平衡二叉树的性质
平衡二叉树本质上是特殊的二叉搜索树（二叉排序树），它具有二叉搜索树所有的特点，此外它有自己的特别的性质，如下：
（1）它是一棵空树或它的左右两个子树的高度差的绝对值不超过1；
（2）平衡二叉树的左右两个子树都是一棵平衡二叉树。
什么是平衡因子
平衡因子指的是，平衡二叉树在保持平衡的时候，是通过平衡因子来判断的，节点的平衡因子 = 该节点的左子树的高度 - 该节点右子树的高度。只有当值等于-1（右子树的高度大），0（左右子树的高度相等），1（左子树的高度大）的时候，能够代表该子树是平衡的除此之外，就认为该节点已经失衡了，需要旋转来维持平衡，如下图的平衡因子分布情况：
平衡二叉树的旋转分类
平衡二叉树在插入和删除的时候都有可能发生旋转来维持平衡，总得来说，旋转分四种情形：
（1）左旋转
如下图，对二叉搜索树分别插入1,2,3升序序列，会导致树向右倾斜，这个我们需要左旋来平衡树：
第一张图标记了，当插入3之后，根节点1失衡了，因为1节点没有左子树，所以左子树的高度等于0，而右子树的高度等于2，故两者相减得到-2，证明树失衡了，通过向左旋转，调整了root的位置，从而使得树变得均衡了。
（2）右旋转
如下图，对二叉搜索树分别插入3,2,1降序序列，会导致树向左倾斜，这种情况下我们需要向右旋转来平衡树：
在插入1后，树发现失衡了，故而通过向右旋转的方式，来调整平衡。
（3）左右旋转
如下图与（2）的情况类似，但不同的是插入的方式是3,1,2，从而导致最后一个2插入的时候，是在右子树上导致失衡的，这种情况下比前面的稍微复杂，需要旋转两次来调整平衡。
先左旋之后，发现仍然失衡，然后接着右旋才维持平衡。
（4）右左旋转
如下图，对二叉搜索树分别插入1,3,2，与上面的（3）情形正好相反
这种情况下，先右旋然后左旋就可以保持平衡
代码实现
平衡二叉树的代码，其实和二叉搜索树的代码大体一致，包括搜索，插入和删除功能，主要的区别在于在树节点定义上多加了一个height字段，用来计算均衡因子使用，此外在插入和删除之后要加上检测平衡的代码，如果发现树失衡了就要及时调整：
public class AVLTree {
class Node{ int data; Node left; Node right; int height;
public Node(int data) { this.data = data; height = 1; }
}
public int getHeight(Node n){ if(n!=null){ return n.height; } return 0; }
public int getBalance(Node n){ if(n!=null){ return getHeight(n.left) - getHeight(n.right); } return 0; }
public Node rightRotate(Node y){ Node x=y.left; Node T2=x.right;
//rotation x.right=y; y.left=T2;
x.height=Math.max(getHeight(x.left),getHeight(x.right))+1; y.height=Math.max(getHeight(y.left),getHeight(y.right))+1;
return x;
}
public Node leftRotate(Node x){ Node y=x.right; Node T2=y.left;
//Rotation y.left=x; x.right=T2;
//update height
x.height=Math.max(getHeight(x.left),getHeight(x.right))+1; y.height=Math.max(getHeight(y.left),getHeight(y.right))+1;
return y;
}
public Node insert(Node node, int data){ if(node==null){ return new Node(data); }
if(node.data>data){ node.left=insert(node.left,data); }else if(node.data<data){ node.right=insert(node.right,data); }else { return node;// 已经存在 }
node.height=Math.max(getHeight(node.left),getHeight(node.right))+1;
int balDiff=getBalance(node);
// 左倾斜，右旋 if(balDiff>1&&data<node.left.data){ return rightRotate(node); }
// 右倾斜，左旋
if(balDiff<-1&&data> node.right.data){ return leftRotate(node); }
// 左倾斜，先左旋，再右旋 if(balDiff>1&&data>node.left.data){ node.left=leftRotate(node.left); return rightRotate(node); }
// 右倾斜，先右旋，再左旋 if(balDiff<-1&&data<node.right.data){ node.right=rightRotate(node.right); return leftRotate(node); }
return node;
}
private Node delete(Node node, int data){
if(node==null){ System.out.println("要删除的节点不存在"); return null; }else if(data<node.data){ node.left=delete(node.left,data); }else if(data>node.data){ node.right=delete(node.right,data); }else{//叶子节点，或者只拥有一个孩子节点的处理逻辑是一样的 if(node.left==null){ return node.right; }else if(node.right==null){ return node.left; }else{ //到这一步说明删除的节点拥有2个孩子节点 //找到剩下左子树里面最大的节点，或者找到右子树里面最小的节点，这里使用的是前者 //使用最大值覆盖当前要被删除的节点的值 node.data=retrieveData(node.left); //最后删除，在剩下左子树里面刚才被替换到最大值的节点 node.left=delete(node.left,node.data); }
}
if(node==null) return null;
node.height=Math.max(getHeight(node.left),getHeight(node.right))+1;
int balDiff=getBalance(node);
// 左倾斜，右旋 if(balDiff>1&&getBalance(node.left)>=0){ return rightRotate(node); }
// 右倾斜，左旋
if(balDiff<-1&&getBalance(node.right)<=0){ return leftRotate(node); }
// 左倾斜，先左旋，再右旋 if(balDiff>1&&getBalance(node.left)<0){ node.left=leftRotate(node.left); return rightRotate(node); }
// 右倾斜，先右旋，再左旋 if(balDiff<-1&&getBalance(node.right)>0){ node.right=rightRotate(node.right); return leftRotate(node); }
return node; }
private int retrieveData(Node p) { while (p.right != null) p = p.right;
return p.data; }
public void inorder(Node root) { if (root != null) { inorder(root.left); System.out.print(" " + root.data); inorder(root.right); } }
public List<List<Integer>> levelOrder(Node root) { List result = new ArrayList();
if (root == null) { return result; }
Queue<Node> queue = new LinkedList<Node>(); queue.offer(root);
while (!queue.isEmpty()) { ArrayList<Integer> level = new ArrayList<Integer>(); int size = queue.size(); for (int i = 0; i < size; i++) { Node head = queue.poll(); level.add(head.data); if (head.left != null) { queue.offer(head.left); } if (head.right != null) { queue.offer(head.right); } } result.add(level); } System.out.println(result); return result; }
public static void main(String[] args) {
Node root = null; AVLTree i = new AVLTree(); testCase2(root,i); }
private static void testCase1(Node root,AVLTree i ){ root = i.insert(root, 1); root = i.insert(root, 2); root = i.insert(root, 3);
root = i.insert(root, 4); root = i.insert(root, 5); root = i.insert(root, 6); root = i.insert(root, 7); root = i.insert(root, 8); i.levelOrder(root); root = i.delete(root,5); i.levelOrder(root); }
private static void testCase2(Node root,AVLTree i ){ root = i.insert(root, 50); root = i.insert(root, 25); root = i.insert(root, 75);
root = i.insert(root, 15); root = i.insert(root, 40); root = i.insert(root, 60); root = i.insert(root, 80); root = i.insert(root, 35); root = i.insert(root, 55); root = i.insert(root, 65); root = i.insert(root, 90); root = i.insert(root, 62); i.levelOrder(root);
root = i.delete(root,15); i.levelOrder(root);
}
}`
平衡二叉树的优缺点
优点： 通过严格的平衡性保证，其搜索性能在最差的情况下的也得达到O（logn）
缺点： 为了保证严格的均衡性，导致在插入和删除的时候需要额外花费时间旋转来调整平衡度，从而使得插入和删除的性能下降
总结
本文主要介绍了平衡二叉树的相关内容，AVL平衡二叉树很好的解决了二叉搜索树在遇到有序序列性能退化为O（N）的情况，使得在最坏情况下的搜索效率仍然能够达到O（logN），但这种优化是牺牲了插入和删除的性能换来的，故而AVL树并不适合需要频繁插入和删除的场景，而红黑树则是权衡了 这种情况，其并不强调严格的平衡性，而是保持一定的平衡性，从而使得在搜索，插入，删除的场景下均有一个不错的速度，这个会在后续的文章中分析。