2-3树

╰+哭是因爲堅強的太久メ 2021-07-24 22:24 341阅读 0赞

# 一 2-3树基本介绍 #

2-3树是最简单的B树, 具有如下特点:

*  2-3树的所有叶子节点都在同一层。(注：只要是B树都满足这个条件。)
 *  有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点。
 *  有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点。
 *  2-3树是由二节点和三节点构成的树。

# 二 2-3树构建规则 #

1 2-3树的所有叶子节点都在同一层。(注：只要是B树都满足这个条件。)

2 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点。

3 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点。

4 当按照规则插入一个数到某个节点时，不能满足上面三个要求，就需要拆，先向上拆，如果上层满，则拆本层，拆后仍然需要满足上面3个条件。

5 对于三节点的子树的值大小仍然遵守(BST 二叉排序树)的规则。

# 三 2-3树构建过程 #

将数列\{16, 24, 12, 32, 14, 26, 34, 10, 8, 28, 38, 20\} 构建成2-3树，并保证数据插入的大小顺序。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

# 四 其他说明 #

除了2-3树，还有2-3-4树等，概念和2-3树类似，也是一种B树。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/f6704d7d574b4150aecf35d83141dc1f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 1]: /images/20210724/ba67ca413cba401491775f3e37bba886.png

发表评论取消回复

表情：

评论列表（有 0 条评论，341人围观）

还没有评论，来说两句吧...

相关阅读

相关 Day23——二叉树专题

文章目录二叉树定义递归三部曲前序遍历中序遍历

曾经终败给现在/ 2024年04月01日 13:02/ 0 赞/ 33 阅读

相关第五章树 23 AcWing 1623. 中缀表达式

第五章树 23 AcWing 1623. 中缀表达式原题链接 [AcWing 1623. 中缀表达式][AcWing 1623.] 算法标签模拟树的

柔情只为你懂/ 2023年09月24日 14:07/ 0 赞/ 33 阅读

相关 23_____二叉搜索树的后序遍历

知识摘要： 1.二叉搜索树(又叫：二叉排序树，二叉查找树)：遵循： Tree.left.val<Tree.val<Tree.right.val. 所以它的中序遍历一

本是古典何须时尚/ 2023年08月17日 17:22/ 0 赞/ 54 阅读

相关 23流水线

public static void main(String args[]) { Scanner in = new Scanner(Syste

太过爱你忘了你带给我的痛/ 2022年09月02日 04:28/ 0 赞/ 161 阅读

相关 leetcode23

LeetCode23----------Merge K Sorted Lists 这道理暴力搜索两两合并排序肯定超时的，这个我试过。。。题目给的Tag是分治法，我就用分治

朱雀/ 2022年08月09日 02:22/ 0 赞/ 66 阅读

相关面试题23：从上往下打印二叉树

面试题23：从上往下打印二叉树题目描述从上往下打印出二叉树的每个节点，同层节点从左至右打印。代码： package offe

￡神魔★判官ぃ/ 2022年07月12日 05:50/ 0 赞/ 131 阅读

相关 2-23

1 接受数据库数据的数据类型与数据库数据的类型不兼容解决办法：把接收数据类型换为Object类型。 2 笔记本运行程序时有红字提醒。解决办法：更换

迈不过友情╰/ 2022年06月15日 05:13/ 0 赞/ 133 阅读

相关 7-23 还原二叉树（25 分）

给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。输入格式: 输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均

桃扇骨/ 2022年04月22日 03:12/ 0 赞/ 170 阅读

相关 23 形容词

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

迷南。/ 2022年04月05日 13:42/ 0 赞/ 207 阅读

相关 7-23 还原二叉树（25 分)

7-23 还原二叉树（25 分) 给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。输入格式: 输入首先给出正整数N（≤50），为树中结点总数。

比眉伴天荒/ 2022年02月27日 14:28/ 0 赞/ 146 阅读