3

CS 中的许多数据结构都是二进制的（BST、堆等）。以非二进制形式实现它们的充分理由是什么？IE。每个节点都有一个包含 3 个子节点的堆，等等。

4

3 回答 3

2

每个节点具有两个以上子节点的树是一种折衷，因为它们的深度较浅，但每个节点的链接更多。B -tree常用于数据库和文件系统，是每个节点具有多个链接的树结构的经典示例。这种结构非常适合文件系统，因为可以调整 B 树节点的大小以与文件系统块或集群的大小紧密匹配。

于 2012-07-15T22:38:20.327 回答
1

二叉树的空间开销相对较大。例如，实现集合的二叉搜索树中的节点包含四个字段key，left和right。由于key是您真正感兴趣的唯一事物，并且left和right指针只是数据结构的簿记，因此这是 2/3 的开销。

相比之下，三元搜索树节点将有五个字段：key1和key2，加上指针left，middle和right。这只是 3/5 的开销，并且对于更大的节点，开销的相对量会进一步减少。当然，在某些时候，结构会变得太大而无法管理，因此您可以从更大的节点中挤出的性能数量是有限的；该限制取决于应用程序。

（我什至没有考虑内存分配引起的开销，随着节点变大，开销也会下降。拥有更大的节点还有其他原因，例如2-3 树比二叉搜索树具有更好的渐近复杂度。）

于 2012-07-15T22:44:40.013 回答
1

当操作是二进制时，您将使用二进制数据结构。当操作是三元时，您将使用三元数据结构。二进制数据结构常见的一个原因是大多数操作都是二进制的。例如，如果要比较 4 个元素，则一次比较 2 个元素。与 相同+,-,*,/。以 Java 中的 TreeSet 或 TreeMap 为例，它是一棵红黑树。您为它提供一个 Comparator 并实现：

compare(T o1, T o2)

这是比较 2 个参数的二元运算。

于 2012-07-16T05:54:21.753 回答