看图轻松理解数据结构与算法系列(2-3树)

作者:超人汪小建(seaboat)

出处:https://blog.csdn.net/wangyangzhizhou/column/info/25184/2


2-3树

2-3树,是最简单的B-树,其中2、3主要体现在每个非叶子节点都有2个或3个子节点,B-树即是平衡树,平衡树是为了解决不平衡树查询效率问题,常见的二叉平衡书有AVL树,它虽然提高了查询效率,但是插入操作效率不高,因为它需要再每次插入节点后维护树的平衡,而为了解决查询效率同时有兼顾插入效率,于是提出了2-3树。

2-3树特点

  • 2-3树是一棵平衡树,但不是二叉平衡树。
  • 对于高度相同的2-3树和二叉树,2-3树的节点数要大于满二叉树,因为有些节点可能有三个子节点。
  • 2-3树可以是一棵空树。
  • 对于2节点来说,该节点保存了一个key及对应的value,除此之外还保存了指向左右两边的子节点,子节点也是一个2-3节点,左子节点所有值小于key,右子节点所有值大于key。
  • 对于3节点来说,该节点保存了两个key及对应的value,除此之外还保存了指向左中右三个方向的子节点,子节点也是一个2-3节点,左子节点的所有值小于两个key中较小的那个,中节点的所有值在两个key值之间,右子节点大于两个key中较大的那个。
  • 对2-3树进行中序遍历能得到一个排好序的序列。

image

插入操作

刚开始是空树,插入节点“A”,创建根节点,

image

插入节点“B”,从根节点开始寻找存放的节点位置,与“A”节点合并后放到同一个叶子上,此时该叶子只包含“AB”两个项目,无需分裂,

image

继续插入节点“C”,从根节点开始寻找存放的节点位置,找到“AB”叶子节点,将其放进去,

image

但此时该叶子节点包含了“ABC”三个项目,需要将该节点进行分裂操作,分裂的具体过程如下,找到该节点三个项目中中间大的项,

image

上移成为最小项和最大项的父节点,而最小项作为中间项的左子节点,最大项作为中间项的右子节点。

image

继续插入“D”节点,从根节点开始寻找,

image

大于“B”,所以往右,

image

找到“C”节点,并合并到该叶子节点,该节点只有两个项目,不必分裂。

image

继续插入“E”,查找到“CD”叶子节点,放入“E”节点后发现该叶子节点有三个项目,需要分裂,

image

将中间项提升到父节点,其余两项分裂成两个子节点,“D”上升到父节点后存放在右边,而且父节点只有两个项目,不必再继续分裂。

image

继续插入“F”节点,

image

往下看连续分裂两次的情况,继续插入“G”节点,大于“B”,继续比较,

image

大于“D”,往右子节点,

image

到右子节点后与“F”比较,发现大于“F”,放到右边,

image

image

发现“EFG”叶子节点有三个项目,必须分裂,

image

将中间项“F”提升到父节点,“E”和“G”左右两项分别称为左右子节点,

image

提升到父节点后发现父节点包含了“BDF”三项,也需要分裂,于是准备将中间项“F”提升,

image

发现“BDF”节点本来属于根节点,那么分裂后就没有根节点了,于是需要创建一个新节点作为根节点,即提升的“D”节点作为新的根节点。“B”和“F”左右两项分别作为左右子节点。

image

总结起来就是:一个节点插入到一棵2-3树中,先寻找该节点应该落到哪个叶子节点上,注意一定是在叶子节点。将新节点作为一个新项加入到叶子节点中,此时如果该节点只有两个项目,则完成插入操作。但如果该节点有三个项目,则需要进行分裂操作,左中右三项按大小排序,将中间项提升到父节点中,而左右两项作为左右子节点,然后可能还没完,因为父节点上可能又包含了三个项目,如果是这样还得做分裂操作,一直递归到父节点只包含一个或两个项目。

查找

2-3树的查找与二叉树的查找类似,从根节点开始比较,如果相等则查找成功,否则往下继续查找,对于只有两个子节点的节点则在其左右子树中递归查找,而对于有三个子节点的节点则需要在左中右子树中递归查找。

如下2-3树,查找“C”节点,

image

从根节点开始,与“D”比较,“C”小于“D”则往左,

image

继续与“B”比较,“C”大于“B”则往右,

image

“C”与“C”相等,找到。

image

如果要查找“H”节点,从根节点开始,“H”大于“D”则往右,

image

在“FH”节点中逐个项比较,先跟“F”项比较,“H”大于“F”,继续比较下一项,

image

“H”等于“H”,找到,在“FH”节点中找到“H”。

image

如果要查找“G”节点,从根节点开始,“G”大于“D”则往右,

image

“G”与“FH”节点逐个比较,大于“F”,继续比较下一项,

image

“G”小于“H”,即“G”间于“F”和“H”之间,于是往中间,

image

“G”等于“G”,找到。

image

赞(2) 打赏

如未加特殊说明,此网站文章均为原创,转载必须注明出处。Java 技术驿站 » 看图轻松理解数据结构与算法系列(2-3树)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注【Java 技术驿站】公众号,每天早上 8:10 为你推送一篇技术文章

扫描二维码关注我!


关注【Java 技术驿站】公众号 回复 “VIP”,获取 VIP 地址永久关闭弹出窗口

免费获取资源

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

支付宝扫一扫打赏

微信扫一扫打赏