数据结构系列之什么是2-3-4树?

原创
08/08 00:41
阅读数 14

1、什么是2-3-4树?

2-3-4树是四阶的B树(Balance Tree),是一种多路查找树,要求所有的节点都拥有相同的深度。

节点只能是2-节点,3-节点,4-节点之一。

  • 2-节点:包含1个元素的节点,有2个子节点
  • 3-节点:包含2个元素的节点,有3个子节点
  • 3-节点:包含3个元素的节点,有4个子节点

2-3-4树节点至少有1个元素,符合二叉查找树的性质,即父节点大于左子节点,小于右子节点,但对于2-3-4树有多个元素时,每个元素必须大于它左边的和它的左子树中元素

在这里插入图片描述

2、2-3-4树的查询

2-3-4树的查询操作像普通的二叉搜索树一样,但由于其结点元素数不确定,在一些编程
语言中实现起来并不方便,实现一般使用它的等同树,红黑树,即转换为红黑树,然后进行查找

3、2-3-4树生成过程

本文同步分享在 博客“smileNicky”(CSDN)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部