学习
实践
活动
工具
TVP
写文章

什么是2-3树

前言

前面的文章我们已经学习了二叉搜索树和平衡二叉搜索树AVL树,今天我们再来了解一种新的平衡树2–3树,2–3树由约翰·霍普克洛夫特于1970年发明,在计算机科学中,2–3树是一种树型数据结构,内部节点(存在子节点的节点)要么有2个孩子和1个数据元素,要么有3个孩子和2个数据元素,叶子节点没有孩子,并且有1个或2个数据元素,2-3树的平均时间复杂度为O(logN),空间复杂度为O(N),注意严格的说2-3树的性能是在O(log3N)和O(log2N)之间的,因为大O复杂度表示通常会忽略系数项。

前面的文章提到过的二叉树,每个节点的孩子个数最多的是2个,并且每个节点只有一个值,而2-3树的节点的孩子个数只能是2个或者3个,这是一种多路树的结构,类似的结构还有2-3-4树,B+树等,多路树的存在除了支持树的平衡外,还可以降低树的高度,从而让搜索,插入,删除的性能有所提升,但与此对应的是程序的编码会变得更加复杂,这也是2-3树或者2-3-4树,在开源框架或日常开发中并不如AVL树和红黑树使用频繁的原因,但B+树除外,因为B+树是特殊优化后的多路查找树,是专门为数据库结合磁盘文件系统定制的。

2-3树的性质

(1)每个节点可以拥有2个或者3个孩子节点,当父节点的值只有一个时,节点的孩子个数有2个,当父节点的值有2个时,节点的孩子个数有3个。

(2)所有的叶子节点都处于同一高度

如图:

(3)父节点是一个值的时候,左孩子的值小于父节点,右孩子的值大于父节点,父节点是2个值,比如记为S , L的时候,孩子节点有3个,分别是左,中,右,左边小于父节点S的值,中间的值大于S,小于L,右边节点的值大于L,如下图:

2-3树 VS 二叉搜索树

同样的一组数据,在2-3树和二叉搜索树里面的对比如下:

可以看到2-3树的节点分布非常均匀,且叶子节点的高度一致,并且如果这里即使是AVL树,那么树的高度也比2-3树高,而高度的降低则可以提升增删改的效率。

2-3树的插入

为了保持平衡性,2-3树的插入如果破坏了平衡性,那么树本身会产生分裂和合并,然后调整结构以维持平衡性,这一点和AVL树为了保持平衡而产生的节点旋转的作用一样,2-3树的插入分裂有几种情况如下:(1)情况一:叶子节点的插入调整,规律是叶子的中间值上升,然后左右值分裂,如下图:

(2)情况二:非叶子节点的调整,大体上与叶子节点的调整一致,不同的是,非叶子节点的孩子节点的值也需要重新分裂,如下图:

(3)情况三:必要的时候为了维持平衡性,会新产生一个root节点,如下图:

2-3树的删除

2-3树节点的删除也会破坏平衡性,同样树本身也会产生分裂和合并,如下:

节点的删除,与二叉搜索树的删除类似,不同的是2-3树会寻找中序的后继节点来替换要删除的节点的值,然后再删除替换的值:

结果如下:

与插入类似,删除的过程中root节点的值可能会被调整到新的节点,而原root节点就会变成空节点,从而需要删除,如下:

删除的过程,也是非常复杂的,涉及到节点的分裂,合并,重分布,删除等操作,这里不再详细描述。

关于2-3-4树

2-3-4树与2-3树类似,只不过当父节点的值是3的时候,节点的孩子个数可以有4个,如下:

2-3-4树可以再次降低的树的高度,但是对应的编码会更加复杂,尤其是在插入和删除之后,所以常常会被容易实现和理解的红黑树代替,这里不再过多介绍。感兴趣的朋友可以自行查询资料学习。

总结

本篇文章,主要介绍了2-3树相关的知识,2-3树,2-3-4树以及B树都不是二叉树,但与二叉树的大致特点是类似的,它们是一种平衡的多路查找树,节点的孩子个数可以允许多于2个,虽然高度降低了,但编码相对复杂,尤其是考虑维护树的平衡性的操作,带来的好处就是可以提升查询的性能,算是各有利弊,在工程项目中通常会权衡选择。

文章分享自微信公众号:
我是攻城师

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!

作者:攻城师在路上
原始发表时间:2019-04-10
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 动画 | 什么是2-3树?

    我们回忆一下AVL树,它在插入和删除节点时,总要保证任意节点左右子树的高度差不超过1。正是因为有这样的限制,插入一个节点和删除一个节点都有可能调整多个节点的不平...

    我脱下短袖
  • 动画 | 什么是红黑树?(基于2-3树)

    学习过2-3树之后就知道应怎样去理解红黑树了,如果直接看「算法导论」里的红黑树的性质,是看不出所以然。我们也看看一颗二分搜索树满足红黑的性质:

    我脱下短袖
  • 动画 | 什么是2-3树?(修改删除操作方式)

    我们回忆一下AVL树,它在插入和删除节点时,总要保证任意节点左右子树的高度差不超过1。正是因为有这样的限制,插入一个节点和删除一个节点都有可能调整多个节点的不平...

    我脱下短袖
  • 三分钟基础知识:什么是 2-3 树?

    前面讲到了二叉搜索树 (BST) 和二叉平衡树 (AVL) :【漫画】以后在有面试官问你AVL树,你就把这篇文章扔给他。

    帅地
  • 2-3树与红黑树

    张风捷特烈
  • 什么是 “线段树” ?

    线段树是一个复杂的数据结构,比较难理解,也比较难解释清楚。在我将这个数据结构反复学习了五遍的时候,我终于有了信心写出这篇介绍线段树的文章。希望大家能够掌握这种数...

    小灰
  • 算法原理系列:2-3查找树

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/...

    用户1147447
  • 动画 | 什么是AVL树?

    首先介绍下 二分搜索树 ,它又名有序二叉查找树,它的特点是左子树的节点值要小于父节点值,右子树的节点值要大于父节点值。基于这样的特点,我们在查找某个节点的时候,...

    我脱下短袖
  • 什么是红黑树?

    当在10亿数据中只需要进行10几次比较就能查找到目标时,不禁感叹编程之魅力!人类之伟大呀! —— 学红黑树有感。

    小东啊
  • 数据结构与算法——2-3树

    前面讲到了二叉搜索树 (BST) 和二叉平衡树 (AVL) ,二叉搜索树在最好的情况下搜索的时间复杂度为 O(logn) ,但如果插入节点时,插入元素序列本身就...

    五分钟学算法
  • 漫画:什么是红黑树?

    2017年,小灰曾经发布过一篇关于红黑树的漫画,当时由于时间仓促,部分知识点一带而过,并没有讲解得很细致全面。

    小灰
  • 漫画:什么是B-树?

    下面来具体介绍一下B-树(Balance Tree),一个m阶的B树具有如下几个特征:

    小灰
  • 图解:什么是B-树、B+树、B*树

    6.非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];

    你好戴先生
  • 「译」什么是抽象语法树

    AST 是抽象语法树的缩写词,表示编程语言的语句和表达式中生成的 token。有了 AST,解释器或编译器就可以生成机器码或者对一条指令求值。

    Chor
  • 漫画:什么是B+树?

    在上一篇漫画中,我们介绍了B-树的原理和应用,没看过的小伙伴们可以点击下面的链接:

    小灰
  • 算法和数据结构: 八 平衡查找树之2-3树

    前面介绍了二叉查找树(Binary Search Tree),他对于大多数情况下的查找和插入在效率上来说是没有问题的,但是他在最差的情况下效率比较低。本文及后面...

    yaphetsfang
  • 什么是二叉查找树?

    对于树的基本认识,我们很容易通过我们平常所见到的树来理解:一棵树,有一个根,根往上又会分叉出大树枝,大树枝又会分叉出小树枝,以此往复,直到最后是叶子。而作为数据...

    编程珠玑
  • 深入理解什么是B树?

    前面的文章,我们已经介绍过其他的几种高级的动态数据结构,典型如红黑树,跳跃表等,今天我们再来学习另外一种高级数据结构B树,我们知道树的查询时间复杂度和其树的高度...

    我是攻城师

扫码关注腾讯云开发者

领取腾讯云代金券