二叉树、红黑树、B树、B+树

这篇具有很好参考价值的文章主要介绍了二叉树、红黑树、B树、B+树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

二叉树

一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
二叉树的特点

  1. 每个结点最多有两棵子树,即二叉树不存在度大于2的结点。
  2. 二叉树的子树有左右之分,其子树的次序不能颠倒。

满二叉树

满二叉树:二叉树的所有叶子节点都在最后一层且总数n=2^(n-1)。

二叉树、红黑树、B树、B+树,数据结构,算法

完全二叉树

完全二叉树:数据从上到下,从左到右依次进行平铺。

有序二叉树

有序二叉树:左子树上的值小于根节点的值,右子树上的值大于根节点的值。

有序二叉树的遍历:

深度优先遍历:

1、先序/前序遍历:根节点----》左子树-----》右子树

2、中序遍历:左子树----》根节点-----》右子树

3、后序遍历:左子树----》右子树-----》根节点

有序二叉树不稳定:O(logn) - O(n)

有序二叉树不稳定是因为没有任何限制,以至于在某些特殊的情况下会形成链表。

平衡二叉树

平衡二叉树是在有序二叉树的基础之上而来的,就是为了解决有序二叉树不稳定的问题。要求:一个节点的左右子树高度差的绝对值不能超过1,可以等于1。

如果插入的数据之后使得一个节点的左右子树高度差的绝对值超过了1,就要通过LL、RR、LR、RL四种旋转策略来保证平衡二叉树。

四种旋转策略

LL旋转策略:

二叉树、红黑树、B树、B+树,数据结构,算法

实例:

二叉树、红黑树、B树、B+树,数据结构,算法

RR旋转策略:

二叉树、红黑树、B树、B+树,数据结构,算法

实例:

二叉树、红黑树、B树、B+树,数据结构,算法

LR旋转策略:

二叉树、红黑树、B树、B+树,数据结构,算法

实例:

二叉树、红黑树、B树、B+树,数据结构,算法

RL旋转策略:

二叉树、红黑树、B树、B+树,数据结构,算法

实例:

二叉树、红黑树、B树、B+树,数据结构,算法

在实行旋转策略是,选择距离造成不平衡节点最近的不平衡节点作为要操作节点。

平衡二叉树特别稳定,但每次进行调整都会耗费计算机性能。

我们想既要时间复杂度在O(logn),又要十分稳定,还要不耗费计算机性能,这时,推出了红黑树。

红黑树(基于2-3-4树)

2-3-4树是从下向上构建的。节点内升序,每个节点最多有3个值,当插入第4个值时,需要在这四个之中选中间值进行升元。

实例:

二叉树、红黑树、B树、B+树,数据结构,算法

然后通过2-3-4树转换 形成红黑树

转换规则如下图:

二叉树、红黑树、B树、B+树,数据结构,算法

将刚刚的2-3-4树转换为红黑树:

二叉树、红黑树、B树、B+树,数据结构,算法

红黑树的特点:

1、红黑树中每一个节点不是红色节点就是黑色节点。

2、红黑树当中根节点一定是黑色的。———>在转化的过程中2-3-4节点都是以黑色节点开头的

3、每一个叶子节点都是黑色的。

4、从根节点到任意一个叶子节点的路径上所走过的黑色节点的数量相同

5、如果一个节点是红色的,那么他的子节点一定是黑色

4、5条特点会导致最长的路径绝对不会超过最短路径的2倍。例如最长路径为黑红黑红黑红,最短路径为黑黑黑。

为什么红黑树是O(logn)?

2-3-4树是多叉树,如果数据相等,它的时间复杂度小于传统二叉树,2-3-4树的时间复杂度

红黑树最复杂的时候也就是变为2倍,变为2logn。这是依旧可以看成是logn。

B树

多叉树以B树为最基本点。2-3-4树来源于B树。

B树特点:

1、B树的数据存储是 key-value类型的。

2、B树有几个叉:并不确定,要看具体实现。

3、M阶B树

        3.1、每个节点上最多有 M-1 个值,并且以升序排列。3阶B树每个节点最多有两个值。.....(2-3-4树属于4阶B树)

红黑树和B树如果都在内存中,内存向cpu提供数据的时间相等,由于红黑树对比次数相对较少,所以红黑树是内存最优二叉树。

为什么要有B树:

红黑树和B树如果都在磁盘中--------》数据寻址浪费时间--------》磁头移动的物理时间+平均盘面旋转半圈

B树多用于磁盘,原因是分出多个叉,降低树的高度,降低寻址次数和时间。

B树优胜于寻址,但是数据进行对比还是要在内存中。

B+树

在B树基础上改造出现的B+树,但和传统B树又不太一样。B+树是mysql数据库专用底层数据结构。

B+树的特点:

1、非叶子节点仅具有索引功能,也就是说非叶子节点只能存储key值,不能存储value值。

2、B+树的所有叶子节点会构成一个有序的链表,这样就可以根据key值遍历数据。

之所以有这两个特点就是为数据库的功能服务

B+树的构建

二叉树、红黑树、B树、B+树,数据结构,算法

插入 3 ,4

二叉树、红黑树、B树、B+树,数据结构,算法

二叉树、红黑树、B树、B+树,数据结构,算法

磁盘向cpu推送数据:每次需要推送一页(4kb)的数据,如两个文件 2kb+3kb,只能先推送2kb,再推送3kb。

B+树的优点:

1、非叶子节点不包含数据,只能放索引,这样每次就可以向内存当中传输更多的key值,在内存当中进行数据比对,在磁盘当中进行数据查询。

2、叶子节点是链接在一起的,这样有利于区间查询。文章来源地址https://www.toymoban.com/news/detail-679287.html

到了这里,关于二叉树、红黑树、B树、B+树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法(三):树论(树形结构、二叉树、二叉搜索树、红黑树、Btree&B+Tree、赫夫曼树、堆树)

    树论(树形结构、二叉树、二叉搜索树、红黑树、Btree、B+Tree、赫夫曼树、堆树) 在树形结构里面重要的术语: 结点:树里面的元素。 父子关系:结点之间相连的边 子树:当结点大于1时,其余的结点分为的互不相交的集合称为子树 度:一个结点拥有的子树数量称为结点的

    2024年02月01日
    浏览(94)
  • 数据结构之进阶二叉树(二叉搜索树和AVL树、红黑树的实现)超详细解析,附实操图和搜索二叉树的实现过程图

    绪论​ “生命有如铁砧,愈被敲打,愈能发出火花。——伽利略”;本章主要是数据结构 二叉树的进阶知识,若之前没学过二叉树建议看看这篇文章一篇掌握二叉树,本章的知识从浅到深的 对搜索二叉树的使用进行了介绍和对其底层逻辑的实现进行了讲解 ,希望能对你有所

    2024年02月04日
    浏览(47)
  • 【数据结构】树二叉树的概念以及堆的详解

    ✨链接1:【数据结构】顺序表 ✨链接2:【数据结构】单链表 ✨链接3:【数据结构】双向带头循环链表 ✨链接4:【数据结构】栈和队列 百度百科的解释 :树是一种 非线性 的数据结构,它是由n(n≥0)个有限节点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像

    2024年02月16日
    浏览(40)
  • 【高阶数据结构】红黑树 {概念及性质;红黑树的结构;红黑树的实现;红黑树插入操作详细解释;红黑树的验证}

    红黑树(Red Black Tree) 是一种自平衡二叉查找树,在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。 AVL树 VS 红黑树 红黑树是

    2024年02月09日
    浏览(49)
  • 搜索二叉树 | 红黑树 | 验证是否为红黑树 | 代码实现

    黑红树是一颗特殊的搜索二叉树,本文在前文的基础上,图解红黑树插入:前文 链接,完整对部分关键代码展示,完整的代码在gitee仓库中: 链接 文章中有错误的地方,欢迎大家指正!如果有帮助到你,也请多多点赞支持! 1.红黑树的概述 平衡二叉树要求左右子树的高度差

    2024年02月21日
    浏览(41)
  • 数据结构 | 红黑树

    节点的左边比节点的值小,右边比节点的值大。 节点要么是 红色 ,要么是 黑色 根节点 是黑色 叶子节点都是黑色的空节点 红黑树中红色节点的子节点都是黑色 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点 在添加或者删除节点的时候,如果不满足这些性质会

    2024年01月21日
    浏览(44)
  • [数据结构]-红黑树

    前言 作者 : 小蜗牛向前冲 名言: 我可以接受失败,但我不能接受放弃   如果觉的博主的文章还不错的话,还请 点赞,收藏,关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正 目录 一、红黑树的基本知识  1、红黑树的概念 2、性质  二、红黑树的模拟实

    2024年02月04日
    浏览(46)
  • 【数据结构】红黑树

    🐱作者:一只大喵咪1201 🐱专栏:《数据结构与算法》 🔥格言: 你只管努力,剩下的交给时间! 在学习AVL树的时候,我们知道,当修改AVL树的结构(插入,删除)时,会通过旋转来保证平衡因子不超过1,所以频繁的修改结构会导致效率低下,今天我们学习的红黑树就完美解

    2023年04月17日
    浏览(49)
  • 数据结构——红黑树

    目录 概念 性质 结点的定义  插入 调整 当p是g的左孩子时 当p为g的右孩子时 插入完整代码 红黑树的检测 红黑树完整代码(包括测试数据)   红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是RED或BLACK。 通过对任何一条从根到叶子的路径

    2023年04月09日
    浏览(46)
  • 【数据结构-树】红黑树

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月07日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包