一、平衡二叉树起步

1. 基本概念

平衡二叉树（AVL）可以很好地解决二叉搜索树中退化为链表的问题，从上一篇文章了解到二叉搜索树的性能取决于树的形状，当我们以升序或者降序的顺序往二叉搜索树中插入数据时，将会造成类似下图右的情况，此时时间复杂度为O(n)，二叉树退化为链表，没有得到二叉树应有的效率，所以平衡二叉树应运而生。

首先平衡二叉树也是一颗二叉搜索树，它也满足二叉搜索树的特性。但除此之外，它还有一个重要的特性：每一个节点的左子树和右子树的高度差最多为1。因为这个高度差限制从而避免了上述的最坏情况，因此查找、插入和删除的效率也可以保持在O(lg n)。

2. 平衡因子

平衡因子：为了反映每个节点的高度差，平衡二叉树在二叉搜索树的基础上，在节点中添加了一个新的域，称为平衡因子（BF）。平衡因子代表了当前节点左子树深度减去右子树深度的值。根据前面平衡二叉树所提及的性质，我们可以直到，对于平衡二叉树，每个节点中的平衡因子只能是-1、0、1这三种可能。

接下来简单示例一下：

• 图1是平衡二叉树，树中所有节点的平衡因子都在-1、0、1这个集合中。同样图4也是平衡二叉树；
• 图2不是平衡二叉树，甚至不是二叉搜索树，59大于58，但是确是58这个节点的右子树；
• 图3不是平衡二叉树，58这个节点的左子树深度减去右子树深度等于2，不属于-1、0、1这个集合；

二、 旋转

前面提到，平衡二叉树中每个节点的平衡因子需要控制在{-1、0、1}三个数值中，那么当某个节点的平衡因子不属于这三个值，就需要通过某种操作将平衡因子控制在{-1、0、1}中，这种操作就称之为旋转。旋转根据情况可分为左旋转和右旋转，现在先来了解一下什么是旋转。

如图1所示，当1这个节点插入树中时，3这个节点的左子树深度减去右子树深度为2，那么此时就需要旋转，将图1修正到图2的形式；当4节点插入时，平衡因子还在范围内，所以不用进行旋转；

当插入节点5之后，节点3的平衡因子变化成了-2，此时需要通过对节点3进行左旋转修正为上图图5的形式；现在对旋转应该有了大致的了解，接下来介绍旋转的几种情况：

1. LL型

当我们向一个已经达到平衡状态的树中插入9这个元素，如上图所示。此时16这个点的左子树减去右子树等于2，所以需要将以16为根节点的这个子树进行右旋转，达到有图的平衡状态，这种情况子树以及子树的子树都在左边的情况，称为LL型，需要用到右旋转操作，简单用伪代码示例以下：

public void rotateRight(Node h) { // h为失衡节点，下面简称根节点Node x = h.left; // 根结点的左孩子保存为xh.left = x.right; // 根结点左孩子的右孩子挂到根结点的左孩子上x.right = h; // 根结点挂到根结点左孩子的右孩子上h = x; // 根结点的左孩子代替h称为新的根结点
}

当然实际的代码比上面的伪代码复杂些，这里简单示例一下，后面再详细说明。

2. RR型

当向一个已经达到平衡状态的树中插入26这个元素，如上图所示，此时7这个节点的左子树减去右子树等于-2，处于非平衡状态，需要将以7为根节点的树进行左旋转，如上图所示。

3. LR型

LR型与RL稍微比较难以理解些，上图平衡树在插入7后，16这个节点达到失衡状态，此时不能直接将以16为根节点的子树进行右旋转，否则会像上图右边所示，7比3大，却在3的左边，这样不符合二叉搜索树的要求。所以要先进行左旋转（注意：不是以16这个节点为根的子树进行左旋转，而是16这个节点的左子树进行左旋转），然后再以16为根的子树进行右旋转。

4. RL型

RL型的情况与LR型的情况差不多，不能直接进行旋转，需要现对失衡节点的右子树进行右旋转，然后再对以失衡节点为根的子树进行左旋转。

5. 小结

对上面所述的四种情况，我在网上看见一张不错的图，用以小结一下：

上图来源：https://blog.csdn.net/Ascend2015/article/details/87796641

三、代码解析

1. 平衡调整

在插入完数据后，对节点进行平衡因子计算，之后再判断是左子树还是右子树高，在通过平衡因子判断是是否为LR型或RL型，再进行左旋右旋的操作，代码如下所示：其中node.depth是指该节点的深度，用以被其父节点计算平衡因子，BF则为平衡因子。

// 从插入的过程回溯回来后，计算平衡因子
node.depth = calcDepth(node);
node.BF = calcBF(node);if (node.BF >= 2) { // 左子树高，可能是LL型或LR型if (node.left.BF == -1) { // 判断是否是LR型// LR型的话，需要先进行左旋LeftRotate(node.left);}// 右旋RightRotate(node);
}if (node.BF <= -2) { // 左子树高，可能是RR型或RL型if (node.right.BF == 1) { // 判断是否是RL型// RL型的话，需要先进行右旋RightRotate(node.right);}// 左旋LeftRotate(node);
}

2. 计算平衡因子

计算平衡因子的代码实现十分简单，就是用节点的左子树高度减去右子树高度

// 计算传入节点处的平衡因子
private int calcBF(Node node) {int left_depth, right_depth; // 定义左右子树的高度left_depth = node.left == null ? 0 : node.left.depth;right_depth = node.right == null ? 0 : node.right.depth;return left_depth - right_depth;
}

3. 计算节点高度

计算节点的深度，就是将左右节点中较高的一边的高度再加上1，即为当前节点的高度了。

// 计算深度
private int calcDepth(Node node) {int depth = 0;if (node.left != null) {depth = node.left.depth;}if (node.right != null && depth < node.right.depth) {depth = node.right.depth;}return ++depth;
}

四、测试代码

以下为测试代码，写得匆忙，有错请指出。

public class AVLTree<Key extends Comparable<Key>, Value> {private Node root;private class Node {private Key key;private Value value;private Node parent, left, right; // 父节点，左右子节点private int depth; // 定义深度private int BF; // 定义平衡因子public Node(Key key, Value value) {this.key = key;this.value = value;depth = 1;BF = 0;}}// 插入数据public void put(Key key, Value value) {if (root == null) { // root为空，新插一个root = new Node(key, value);}put(root, key, value);}private Node put(Node node, Key key, Value value) {if (node == null) {return new Node(key, value); // 新建一个节点}int cmp = key.compareTo(node.key);if (cmp < 0) {// 在node的左子树插入node.left = put(node.left, key, value);node.left.parent = node;} else if (cmp > 0) {// 在node的右子树插入node.right = put(node.right, key, value);node.right.parent = node;} else {// 当前键已经存在，则更新当前键对应的值node.value = value;}// 从插入的过程回溯回来后，计算平衡因子node.depth = calcDepth(node);node.BF = calcBF(node);if (node.BF >= 2) { // 左子树高，可能是LL型或LR型if (node.left.BF == -1) { // 判断是否是LR型// LR型的话，需要先进行左旋LeftRotate(node.left);}// 右旋RightRotate(node);}if (node.BF <= -2) { // 左子树高，可能是RR型或RL型if (node.right.BF == 1) { // 判断是否是RL型// RL型的话，需要先进行右旋RightRotate(node.right);}// 左旋LeftRotate(node);}// 平衡本节点后，重新计算平衡因子与深度node.BF = calcBF(node);node.depth = calcDepth(node);return node;}// 计算传入节点处的平衡因子private int calcBF(Node node) {int left_depth, right_depth; // 定义左右子树的高度left_depth = node.left == null ? 0 : node.left.depth;right_depth = node.right == null ? 0 : node.right.depth;return left_depth - right_depth;}// 计算深度private int calcDepth(Node node) {int depth = 0;if (node.left != null) {depth = node.left.depth;}if (node.right != null && depth < node.right.depth) {depth = node.right.depth;}return ++depth;}// 左旋 // 等等这里画一幅图private void LeftRotate(Node node) {Node parent = node.parent;int flag = 0;if (parent != null) {flag = node.equals(parent.left) ? 0 : 1;}Node temp = node.right;if (temp.left != null) {node.right = temp.left;node.right.parent = node;} else {node.right = null;}temp.left = node;node.parent = temp;temp.parent = parent;if (parent != null) {if (flag == 0) parent.left = temp;else parent.right = temp;} else {// 如果等于null，证明原来的node是root，所以旋转后的temp得作为rootroot = temp;}// 重新计算平衡因子与深度node.BF = calcBF(node);node.depth = calcDepth(node);temp.BF = calcBF(temp);temp.depth = calcDepth(temp);}// 右旋private void RightRotate(Node node) {Node parent = node.parent;int flag = 0; // 用来标识当前节点是其父节点的左孩子还是右孩子节点，0表示左孩子，1表示右孩子if (parent != null) {flag = node.equals(parent.left) ? 0 : 1;}Node temp = node.left;if (temp.right != null) {node.left = temp.right;node.left.parent = node;} else {node.left = null;}temp.right = node;node.parent = temp;temp.parent = parent;if (parent != null) {if (flag == 0) parent.left = temp;else parent.right = temp;} else {// 如果等于null，证明原来的node是root，所以旋转后的temp得作为rootroot = temp;}// 重新计算平衡因子与深度node.BF = calcBF(node);node.depth = calcDepth(node);temp.BF = calcBF(temp);temp.depth = calcDepth(temp);}public void levelOrderTraversal() {levelOrderTraversal(root);}// 层序遍历private void levelOrderTraversal(Node root) {Queue<Node> queue = new LinkedList<Node>();queue.offer(root);while (!queue.isEmpty()) {Node node = queue.poll();System.out.print(node.key + "\t BF:" + node.BF + " \t");if (node != root) {System.out.print("parent:" + node.parent.key);}System.out.println();if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}}public static void main(String[] args) {AVLTree<Integer, String> tree = new AVLTree();tree.put(7, "1");tree.put(3, "2");tree.put(11, "3");tree.put(26, "6");tree.put(9, "4");tree.put(16, "5");tree.levelOrderTraversal();}
}