什么是平衡二叉树

前言上篇文章里面，我们已经学习了二叉搜索树的相关内容，二叉搜索树有一个缺点，在插入数据是有序的序列（包括升序和降序），会导致二叉树退化成链表，从而导致在查找，删除，添加时的性能均从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字段，用来计算均衡因子使用，此外在插入和删除之后要加上检测平衡的代码，如果发现树失衡了就要及时调整：

代码语言：javascript代码运行次数：0运行复制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

node.height=Math.max(getHeight(node.left),getHeight(node.right))+1;

int balDiff=getBalance(node);

// 左倾斜，右旋 if(balDiff>1&&data

// 右倾斜，左旋

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

return node;

}

private Node delete(Node node, int data){

if(node==null){ System.out.println("要删除的节点不存在"); return null; }else if(datanode.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> levelOrder(Node root) { List result = new ArrayList();

if (root == null) { return result; }

Queue queue = new LinkedList(); queue.offer(root);

while (!queue.isEmpty()) { ArrayList level = new ArrayList(); 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树并不适合需要频繁插入和删除的场景，而红黑树则是权衡了 这种情况，其并不强调严格的平衡性，而是保持一定的平衡性，从而使得在搜索，插入，删除的场景下均有一个不错的速度，这个会在后续的文章中分析。