程序员的内功心法-AVL树

直面弱点，不再逃避！！！

接上篇文章《二叉搜索树》了解到二叉搜索树在极端情况也不能满足我们对于查询性能的要求。

二叉树的一些统计特性

• 第n层最多的节点个数2n-1
• 高度为h的二叉树，最多包含2h-1个节点，所以n个节点的二叉树的最小高度是log2n + 1
• 查找成功时，查找次数不会超过树的高度h

二叉树查询性能的衡量

我们下面来使用 A - H字符来观察二叉搜索树在不同的插入顺序下构造的树的结果

自然顺序的平均查找长度为ASL=(1+ 2 + 3 + 4+ 5+ 6+ 7 +8) / 8 = 4.5

计算特定顺序的平均查找长度ASL=(1 + 2*2 + 3*4 + 4*1) / 8 = 2.6

当我们数据相同，但是采用不同的插入顺序，使平均查找长度不一样。所以我们要解决这个问题，先观察两个初始化方式两个树的特点，大致发现使用特定顺序初始化的树，感觉树的节点分布比较平衡。由于统计特点3和特点2，我们希望n个节点的二叉树的接近log2n + 1，那么我们就可以最大化的提升查询性能.

所以为了解决这个问题，我们引入新的二叉搜索树实现-平衡二叉树（AVL树）

AVL树内容定义

• 平衡因子BalanceFactor：左右子树的高度差BF=HL - HR
• 规定左右子树的高度差的绝对值不超过1 |BF| ≤ 1

节点定义

原有节点的基础上增加height属性

class AVLNode<T extends Comparable<T>> {

    private T data;

    //左节点
    private AVLNode<T> left;

    //右节点
    private AVLNode<T> right;

    //当前节点的高度
    private int height;
}

高度计算

由于平衡二叉树的平衡指高度方面的平衡，我们先来计算树的高度

树的高度H指：左HL右HR子树高度的最大值 + 1

}

查找

由于平衡二叉树也是二叉查找树的一种，查询方式和二叉搜索树相同，不再赘述。

调整平衡

为了保证左右平衡，所以我们一系列的操作来维持左右子树的高度在BF规定的范围之内

插入分类

空树时，直接初始化为根结点。

针对作为子节点的插入，插入节点只能为被插入节点的左节点B或者右节点F。而被插入节点D可以是其父节点G的左节点或其父节点A的右节点。所以我们将所有情况分为4类：GDB路径(LL插入)、GDF路径(LR插入)、ADF路径(RR插入)、ADB路径(RL插入)

接下来我们将处理所有的情况

RR插入

当插入节点在右子树的右节点上（ADF路径）

操作步骤：

1. 将右子节点D作为根节点
2. 原根节点A作为新根节点D的左子节点
3. 将D节点的左子节点B设置为原根节点A的右子节点

实现代码如下：

AVLNode<T> singleRightRotation(AVLNode<T> node) {
    AVLNode<T> result = node.getRight();
    AVLNode<T> left = result.getLeft();
    node.setRight(left);
    result.setLeft(node);
    return result;
}

LL插入

当插入的节点在左子树的左节点上（GDB路径）

操作步骤：

1. 将左子节点D作为根结点
2. 原根节点G作为新根节点D的右子节点
3. 将D节点的右子节点F作为原结点G的左子节点

实现代码：

}

RL插入

当插入的节点在右子树的左节点上（ADB路径）

操作步骤：

• 针对A节点的右子节点D做左旋转
• 针对A节点做右旋转

实现代码：

AVLNode<T> doubleRightLeftRotation(AVLNode<T> node){
    AVLNode<T> right = singleLeftRotation(node.getRight());
    node.setRight(right);
    return singleRightRotation(node);
}

LR插入

当插入的节点在右子树的左节点上（GDF路径）

操作步骤：

• 针对G节点的左子节点D做右旋转
• 针对G节点做左旋转

实现代码：

AVLNode<T> doubleLeftRightRotation(AVLNode<T> node) {
    AVLNode<T> left = singleRightRotation(node.getLeft());
    node.setLeft(left);
    return singleLeftRotation(node);
}

删除节点

我们在删除节点时，思路：

• 叶子节点直接删除
• 包含一个子节点，将子节点替换到父节点
• 包含两个子节点，使用后继节点替换被删除节点，删除后继节点即可 更详细的可以回顾下《二叉搜索树》的内容

平衡调整的思路：节点被删除后，相当于在兄弟节点插入新的节点

代码如下：

AVLNode<T> delete(AVLNode<T> node, T data) {

由于AVL是一个高度严格平衡的二叉搜索树，查找效率在log2n级别。但是在维护节点高度平衡时，需要进行旋转操作(插入时最多两次旋转；删除节点时AVL树需要调整整个查询路径的高度平衡，最多需要log2n次旋转)

后面，我们将介绍另外一种平衡搜索二叉树(红黑树)！

欢迎大家关注留言分享和我交流！