前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >什么是2-3树

什么是2-3树

作者头像
我是攻城师
发布2019-04-28 15:02:46
2.1K0
发布2019-04-28 15:02:46
举报
文章被收录于专栏:我是攻城师

前言

前面的文章我们已经学习了二叉搜索树和平衡二叉搜索树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 删除

本文分享自 我是攻城师 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言
  • 2-3树的性质
  • 2-3树 VS 二叉搜索树
  • 2-3树的插入
  • 2-3树的删除
  • 关于2-3-4树
  • 总结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档