2-3树叶子节点是否为空？

Question

2-3树是特殊的B-tree
B-Tree中的叶子节点到底是不是null？也就是2-3树的叶子节点是不是null
网上看到这样的B-Tree结论：所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；
但是同时又看到了这样的结论：叶子节点包含的关键字和其他节点包含的关键字不能重复。
同时又说2-3,2-3-4树是B-tree的特例。
红黑树的叶子节点已知NIL(NULL)。

Answer 1

liuyubobobo 2019-09-15 12:00:13

这两个描述确实是矛盾的。

在“所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；”这个描述下，是在说 B 树的叶子节点是 NIL

在“叶子节点包含的关键字和其他节点包含的关键字不能重复。”这个描述中，是在说 B 树的叶子节点是没有孩子节点的那个节点（但是存储了键）

其实对于B树，怎么定义叶子节点无所谓，因为对于 B 树来说，叶子节点和中间节点的结构是一样的，叶子节点没有什么特殊的。这是它和 B+ 树最大的区别。

对于“叶子节点包含的关键字和其他节点包含的关键字不能重复。”这个描述，我相信它想强调的是，B 树的所有节点中的关键字不会重复，特意强调这个“叶子节点”，应该是在和 B+ 树作比较。

P.S. 

我查了一下维基百科，对于维基百科 B 树词条正文的定义，B树的叶子节点是 NIL。但下面列出了，这一术语其实是有歧义的：

继续加油！：）

• 提问者 厥~~~ #1

  老师 那2-3树或者2-3-4树作为一种特殊的B-tree 他们的叶子节点是NIL(和红黑树一样）还是不是NIL?

• liuyubobobo 回复 提问者 厥~~~ #2

  怎么定义都可以。

• 提问者 厥~~~ 回复 liuyubobobo #3

  第一次碰到一棵树定义不清楚的。其他树的定义都是非常明确的。

点开查看后面1条评论