平衡二叉搜索树 – AVL 树

2180

前言

二叉搜索树的复杂度

对于 图1 的二叉搜索树，添加、删除、查询的复杂度为：O(h)，h 为二叉树高度，也等于 O(logn)，n 为二叉树的节点个数。效率比较高。此时查找元素 10，需要 3 次。
image.png

但是上图中元素如果是从小到大添加的节点，这个时候二叉树会退化成链表 如图2，此时同样查找元素 10，则需要 7 次。

image.png

当节点 n 比较大的时候，上面两种情况的效率差别非常大。

二叉搜索树的复杂度和其高度相关，要保证高效率，需要降低二叉搜索树的高度。
为了更高效的使用二叉搜索书，防止退化成链表，让其复杂度维持在 O(logn) ，可以使用平衡二叉搜索树（AVL）。

平衡：当节点数量固定时，左右子树的高度越接近，这棵二叉树就越平衡（高度越低）。

image.png

最理想的平衡，满二叉树，高度最小（高度差最小）。

image.png

平衡二叉搜索树

平衡二叉搜索树，简称平衡二叉树，英文名称 AVL树。
平衡因子：某结点的左右子树的高度差。
平衡二叉树的特点：

  • 每个节点的平衡因子只可能是 1、0、-1（绝对值 ≤ 1，如果超过 1，称之为“失衡”）
  • 每个节点的左右子树高度差不超过 1
  • 搜索、添加、删除的时间复杂度是 O(logn)

image.png

image.png

添加导致的失衡
下图左边为一棵 AVL树，往它添加元素 11 之后，导致节点 6 的平衡因子变成 -2，此时变为非平衡二叉树，即树失衡。

image.png

添加元素可能导致AVL树失衡，在最坏的情况下，可能会导致所有添加节点祖先节点（不包括添加节点的父节点）都失衡。

添加节点的父节点、非祖先节点，都不可能失衡。

当添加元素导致 AVL树 失衡时，我们需要进行适当旋转操作，使其恢复平衡。

最小失衡子树：在新插入的结点向上查找，以第一个平衡因子的绝对值超过 1 的结点为根的子树称为最小不平衡子树。如上图（右边非AVL树）中，以节点 6 为父节点的那棵树就称为最小失衡子树。

当添加节点导致平衡二叉树出现多棵子树失衡时，只要调整最小的不平衡子树，即可使其恢复为平衡的树。

当插入新结点导致不平衡时, 我们需要找到距离新节点最近的不平衡结点为轴来转动 AVL树来达到平衡。

LL – 右旋转

对于 LL 型，需要执行右旋转操作

LL 是指导致祖父节点失衡的节点是祖父节点的左子树的左子树（left -> left）。

右旋操作思路如下：
1）新插入的节点往上查找，找打第一个失衡的节点（姑且称为 g），以该节点为根节点的子树为最小失衡子树；
2）将失衡节点的左孩子的右子树变成该节点的左子树（g.left = g.left.right）；
3）将失衡节点作为左孩子节点的右子树（g.left.right = g）；
4）失衡节点的左孩子作为最小失衡子树的根节点（失衡节点root = g.left）。

还需要注意维护的内容：相关节点的 parent 属性 和 高度。

如下图，前面的 AVL树 在添加元素 4 之后导致，祖父节点（此处为根节点）8 失衡，而导致 8 失衡的节点是 8 的左子树的左子树（即 LL 型）

image.png

对于 LL 型需要执行右旋转即可使其恢复平衡，如下图：

image.png

RR – 左旋转

对于 RR 型，需要执行左旋转即可使其恢复平衡。

RR 是指导致祖父节点失衡的节点是祖父节点的右子树的由子树（right -> right）。

左旋操作思路如下：
1）新插入的节点往上查找，找打第一个失衡的节点（姑且称为 g），以该节点为根节点的子树为最小失衡子树；
2）将失衡节点的右孩子的左子树变成该节点的右子树（g.right = g.right.left）；
3）将失衡节点作为右孩子节点的左子树（g.right.left = g）；
4）失衡节点的右孩子作为最小失衡子树的根节点(失衡节点root = g.right)。

如下图，前面的 AVL树 在添加元素 9 之后导致，祖父节点（此处为根节点）5 失衡，而导致 5 失衡的节点是 5 的右子树的右子树（即 RR 型）。
image.png

左旋转使其恢复平衡：
image.png

LR – 左旋转、右旋转

LR 是指导致祖父节点失衡的节点是祖父节点的左子树的右子树（left -> right）。

对于 LR 型，需要先后执行左旋和右旋操作
操作思路如下：
1）新插入的节点往上查找，找打第一个失衡的节点（姑且称为 g）；
2）对失衡节点的左孩子进行左旋操作，此时转化为 RR – 左旋转；
3）再对失衡节点做右旋操作，此时转化为 LL – 右旋转。

如下图，往平衡二叉树添加节点 7 后，祖父节点 8 失衡，即为：LR 型（添加的新节点为失衡节点的左子树的右子树）。

image.png

先对失衡节点 8 的左孩子 5 进行左旋操作，然后再对失衡节点 8 进行右旋操作，其过程如下图所示：
image.png

RL – 右旋转、左旋转

对于 RL 型，需要执行左旋转操作

RL 是指导致祖父节点失衡的节点是祖父节点的左子树的右子树（right -> left）。

对于 RL 型，需要先后执行右旋和左旋操作。
操作思路如下：
1）新插入的节点往上查找，找打第一个失衡的节点（姑且称为 g）；
2）对失衡节点的右孩子进行右旋操作，此时转化为 LL – 右旋转；
3）再对失衡节点做左旋操作，此时转化为 RR – 左旋转。

如下图，往平衡二叉树添加节点 6 后，祖父节点 5 失衡，即为：RL 型（添加的新节点为失衡节点的右子树的左子树）。

image.png

先对失衡节点 5 的右孩子 8 进行右旋操作，然后再对失衡节点 5 进行左旋操作，其过程如下图所示：

image.png

代码实现

AVL树节点结构

/**
 * AVL 树节点类
 * @param <E> 泛型
 */
private static class AVLNode<E> {
    E element; //节点数据
    AVLNode<E> left; //左节点
    AVLNode<E> right; //右节点
    AVLNode<E> parent; //父节点
    int height; //节点高度

    public AVLNode(E element, AVLNode<E> parent) {
        this.element = element;
        this.parent = parent;
    }

    public boolean hasTwoChildren() {
        return left != null && right != null;
    }

    /**
     * 是否是左子节点
     */
    public boolean isLeftChild() {
        return (parent != null && this == parent.left);
    }

    /**
     * 是否是右子节点
     */
    public boolean isRightChild() {
        return (parent != null && this == parent.right);
    }

    /**
     * 获取节点的平衡因子
     */
    public int balanceFactor() {
        int leftHeight = left == null ? 0 : left.height;
        int rightHeight = right == null ? 0 : right.height;
        return leftHeight - rightHeight;
    }

    /**
     * 更新节点高度
     */
    public void updateHeight() {
        int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
        int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
        height = Math.max(leftHeight, rightHeight) + 1;
    }

    public AVLNode<E> tallerChildNode() {
        int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
        int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
        if (leftHeight > rightHeight) return left;
        if (leftHeight < rightHeight) return right;
        return left;
    }

}
复制代码

AVL树 同二叉搜索树设计结构类似

public class AVLTree<E> {

    private int size; // 树元素大小
    private AVLNode<E> root; // 根节点

    private Comparator<E> comparator; // 比较器，可由外部控制比较器规则

    // 外部不传入比较器规则，则使用默认的存入节点的对象实现的比较规则
    public AVLTree() {
        this(null);
    }

    // 外部传入比较器规则，则使用传入的比较规则
    public AVLTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    // 元素的数量
    public int size() {
        return size;
    }

    // 是否为空
    public boolean isEmpty() {
        return size == 0;
    }
}
复制代码

元素添加

/**
 * 添加元素
 * 对比二叉搜索树，则在添加节点之后，需要恢复树的平衡
 */
public void add(E element) {
    elementNotNullCheck(element);

    // 添加根节点
    if (root == null) {
        root = new AVLNode<>(element, null);
        size++;

        // 添加元素之后需要恢复平衡
        balanceAfterAdd(root);
        return;
    }

    // 添加的不是第一个节点
    // 1.找到父节点
    AVLNode<E> parent = root;
    AVLNode<E> node = root;
    int cmp = 0;
    while (node != null) {
        // 保存父节点，如果此时不保存的话，在 while 循环发现 node == null 的时候，跳出循环
        parent = node;

        cmp = compare(element, node.element);
        if (cmp > 0) {
            node = node.right;
        } else if (cmp < 0) {
            node = node.left;
        } else { // 相等
            node.element = element;
            return;
        }
    }

    // 2.看看插入到父节点的哪个位置
    AVLNode<E> newNode = new AVLNode<>(element, parent);
    if (cmp > 0) {
        parent.right = newNode;
    } else {
        parent.left = newNode;
    }
    size++;

    // 添加元素之后需要恢复平衡
    balanceAfterAdd(newNode);
}

/**
 * 添加元素之后，恢复平衡
 */
private void balanceAfterAdd(AVLNode<E> node) {
    while ((node = node.parent) != null) {
        // 节点是否平衡
        if (isBalance(node)) {
            // 更新节点高度
            node.updateHeight();

        } else {
            // 节点不平衡，则需要回复平衡
            rebalance(node);
            // 最小失衡树回复平衡，则整棵树恢复平衡跳出循环
            break;
        }
    }
}

/**
 * 恢复平衡
 */
private void rebalance(AVLNode<E> node) {
    AVLNode<E> subNode = node.tallerChildNode();
    AVLNode<E> subSubNode = subNode.tallerChildNode();
    if (subNode.isLeftChild()) { // L
        if (subSubNode.isLeftChild()) { // LL - 左旋转
            rotateRight(node);
        } else { // LR - 子节点左旋转，然后失衡节点右旋转
            rotateLeft(subNode);
            rotateRight(node);
        }
    } else { // R
        if (subSubNode.isLeftChild()) { // RL
            rotateRight(subNode);
            rotateLeft(node);
        } else { // RR
            rotateLeft(node);
        }
    }
}

/**
 * 左旋转 - RR 型
 */
private void rotateLeft(AVLNode<E> node) {
    AVLNode<E> subNode = node.right;
    AVLNode<E> subSubNode = subNode.left;
    node.right = subSubNode;
    subNode.left = node;

    // 让subNode成为最小失衡子树的根节点
    subNode.parent = node.parent;
    if (node.isLeftChild()) {
        node.parent.left = subNode;
    } else if (node.isRightChild()) {
        node.parent.right = subNode;
    } else {
        root = subNode;
    }

    // 更新 subSubNode 的 父节点
    if (subSubNode != null) {
        subSubNode.parent = node;
    }

    // 更新 node 的父节点
    node.parent = subNode;

    // 更新节点的高度
    node.updateHeight();
    subNode.updateHeight();
}

/**
 * 右旋转 - LL 型
 */
private void rotateRight(AVLNode<E> node) {
    AVLNode<E> subNode = node.left;
    AVLNode<E> subSubNode = subNode.right;
    node.left = subSubNode;
    subNode.right = node;

    // 让subNode成为最小失衡子树的根节点
    subNode.parent = node.parent;

    if (node.isLeftChild()) {
        node.parent.left = subNode;
    } else if (node.isRightChild()) {
        node.parent.right = subNode;
    } else {
        root = subNode;
    }

    // 更新 subSubNode 的 父节点
    if (subSubNode != null) {
        subSubNode.parent = node;
    }

    // 更新 node 的父节点
    node.parent = subNode;

    // 更新节点的高度
    node.updateHeight();
    subNode.updateHeight();
}

/**
 * 节点是否平衡
 */
private boolean isBalance(AVLNode<E> node) {
    return Math.abs(node.balanceFactor()) <= 1;
}


/******************** 我是分割线（下面是辅助的相关方法）********************/

/**
 * 元素空（null）检查
 * @param element 元素
 */
private void elementNotNullCheck(E element) {
    if (element == null) {
        throw new IllegalArgumentException("element must not be null");
    }
}

/**
 * 节点值比较
 * @param e1
 * @param e2
 * @return 返回值等于0，代表e1 == e2；返回值大于0，代表e1 > e2；返回值小于0，代表e1 < e2；
 */
private int compare(E e1, E e2) {
    // 外部传入了可比较器则使用传入的可比较器
    if (this.comparator != null) {
        return comparator.compare(e1, e2);
    }

    // 外部未可比较器则使用e1对应类实现的Comparable的比较器，因为二叉搜索树的节点必须存放可比较的对象元素
    return ((Comparable<E>)e1).compareTo(e2);
}
复制代码

元素删除

AVL 树在删除节点可能会导致删除节点的上面的一个父节点（或父节点的父节点…）失衡，因此需要在删除节点后重新检查平衡性并使其恢复平衡。

只可能会导致父节点或祖父节点失衡（但只有一个节点失衡），让父节点恢复平衡后，可能会导致更高层的祖先节点失衡【最多需要 O(logn) 次调整】。

/**
 * 删除元素
 */
public void remove(E element) {
    // 通过元素值查找节点
    AVLNode<E> node = node(element);
    if (node == null) return;
    size--;
    if (node.hasTwoChildren()) { // 度为2的节点
        // 找到后继结点
        AVLNode<E> s = successor(node);
        // 用后继结点的值覆盖读为2的节点的值
        node.element = s.element;
        // 删除后继结点，这里只需要将node指向s，后面代码统一删除 node 即可
        node = s;
    }

    // 删除 node 节点（此时 node 节点的度必然是 0 或者 1，因为node的度未2的情况，上面已经特殊处理了）
    AVLNode<E> replaceNode = node.left != null ? node.left : node.right;
    if (replaceNode != null) { // node 是度为1的节点，使用子节点替代replaceNode替换node的位置
        // 更改 parent
        replaceNode.parent = node.parent;

        if (node.parent == null) { // 删除的是根节点
            root = replaceNode;
        }

        // 更改parent的left、right指向
        if (node == node.parent.left) {
            node.parent.left = replaceNode;

        } else if (node == node.parent.right) {
            node.parent.right = replaceNode;
        }

        // 删除节点之后恢复平衡
        balanceAfterRemove(node);

    } else if(node.parent == null) { // node是叶子节点且根节点
        root = null;

        // 删除节点之后恢复平衡
        balanceAfterRemove(node);

    } else { // node 是叶子节点但不是根节点
        if (node == node.parent.right) {
            node.parent.right = null;
        } else {
            node.parent.left = null;
        }

        // 删除节点之后恢复平衡
        balanceAfterRemove(node);
    }
}

/**
 * 删除节点后恢复平衡
 * 注意:删除节点后需要恢复所有非平衡节点
 */
private void balanceAfterRemove(AVLNode<E> node) {
    while ((node = node.parent) != null) {
        if (isBalance(node)) {
            node.updateHeight();
        } else {
            // 需要恢复所有失衡节点，这里对比添加没有 break
            rebalance(node);
        }
    }
}

/**
 * 通过值找到节点
 */
private AVLNode<E> node(E element) {
    AVLNode<E> node = root;
    while (node != null) {
        int cmp = compare(element, node.element);

        // 相等（即找到）直接返回
        if (cmp == 0) return node;

        // 查询元素比节点值大，则继续查找节点的右子树
        if (cmp > 0) {
            node = node.right;
        } else {
            node = node.left;
        }
    }

    // while 循环结束，未查到对应节点
    return null;
}

/**
 * 获取一个节点的后继结点
 */
private AVLNode<E> successor(AVLNode<E> node) {
    if (node == null) return null;

    // 右子树不为空，前驱结点在右子树中（right.left.left...）
    if (node.right != null) {
        AVLNode<E> p = node.right;
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }

    // 右子树为空，从父节点、祖父节点..中寻找前驱结点
    while (node.parent != null && node == node.parent.right) {
        node = node.parent;
    }
    return node.parent;
}
复制代码

至此，AVL 树的相关接口已经基本实现。

© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
代码人生
喜欢就支持一下吧
点赞0 分享
AI-robot的头像-一一网
asgbookphp ‘index.php’ 跨站脚本攻击漏洞-一一网
asgbookphp ‘index.php’ 跨站脚本攻击漏洞
asgbookphp ‘index.php’ 跨站脚本攻击漏洞
14年前 2.6W+
机器学习之随机森林回归篇（RandomForestRegressor）-一一网
机器学习之随机森林回归篇（RandomForestRegressor）
机器学习之随机森林回归篇（RandomForestRegressor）
4年前 4225
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS-一一网
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS
4年前 3916
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞-一一网
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞
19年前 3842
Wireshark之抓包文件保存-一一网
Wireshark之抓包文件保存
Wireshark之抓包文件保存
4年前 3408
支付宝生活号H5接入支付宝支付流程-一一网
支付宝生活号H5接入支付宝支付流程
支付宝生活号H5接入支付宝支付流程
3年前 3152
相关推荐
开源浪潮下程序员的职业规划和成长-一一网
开源浪潮下程序员的职业规划和成长
开源浪潮下程序员的职业规划和成长
4年前 1487
技术实践丨如何解决异步接口请求快慢不均导致的数据错误问题？-一一网
技术实践丨如何解决异步接口请求快慢不均导致的数据错误问题？
技术实践丨如何解决异步接口请求快慢不均导致的数据错误问题？
4年前 1439
mac命令行设置代理，别挡着我起飞-一一网
mac命令行设置代理，别挡着我起飞
mac命令行设置代理，别挡着我起飞
4年前 1349
Linux纯命令行玩转谷歌浏览器：安装、更新、搜索、截图-一一网
Linux纯命令行玩转谷歌浏览器：安装、更新、搜索、截图
Linux纯命令行玩转谷歌浏览器：安装、更新、搜索、截图
4年前 981
WordPress教程 – WordPress新手指南（2021）-一一网
WordPress教程 – WordPress新手指南（2021）
WordPress教程 – WordPress新手指南（2021）
4年前 918
DBLP数据集处理-一一网
DBLP数据集处理
DBLP数据集处理
4年前 854
搜索
开启精彩搜索
世界，您好！-一一网
3.7W+人已阅读
世界，您好！
TOP1
番茄社区无限观看+付费视频破解教程-一一网
番茄社区无限观看+付费视频破解教程
5年前3.2W+人已阅读
TOP2
香蕉视频v3.8.3_VIP会员破解教程-一一网
香蕉视频v3.8.3_VIP会员破解教程
5年前3.1W+人已阅读
TOP3
[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网
密码保护：[桜井宁宁]COS和泉纱雾超可爱写真福利集
5年前2.8W+人已阅读
TOP4
[桜井宁宁] 爆乳奶牛少女cos写真-一一网
密码保护：[桜井宁宁] 爆乳奶牛少女cos写真
5年前2.8W+人已阅读
TOP5
快猫v1.1.7会员破解版_最新快猫vip破解教程大全-一一网
快猫v1.1.7会员破解版_最新快猫vip破解教程大全
5年前2.7W+人已阅读
TOP6
标签云
默认路由黑裙黑群晖麦克风车机鸿蒙系统鸿蒙系统鸿蒙OS鸿蒙驱动软件驱动题库音频剪辑音乐剪辑面板面具静态雷石集群随机阿里云