首页 > 其他分享 >BST(二叉搜索树)、AVL(平衡二叉树)、RBT(红黑树)的区别

BST(二叉搜索树)、AVL(平衡二叉树)、RBT(红黑树)的区别

时间:2023-07-17 11:56:58浏览次数:43  
标签:BST RBT 二叉 AVL 查找 二叉树 平衡 节点

一、二叉搜索树(BST:Binary Sort Tree)  

  二叉查找树就是左结点小于根节点右结点大于根节点的一种排序树,也叫二叉搜索树。

  二叉查找树比普通树查找更快,查找、插入、删除的时间复杂度为O(logN)。但是二叉查找树有一种极端的情况,就是会变成一种线性链表似的结构。此时时间复杂度就变成了O(N),为了解决这种情况,出现了二叉平衡树。

  

二、平衡二叉树(AVL:)  

  平衡二叉树全称平衡二叉搜索树,也叫AVL树。是一种自平衡的树。

  AVL树也规定了左结点小于根节点,右结点大于根节点。并且还规定了左子树和右子树的高度差不得超过1。这样保证了它不会成为线性的链表。AVL树的查找稳定,查找、插入、删除的时间复杂度都为O(logN),但是由于要维持自身的平衡,所以进行插入和删除结点操作的时候,需要对结点进行频繁的旋转(缺点)

  

三、红黑树(RBT:RB-Tree)

  红黑树是一种自平衡的二叉查找树,它的节点的颜色为红色和黑色。它不严格控制左、右子树高度或节点数之差小于等于1。也是一种解决二叉查找树极端情况的数据结构。

  红黑树规定了:

    1.节点是红色或黑色。

    2.根节点是黑色。

    3.每个叶子节点都是黑色的空节点(NULL节点)。

    4 每个红色节点的两个子节点都是黑色。也就是说从每个叶子到根的所有路径上不能有两个连续的红色节点)。

    5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。  

  

 

  红黑树是保持“黑平衡”的二叉树:对于黑平衡是指,从根节点开始搜索,一直搜索到叶子节点,所经历的黑色节点的个数是一样的。

  黑平衡二叉树,严格意义上,不是平衡二叉树:左右子树的高度差可能大于1,时间复杂度是O(logn),最大高度:2logn,红黑树不会像二分搜索树一样退化为链表。

   查找的时间上面会比AVL树慢一点,因为最大高度为2logn,添加操作和删除操作比AVL树要快一些

  

  查找:

    红黑树在查找方面和AVL树操作几乎相同。但是红黑树左右子树的高度差可能大于1,时间复杂度是O(logn),最大高度:2logn。(因为红黑树可以能确保树的最长路径不大于两倍的最短路径的长度,所以可以看出它的查找效果是有最低保证的。在最坏的情况下也可以保证O(logN)的,这是要好于二叉查找树的。因为二叉查找树最坏情况可以让查找达到O(N)。)

  新增、删除:

    AVL树每次插入删除会进行大量的平衡度计算,红黑树是牺牲了严格的高度平衡的优越条件为代价,它只要求部分地达到平衡要求,结合变色,降低了对旋转的要求,从而提高了性能。(红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外,由于它的设计,任何不平衡都会在三次旋转之内解决。)

四、RBT对比ALV

   AVL 和RBT 都是二叉查找树的优化。其性能要远远好于二叉查找树。他们之间都有自己的优势,其应用上也有不同。

  1、结构对比

结构对比: AVL的结构高度平衡,RBT的结构基本平衡。平衡度AVL > RBT.

  2、查找对比

查找对比: AVL 查找时间复杂度最好,最坏情况都是O(logN)。RBT 查找时间复杂度最好为O(logN),最坏情况下比AVL略差。

  3、插入删除对比

插入删除对比: AVL的插入和删除结点很容易造成树结构的不平衡,而RBT的平衡度要求较低。因此在大量数据插入的情况下,RBT需要通过旋转变色操作来重新达到平衡的频度要小于AVL。
  如果需要平衡处理时,RBT比AVL多一种变色操作,而且变色的时间复杂度在O(logN)数量级上。但是由于操作简单,所以在实践中这种变色仍然是非常快速的。
  当插入一个结点都引起了树的不平衡,AVL和RBT都最多需要2次旋转操作。但删除一个结点引起不平衡后,AVL最多需要logN 次旋转操作,而RBT最多只需要3次。因此两者插入一个结点的代价差不多,但删除一个结点的代价RBT要低一些。

  4、使用上对比

使用上对比:
    数据分布较好:则比较宜于采用 AVL树(例如随机产生系列数);
    数据分布杂乱:如果你想处理比较杂乱的情况,则红黑树是比较快的。

 

标签:BST,RBT,二叉,AVL,查找,二叉树,平衡,节点
From: https://www.cnblogs.com/karrya/p/17559677.html

相关文章

  • lib64/libstdc++.so.6: version `GLIBCXX_3.4.20' not found (required by /home/liuj
     glibc是GNU发布的libc库,即c运行库。glibc是linux系统中最底层的api,几乎其它任何运行库都会依赖于glibc。glibc除了封装linux操作系统所提供的系统服务外,它本身也提供了许多其它一些必要功能服务的实现。由于glibc囊括了几乎所有的 UNIX 通行的标准,可以想见其内容包罗万象。而......
  • 优先队列(基于二叉树的堆)
    代码出处GoSDKcontainer/heap/heap.goInterface接口定义typeInterfaceinterface{sort.InterfacePush(xinterface{})//addxaselementLen()Pop()interface{}//removeandreturnelementLen()-1.}sort.Interface是自定义排序时需要实现的接......
  • 2023.7.14 在二叉树中分配硬币
    借用灵神的图:所以一个直观的想法就是,计算这个子树的硬币个数和节点个数的差的绝对值。这个就是需要传递给父结点的硬币数量。如果这个子树中的子结点也全部执行了这个操作,那么就会把硬币全部集中到当前结点,因此不用考虑子结点中的移动。所以这是个递归算法。(因为要先完成子结......
  • 10.AbstractQueuedSynchronizer(AQS)
    AbstractQueuedSynchronizer(AQS)AQS入门理论知识概念​ 抽象队列同步器,是用来实现锁或者其它同步器组件的公共基础部分的抽象实现,是重量级基础框架及整个JUC体系的基石,主要用于解决锁分配给"谁"的问题​ 整体就是一个抽象的FIFO队列来完成资源获取线程的排队工作,并通过一个int......
  • Microsoft.AspNetCore.Http.Abstractions 2.20 is deprecated
     您想要升级Microsoft.AspNetCore.Http.Abstractions包,您需要注意以下几点:Microsoft.AspNetCore.Http.Abstractions包在ASP.NETCore2.2版本后已经被标记为过时,因为它已经被包含在Microsoft.AspNetCore.App框架引用中12。因此,您不需要单独引用这个包,只需要在项目文件中......
  • 算法学习day14二叉树part01-94、144、145
    packageSecondBrush.Tree;importjava.util.ArrayList;importjava.util.List;/***94.二叉树的中序遍历*给定一个二叉树的根节点root,返回它的中序遍历。**/publicclassBinaryTreeInorderTraversal_94{publicList<Integer>inorderTraversal(Tre......
  • LeetCode 剑指 Offer 08. 二叉树的下一个节点
    题目:二叉树的下一个节点给定一棵二叉树的其中一个节点,请找出中序遍历序列的下一个节点。(树的后继)注意:如果给定的节点是中序遍历序列的最后一个,则返回空节点;二叉树一定不为空,且给定的节点一定不是空节点;解题思路二叉树的中序遍历:{[左子树],根节点,[右子树]}如图所示......
  • 2023最新版本WebStrom安装教程【2023.1.3】
    前言本文方法可以安装使用截止当前2023.1.3最新版本WebStrom,过程非常简单,按照下面的步骤来一分钟即可搞定。1.下载安装已经安装过的可以跳过该步骤!下载到官网地址下载正版安装包JetBrainsWebStrom官网下载地址安装开始安装选择安装路径桌面快捷方式勾选创建妆......
  • 【算法】根据二叉树的级别返回排序后的元素列表
    根据给定的Node树节点,返回包含按级别排序的树中元素的列表,这意味着根元素位于第一位,然后根子元素(从左到右)位于第二位和第三位,依此类推。1publicclassNode2{3publicNodeLeft;4publicNodeRight;5publicintValue;67publicNode(No......
  • mac M2 多个 docker环境 colim 、docker for mac 、orbstack
    三个环境存在是会让docker命令混乱colim真实的路径/opt/homebrew/bin/docker->/opt/homebrew/Cellar/docker/24.0.2/bin/dockerdocker.sock~/.colim/run/docker.sockdockerformac真实的路径/usr/local/bin/docker->/Applications/Docker.app/Contents/Res......