专栏首页javascript艺术程序员的内功心法-234树

程序员的内功心法-234树

直面弱点,奋发图强!!!

引言

红黑树、B树、B+树,都是软件开发中一个比较难理解和掌握的知识点。他们的本质依然是平衡二叉搜索树。如果直接去学习红黑树、B树、B+树的知识点,无异于雾里看花。这次我们从这些数据结构的底层逻辑设计出发,不牵扯任何代码层面上的内容。

二三四树

定义

  • 二节点
    • 一个key和左右两个链接;其中key大于左链接、小于右链接
  • 三节点
    • 包含两个key和三个链接(两个key分别称为key1和key2,key1小于key2)
    • 1、2、3三个子链接(子链接1的key小于根结点key1、子链接2的key大于根结点key1且小于根结点key2、子链接3的key大于根结点key2)
  • 四节点
    • 包含三个key和四个子链接(三个key分别为key1、key2、key3且从小到大排列)
    • 1、2、3、4三个子链接(子链接1的key小于根结点key1、子链接2的key大于根结点key1且小于根结点key2、子链接3的key大于根结点key2且小于根结点key3、子链接4的key大于根结点key3)
  • 上述的节点计数指子链接的数量,而非节点包含的key的数量

操作

由于2、3、4树的查询操作和二叉搜索树的操作一致,不再赘叙。本次主要完成插入和删除的操作描述

可以参考之前的文章,熟悉二叉树一些基本定义和操作

二叉搜索树(BST)

平衡二叉树(AVL)

插入

我们把1-10的数字拆入到一棵234树中

依次插入1、2、3节点

插入4节点,需要将4节点分裂成3个2节点的操作

至此,插入逻辑介绍完毕

删除

节点的删除逻辑,和二叉树的删除逻辑区别不大。如果是叶子节点,可以直接删除;如果是非叶子节点,需要转换为后继/前驱节点的删除方式,所有都可以转换为极值的删除

非2节点的删除
2节点的删删除
对于2节点的删除,需要转换为3、4节点中节点的删除
父节点为非2节点,兄弟节点是2节点
父节点是非2节点,兄弟节点是非2节点
父节点是2节点,兄弟节点非2节点
父节点是2节点,兄弟节点也是2节点

至此,我们的234树的插入和删除操作介绍完了。搞清楚234树的插入和删除操作将是后续红黑树、B树、B+树的前置条件

本文分享自微信公众号 - javascript艺术(gh_4e5484fd6b52),作者:郭里奥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-05-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序员的内功心法-AVL树

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

    javascript艺术
  • 程序员内功心法-设计模式

    房上的猫
  • 程序员内功心法《设计模式》

    设计模式是在软件工程实践过程中,JAVA使用者们总结出的良好的编程方法,使用设计模式能够增加系统的健壮性,易修改性和可扩展性,当你进行开发的软件规模比较大的时候...

    Java架构
  • 程序员的内功心法,你不来看看吗?

    在生活中我们经常会使用到搜索的功能。在我们数据量不大的情况下,可以使用每次遍历全部数据,查询我们的目标数据。当数据量增加时,我们遍历的方式就有些力不从心了;也...

    javascript艺术
  • 《Mac OS系统架构》程序员内功心法索引

    对这幅图的探索已经是3天了~ 它像极了一份神功秘籍 在这份秘籍的指引下 似乎冥冥之中为你的体内注入绵绵深厚的内力 在程序员大神之路的漫长探索过程中 这张图的出现...

    企鹅号小编
  • 程序员内功:八大排序算法

    版权声明:本文为博主原创文章,未经博主允许不得转载。个人网站:http://cuijiahua.com。 ...

    Jack_Cui
  • 程序员内功心法【设计模式】之建造者模式

    建造者模式构建复杂对象就像造汽车一样,是一个一个组件一个一个步骤创建出来的,它允许用户通过制定的对象类型和内容来创建他们,但是用户并不需要知道这个复杂对象是如何...

    Java架构
  • 程序员的外功和内功的修炼

    第一时间获取文章,可以关注本人公众号 月牙寂道长 yueyajidaozhang

    月牙寂道长
  • 神级程序员教你如何写代码——十年编程内功心法

    写代码就是学一门语言然后开始撸代码吗?看完了我一系列文章的同学或者本身已经就是老鸟的同学显然不会这么认为。编程是一项非常严谨的工作!虽然我们自嘲为码农,但是这工...

    企鹅号小编
  • 一个19岁萝莉程序媛的内功心法

    Lydia才19岁,但她绝对是那种“毕业两年,五年工作经验”的类型。年纪轻轻,却有数年的导师经历。她的内功心法都是非常实用的干货,不鸡汤,不矫揉造作。 软件门外...

    企鹅号小编
  • Google 被祭天了!来自程序员内心的恐惧

    自Facebook陷入数据泄露丑闻后,各巨头们一直“谨守本分”。Google作为科技巨头之一,向来是开发者心目中的表率,虽然前一阵子的军事AI项目、审查版引擎等...

    一墨编程学习
  • 一文带你领略并发编程的内功心法

    可以使用不同的并发模型来实现并发系统,并发模型说的是系统中的线程如何协作完成并发任务。不同的并发模型以不同的方式拆分任务,线程可以以不同的方式进行通信和协作。

    cxuan
  • 【拓展】成功程序员的 14 个优秀习惯,良心推荐!

    在没有搞清楚开发需求、任务工作量、团队期望值之前,有前途的程序员不会轻易答应。特别是对于新人来说,比较急于表现自己,对于同事或者老板的工作安排来者不拒,精神可嘉...

    pingan8787
  • 盘点互联网公司最常见的面试编程题

    互联网公司面试,笔试环节或第一面往往都是现场做编程题。很多面试的老铁反映说,败在了编程题上,去不了自己心仪的公司,拿不到想要的待遇。

    不可言诉的深渊
  • 盘点互联网公司最常见的面试编程题

    互联网公司面试,笔试环节或第一面往往都是现场做编程题。很多面试的老铁反映说,败在了编程题上,去不了自己心仪的公司,拿不到想要的待遇。

    石晓文
  • 盘点互联网公司最常见的面试编程题

    互联网公司面试,笔试环节或第一面往往都是现场做编程题。很多面试的老铁反映说,败在了编程题上,去不了自己心仪的公司,拿不到想要的待遇。

    double
  • 实践干货 | 自动化视觉跟踪

    在之前的某个教程里,我们探讨了如何控制Pan/Tilt Servo设备来安置一个PiCam(树莓派的相机)。这次,我们将使用你的设备来帮助相机自动地跟踪某种颜色...

    AI研习社
  • Appium+python自动化(十二)- Android UIAutomator终极定位凶器(超详解)

    乍眼一看,小伙伴们觉得这部分其实在异性兄弟那里就做过介绍和分享了,其实不然,上次介绍和分享的大哥是uiautomatorviewer,是一款定位工具...

    北京-宏哥
  • 自动化视觉跟踪

    在之前的某个教程里,我们探讨了如何控制Pan/Tilt Servo设备来安置一个PiCam(树莓派的相机)。这次,我们将使用你的设备来帮助相机自动地跟踪某种颜色...

    AI科技评论

扫码关注云+社区

领取腾讯云代金券