二叉树以外不同类型树ADT的差异

Question

除了二进制和二进制搜索树之外，我不确定以下基于树的数据结构之间的根本区别是什么。有些树仅仅是另一棵树的子集吗？有些树是完全相同的，但有不同的命名吗？

1. B-树
2. B+树
3. K-列树
4. k-d树
5. N叉树
6. 四叉树
7. 2-3树
8. 2-3-4树
9. M-树
10. M-列树

唯一定义非常清楚且没有重叠的树是二进制树、二进制搜索树，甚至是尝试树。

除此之外，谷歌对上面列出的树的搜索结果导致了这么多不同的定义，有些是重叠的，有些是非常不同的。例如，一个人对b树的实现与另一个人的实现是如此的不同，以至于它实际上需要改变定义。到了这个地步，所有这些定义都开始把我搞糊涂了。是否有可视为标准圣经的所有上述树数据结构的书籍？一些澄清将是非常感谢的。

Answer 1

大多数，尽管可能不是全部，都是在Aho，Hopcroft和Ullman的数据结构和算法中

提示是，任何以-ary命名的树都是具有定义分支度的树，因此二叉树每个节点有两个(可能为空)子节点；n个-ary树每个节点有n个(可能为空)子节点。

列表中的大多数人在定义和算法上都有某种平衡，以使他们最坏的情况行为保持在O(n log n)，而没有平衡的情况下，他们通常有O(n^2)的最坏情况行为。

四叉树将是例外，因为它是一种划分空间的方法，用于图形和图像处理算法。