是一个二叉树的二叉树吗？

Question

当我搜索上述问题时，我得到了一个答案Yes。

一个完整的二进制树的定义如下：

完整二进制树（有时适当二叉树或2-树）是一个树，其中除叶子之外的每个节点有两个孩子。

但问题是，这个属性可能不能满足我每次构建的顺序2.

B树例如时间：

插入10,17,45中顺序B树2

，我们得到的是结构

10 
    17 
     45 

这不是一个完整的二叉树。

那么为什么说它是一个二叉树的二叉树？

Answer 1

对于B树而言，术语“订单”的定义很差，几乎没有用处......每个人都以不同的方式使用该术语。对于任何种类的B树，节点中指针的数量由该节点中的键的数量决定。如果密钥的数量是k，则指针的数量是k + 1，周期。关于指针的数量是没有选择的，因为在其他类型的树中可能存在。一个节点中的所有指针都是零（在单级“树”中的根，树叶），或者全部都是有效的，没有中间的，也没有混合。

其次，为了使B树能够正常工作，需要在键的数量上进行选择。这意味着最小的可能的B树节点是具有一个或两个键（因此有两个或三个指针）的节点。这基本上是一个（2,3）树，据说这正是B树如何被发明 - 作为（2,3）树的泛化。

插入钥匙10，17和45到可能的最低阶的空B-树会是这样的：

[] 

[10] 

[10 17] 

    [17] 
[10] [45] 

最终的结果确实发生，看起来像一个平衡二叉树。

但是，由于上述原因，在您似乎使用该术语（每个节点最多两个指针）的意义上，没有2阶B树。将多个密钥插入这样一个退化的B树时，不可能保持B树不变量。

注意：有许多B树变种可以暂时或甚至永久地破坏经典B树的结构不变量，主要用于实现性能目标，简化维护或实现特殊属性，少并发操作。尽管它们的名字中可能包含“B树”，但这些不会被视为适合本次讨论的B树。