【数据结构-树】AVL树

2023-09-15 00:03:20

💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。
img

  • 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老
  • 导航
    • 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等
    • 常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等
    • 数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等
    • 懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作
    • 数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂

非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨

博客目录

一.简介

1.AVL 历史

AVL 树是一种自平衡二叉搜索树，由托尔·哈斯特罗姆在 1960 年提出并在 1962 年发表。它的名字来源于发明者的名字：Adelson-Velsky 和 Landis，他们是苏联数学家，于 1962 年发表了一篇论文，详细介绍了 AVL 树的概念和性质。

在二叉搜索树中，如果插入的元素按照特定的顺序排列，可能会导致树变得非常不平衡，从而降低搜索、插入和删除的效率。为了解决这个问题，AVL 树通过在每个节点中维护一个平衡因子来确保树的平衡。平衡因子是左子树的高度减去右子树的高度。如果平衡因子的绝对值大于等于 2，则通过旋转操作来重新平衡树。

AVL 树是用于存储有序数据的一种重要数据结构，它是二叉搜索树的一种改进和扩展。它不仅能够提高搜索、插入和删除操作的效率，而且还能够确保树的深度始终保持在 O(log n) 的水平。随着计算机技术的不断发展，AVL 树已经成为了许多高效算法和系统中必不可少的一种基础数据结构。

如果一棵二叉搜索树长的不平衡，那么查询的效率会受到影响，如下图

image-20230313090500760

通过旋转可以让树重新变得平衡，并且不会改变二叉搜索树的性质（即左边仍然小，右边仍然大）

image-20230313090817485

2.如何判断失衡？

如果一个节点的左右孩子，高度差超过 1，则此节点失衡，才需要旋转

叶子节点的高度默认为 1

网上遍历,高度越高

3.节点的高度

如何得到节点高度？一种方式之前做过的一道题目：E05. 求二叉树的最大深度（高度），但由于求高度是一个非常频繁的操作，因此将高度作为节点的一个属性，将来新增或删除时及时更新，默认为 1（按力扣说法）

static class AVLNode {
    int height = 1;
    int key;
    Object value;
    AVLNode left;
    AVLNode right;
    // ...
}

求高度代码

这里加入了 height 函数方便求节点为 null 时的高度

private int height(AVLNode node) {
    return node == null ? 0 : node.height;
}

更新高度代码

将来新增、删除、旋转时，高度都可能发生变化，需要更新。下面是更新高度的代码

private void updateHeight(AVLNode node) {
    node.height = Integer.max(height(node.left), height(node.right)) + 1;
}

4.何时触发失衡判断？

定义平衡因子（balance factor）如下

平衡因子 = 左子树高度 − 右子树高度 平衡因子 = 左子树高度 - 右子树高度 平衡因子=左子树高度−右子树高度

当平衡因子

  • bf = 0，1，-1 时，表示左右平衡
  • bf > 1 时，表示左边太高
  • bf < -1 时，表示右边太高

对应代码

private int bf(AVLNode node) {
    return height(node.left) - height(node.right);
}

当插入新节点，或删除节点时，引起高度变化时，例如

image-20230310153645397

目前此树平衡，当再插入一个 4 时，节点们的高度都产生了相应的变化，8 节点失衡了

image-20230310153803661

在比如说，下面这棵树一开始也是平衡的

image-20230310154155728

当删除节点 8 时，节点们的高度都产生了相应的变化，6 节点失衡了

image-20230310154232729

二.自平衡

1.失衡的四种情况

  • LL
  • LR
  • RL
  • RR

2.LL

image-20230310154459709

  • 失衡节点（图中 8 红色）的 bf > 1，即左边更高
  • 失衡节点的左孩子（图中 6）的 bf >= 0 即左孩子这边也是左边更高或等高

3.LR

image-20230310154858754

  • 失衡节点（图中 8）的 bf > 1，即左边更高
  • 失衡节点的左孩子（图中 6 红色）的 bf < 0 即左孩子这边是右边更高

对称的还有两种情况

4.RL

image-20230310155048187

  • 失衡节点（图中 3）的 bf <-1，即右边更高
  • 失衡节点的右孩子（图中 6 红色）的 bf > 0，即右孩子这边左边更高

5.RR

image-20230310155347349

  • 失衡节点（图中 3）的 bf <-1，即右边更高
  • 失衡节点的右孩子（图中 6 红色）的 bf <= 0，即右孩子这边右边更高或等高

6.解决失衡

失衡可以通过树的旋转解决。什么是树的旋转呢？它是在不干扰元素顺序的情况下更改结构，通常用来让树的高度变得平衡。

观察下面一棵二叉搜索树，可以看到，旋转后，并未改变树的左小右大特性，但根、父、孩子节点都发生了变化

      4                                   2
     / \             4 right             / \
    2   5      -------------------->    1   4
   / \         <--------------------       / \
  1   3              2 left               3   5

7.右旋

旋转前

image-20230310162158692

  • 红色节点，旧根（失衡节点）
  • 黄色节点，旧根的左孩子，将来作为新根，旧根是它右孩子
  • 绿色节点，新根的右孩子，将来要换爹作为旧根的左孩子

旋转后

image-20230310162442932

代码

private AVLNode rightRotate(AVLNode red) {
    AVLNode yellow = red.left;
    AVLNode green = yellow.right;
    yellow.right = red;
    red.left = green;
    return yellow;
}

8.左旋

旋转前

image-20230310162945078

  • 红色节点，旧根（失衡节点）
  • 黄色节点，旧根的右孩子，将来作为新根，旧根是它左孩子
  • 绿色节点，新根的左孩子，将来要换爹作为旧根的右孩子

旋转后

image-20230310163019508

代码

private AVLNode leftRotate(AVLNode red) {
    AVLNode yellow = red.right;
    AVLNode green = yellow.left;
    yellow.left = red;
    red.right = green;
    return yellow;
}

9.左右旋

指先左旋左子树，再右旋根节点（失衡），这时一次旋转并不能解决失衡

image-20230310171424362

左子树旋转后

image-20230310171636904

根右旋前

image-20230310171821578

根右旋后

image-20230310171903417

代码

private AVLNode leftRightRotate(AVLNode root) {
    root.left = leftRotate(root.left);
    return rightRotate(root);
}

10.右左旋

指先右旋右子树，再左旋根节点（失衡）

image-20230310172212302

右子树右旋后

image-20230310172234154

根左旋前

image-20230310172303012

根左旋后

image-20230310172317379

代码

private AVLNode rightLeftRotate(AVLNode root) {
    root.right = rightRotate(root.right);
    return leftRotate(root);
}

判断及调整平衡代码

private AVLNode balance(AVLNode node) {
    if (node == null) {
        return null;
    }
    int bf = bf(node);
    if (bf > 1 && bf(node.left) >= 0) {
        return rightRotate(node);
    } else if (bf > 1 && bf(node.left) < 0) {
        return rightLeftRotate(node);
    } else if (bf < -1 && bf(node.right) > 0) {
        return leftRightRotate(node);
    } else if (bf < -1 && bf(node.right) <= 0) {
        return rightRotate(node);
    }
    return node;
}

以上四种旋转代码里，都需要更新高度，需要更新的节点是红色、黄色，而绿色节点高度不变

三.新增与删除

1.新增

public void put(int key, Object value) {
    root = doPut(root, key, value);
}

private AVLNode doPut(AVLNode node, int key, Object value) {
    if (node == null) {
        return new AVLNode(key, value);
    }
    if (key == node.key) {
        node.value = value;
        return node;
    }
    if (key < node.key) {
        node.left = doPut(node.left, key, value);
    } else {
        node.right = doPut(node.right, key, value);
    }
    updateHeight(node);
    return balance(node);
}

2.删除

public void remove(int key) {
    root = doRemove(root, key);
}

private AVLNode doRemove(AVLNode node, int key) {
    if (node == null) {
        return null;
    }
    if (key < node.key) {
        node.left = doRemove(node.left, key);
    } else if (node.key < key) {
        node.right = doRemove(node.right, key);
    } else {
        if (node.left == null) {
            node = node.right;
        } else if (node.right == null) {
            node = node.left;
        } else {
            AVLNode s = node.right;
            while (s.left != null) {
                s = s.left;
            }
            s.right = doRemove(node.right, s.key);
            s.left = node.left;
            node = s;
        }
    }
    if (node == null) {
        return null;
    }
    updateHeight(node);
    return balance(node);
}

3.完整代码

public class AVLTree {
    static class AVLNode {
        int height = 1;
        int key;
        Object value;
        AVLNode left;
        AVLNode right;

        public AVLNode(int key) {
            this.key = key;
        }

        public AVLNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public AVLNode(int key, Object value, AVLNode left, AVLNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    AVLNode root;

    private AVLNode leftRotate(AVLNode p) {
        AVLNode r = p.right;
        AVLNode b = r.left;
        r.left = p;
        p.right = b;
        updateHeight(p);
        updateHeight(r);
        return r;
    }

    private void updateHeight(AVLNode node) {
        node.height = Integer.max(height(node.left), height(node.right)) + 1;
    }

    private AVLNode rightRotate(AVLNode r) {
        AVLNode a = r.left;
        AVLNode b = a.right;
        a.right = r;
        r.left = b;
        updateHeight(r);
        updateHeight(a);
        return a;
    }

    private AVLNode leftRightRotate(AVLNode p) {
        AVLNode r = p.left;
        p.left = leftRotate(r);
        return rightRotate(p);
    }

    private AVLNode rightLeftRotate(AVLNode p) {
        AVLNode r = p.right;
        p.right = rightRotate(r);
        return leftRotate(p);
    }

    private int height(AVLNode node) {
        return node == null ? 0 : node.height;
    }



    public void remove(int key) {
        root = doRemove(root, key);
    }

    private AVLNode doRemove(AVLNode node, int key) {
        if (node == null) {
            return null;
        }
        if (key < node.key) {
            node.left = doRemove(node.left, key);
        } else if (node.key < key) {
            node.right = doRemove(node.right, key);
        } else {
            if (node.left == null) {
                node = node.right;
            } else if (node.right == null) {
                node = node.left;
            } else {
                AVLNode s = node.right;
                while (s.left != null) {
                    s = s.left;
                }
                s.right = doRemove(node.right, s.key);
                s.left = node.left;
                node = s;
            }
        }
        if (node == null) {
            return null;
        }
        updateHeight(node);
        return balance(node);
    }

    public void put(int key, Object value) {
        root = doPut(root, key, value);
    }

    private AVLNode doPut(AVLNode node, int key, Object value) {
        if (node == null) {
            return new AVLNode(key, value);
        }
        if (key == node.key) {
            node.value = value;
            return node;
        }
        if (key < node.key) {
            node.left = doPut(node.left, key, value);
        } else {
            node.right = doPut(node.right, key, value);
        }
        updateHeight(node);
        return balance(node);
    }

    private int bf(AVLNode node) {
        return height(node.left) - height(node.right);
    }

    private AVLNode balance(AVLNode node) {
        if (node == null) {
            return null;
        }
        int bf = bf(node);
        if (bf > 1 && bf(node.left) >= 0) {
            return rightRotate(node);
        } else if (bf > 1 && bf(node.left) < 0) {
            return rightLeftRotate(node);
        } else if (bf < -1 && bf(node.right) > 0) {
            return leftRightRotate(node);
        } else if (bf < -1 && bf(node.right) <= 0) {
            return rightRotate(node);
        }
        return node;
    }
}

4.小结

AVL 树的优点：

  1. AVL 树是一种自平衡树，保证了树的高度平衡，从而保证了树的查询和插入操作的时间复杂度均为 O(logn)。
  2. 相比于一般二叉搜索树，AVL 树对查询效率的提升更为显著，因为其左右子树高度的差值不会超过 1，避免了二叉搜索树退化为链表的情况，使得整棵树的高度更低。
  3. AVL 树的删除操作比较简单，只需要像插入一样旋转即可，在旋转过程中树的平衡性可以得到维护。

AVL 树的缺点：

  1. AVL 树每次插入或删除节点时需要进行旋转操作，这个操作比较耗时，因此在一些应用中不太适用。
  2. 在 AVL 树进行插入或删除操作时，为保持树的平衡需要不断进行旋转操作，在一些高并发环节和大数据量环境下，这可能会导致多余的写锁导致性能瓶颈。
  3. AVL 树的旋转操作相对较多，因此在一些应用中可能会造成较大的空间浪费。

觉得有用的话点个赞 👍🏻 呗。
❤️❤️❤️本人水平有限，如有纰漏，欢迎各位大佬评论批评指正！😄😄😄

💘💘💘如果觉得这篇文对你有帮助的话，也请给个点赞、收藏下吧，非常感谢!👍 👍 👍

🔥🔥🔥Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧！🌙🌙🌙

img

更多推荐

CSI及CPHY的学习知识点

1.CPHY不需要linecoding8b/10b这些线路编码是不需要的，CPHY的三线编码本身就解决了连续0/1的情况。2.CPHY的三线编码使用状态跳变传递信息的有六个线态(wirestate),每一个当前线态都可以跳变到另外5个线态。每一次跳变对应3bitsymbol【跳变有5种可能，用3bit表示，所以3bit

OpenCV自学笔记二十：图像分割和提取

1、用分水岭算法实现图像分割与提取分水岭算法是一种经典的图像分割算法，用于将图像中的前景和背景进行分离。它基于图像中的灰度值和梯度信息来确定边界，并通过填充区域将图像分割成多个连通的区域。以下是分水岭算法的基本原理：1.预处理：首先对输入图像进行预处理操作，例如灰度化、平滑滤波和边缘检测等，以便更好地捕捉图像的特征。2

新工具 ！一键无限重置 Jetbrain 2023 最新版系列

今天逛github，看到了一个新的Jetbrains系列软件的无限30天试用的方法，体验了下，感觉还不错，使用方法很简单。我看介绍软件还处于测试阶段，大家感兴趣的可以试试看。演示软件RubyMine2023.1JetbrainKiller0.5.0使用方法软件名称叫JetbrainKiller，使用方法就是打开软件，一

基于 Socket 网络编程

基于Socket网络编程前言一、基于Socket的网络通信传输（传输层）二、UDP的数据报套接字编程1、UDP套接字编程API2、使用UDPSocket实现简单通信三、TCP流套接字编程1、TCP流套接字编程API2、使用TCPSocket实现简单通信3、使用Tcp协议进行网络传输的“五大要点”前言我们再进行网络编程时

VFP保存大文件到MSSQL，最大2G，超过得上手段

目前社群在聊这个大文件读取的问题，赵总说要把image字段换成BASE64来读取，我就一脸蒙。为什么要转BASE64，体积暴涨三分之一，明显直取更快，200MB文件对单个文件来说，不算大。赵总还写了啥直读程序，于是就来验证一下情况拿出猫框，简单的操作一下建立MSSQL数据库表1生成猫框DAL类DefineClassDa

思腾云计算

为推动AI行业的国产化布局，迎合国产化服务器的市场需求，思腾合力推出华思系列服务器。1.前置24盘12GSASEXP硬盘背板，可以插24个3.5/2.5寸SAS/SATA硬盘；2.后置12盘12GSASEXP硬盘背板，可插12个3.5/2.5寸SAS/SATA硬盘，外加4口U.2硬盘背板1套；3.内置2个M.2SATA

线性代数的本质(十一)——复数矩阵

文章目录复数矩阵附录极大线性无关组向量叉积复数矩阵矩阵AAA的元素aij∈Ca_{ij}\in\Complexaij​∈C，称为复矩阵。现将实数矩阵的一些概念推广到复数矩阵，相应的一些性质在复数矩阵同样适用。定义：设复矩阵A=(aij)m×nA=(a_{ij})_{m\timesn}A=(aij​)m×n​矩阵Aˉ=(

SkyWalking快速上手（五）——存放在内存、数据持久化

文章目录存放在内存一、概述二、数据存放方式1.指标数据2.跟踪数据三、优势和注意事项四、总结数据持久化一、指标数据的持久化二、跟踪数据的持久化三、注意事项四、总结存放在内存一、概述SkyWalking是一个开源的分布式系统追踪和性能监控工具，用于帮助开发人员和运维人员监控和分析分布式系统的性能问题。在SkyWalkin

SkyWalking入门之Agent原理初步分析

一、简介当前稍微上点体量的互联网公司已经逐渐采用微服务的开发模式，将之前早期的单体架构系统拆分为很多的子系统，子系统封装为微服务，彼此间通过HTTP协议RESETAPI的方式进行相互调用或者gRPC协议进行数据协作。早期微服务只有几个的情况下，我们遇到问题可以直接简单、快速地通过采集日志进行分析，是A服务存在问题还是B

ReadWriteLock（读写锁）和阻塞队列BlockingQueue与同步队列SynchronousQueue

1.ReadWriteLockpackagecom.kuang.rw;importjava.util.HashMap;importjava.util.Map;importjava.util.concurrent.locks.ReadWriteLock;importjava.util.concurrent.locks.R

传导和辐射EMI有什么区别？

当我们设计原型或使用开发板时，通常可以忽略电磁干扰。但EMI在现实生活中的电子设备和系统中是一个重要的主题，工程师有责任确保电路能够在预期的EMI水平下正常运行，并且不会产生过多的EMI。我倾向于将EMI与无线干扰联系起来，考虑到名称，这并不令人惊讶：它被称为电磁干扰，我们自然将其与电磁辐射联系起来。但正如您从本文标题

热文推荐
  1. Linux--信号量

    一、信号量信号量（semaphore）与已经介绍过的IPC结构不同，他是一个计数器。用于实现进程间的互斥与同步，而不是用于存储进程间的通信数据。可以与共享内存配合使用。临界资源：多道程序系统种存在许多进程，他们共享各种资源，然而有很多资源一次智能供一个进程使用。一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属

  2. 决策树案例分析

    决策树(DecisionTree)常用于研究类别归属和预测关系的模型，比如是否抽烟、是否喝酒、年龄、体重等4项个人特征可能会影响到‘是否患癌症’，上述4项个人特征称作‘特征’，也即自变量（影响因素X），‘是否患癌症’称为‘标签’，也即因变量（被影响项Y）。决策树模型时，其可首先对年龄进行划分，比如以70岁为界，年龄大于

  3. AI与传统数据库 - ChatGPT风过之后 ｜ 从Duet AI说开来

    作者：NiDemai，是NineData数据库产品专家，曾任阿里云数据库国际产品总负责人，华为高斯GaussDB创始团队核心架构师，IBMDb2资深研发工程师。Demai专注Cloud-Nativedatabase架构设计，分析型MPP，企业数据库开发及生态，并且积极参与开源社区建立和发展。OpenAI的突破震撼整个市

  4. 用青龙面板实现阿里云盘每日签到

    什么是青龙面板?青龙面板是支持Python3、JavaScript、Shell、Typescript的定时任务管理平台。青龙面板从功能上看，和群晖的计划任务很像，都可以定时执行一个任务，并发送通知，只是青龙面板更强大一些。安装在群晖上以Docker方式安装。在注册表中搜索whyour，选择第一个whyour/qingl

  5. 迅为iTOP-RK3568开发板Sobel 算子边缘检测

    本小节代码在配套资料“iTOP-3568开发板\03_【iTOP-RK3568开发板】指南教程\04_OpenCV开发配套资料\32”目录下，如下图所示：Sobel(索贝尔)算子是计算机视觉领域的一种重要处理方法。主要用于获得数字图像的一阶梯度,常见的应用和物理意义是边缘检测。索贝尔算子把图像中每个像素的上下左右四领域

  6. 【数据结构】顺序表与ArrayList

    作者主页：paperjie的博客本文作者：大家好，我是paperjie，感谢你阅读本文，欢迎一建三连哦。本文录入于《JAVA数据结构》专栏，本专栏是针对于大学生，编程小白精心打造的。笔者用重金(时间和精力)打造，将javaSE基础知识一网打尽，希望可以帮到读者们哦。其他专栏：《算法详解》《C语言》《javaSE》等内容

  7. 基于TensorFlow+CNN+协同过滤算法的智能电影推荐系统——深度学习算法应用(含微信小程序、ipynb工程源码)+MovieLens数据集（七）

    目录前言总体设计系统整体结构图系统流程图运行环境模块实现1.模型训练1）数据集分析2）数据预处理3）模型创建4）模型训练5）获取特征矩阵2.后端Django3.前端微信小程序1）小程序全局配置文件2）推荐电影页面3）个人信息界面以及用户登录记录页面系统测试1.模型损失曲线2.测试效果相关其它博客工程源代码下载其它资料下

  8. 让机器人飞入寻常百姓家丨青源Workshop「人形机器人」观点集锦

    人形机器人并非新事物，早在上世纪70年代，日本早稻田大学加藤一郎就带领团队研发出世界上第一台人形智能机器人——WABOT-1。而去年马斯克Optimus的发布，也对“机器人热”再度推波助澜。人形机器人领域的发展，需要软件和硬件的共同迭代和优化，同时相比于无人驾驶，人形机器人涉及更加复杂的真实世界多模态环境。机器人技术依

  9. Cpp/Qt-day020918Qt

    目录完善登录框点击登录按钮后，判断账号（admin）和密码（123456）是否一致，如果匹配失败，则弹出错误对话框，文本内容“账号密码不匹配，是否重新登录”，给定两个按钮ok和cancel，点击ok后，会清除密码框中的内容，继续进行登录；如果点击cancel按钮，则关闭界面。如果账号和密码匹配，则弹出信息对话框，给出提