什么时候非二进制数据结构比二进制数据结构更好？ （即堆，BST等）

Question

CS中的很多数据结构都是二进制的（BST，堆等）。以非二进制形式实现它们的理由是什么？ IE浏览器。有3个孩子对于每个节点等

Answer 1

树木与每个节点多于两个孩子的折衷堆，因为他们将在每个节点更多的链接为代价具有浅的深度。通常用于数据库和文件系统的B-tree是每个节点具有多个链接的树结构的典型示例。这种结构与文件系统非常吻合，因为可以调整B树节点的大小以与文件系统块或群集的大小紧密匹配。

Answer 2

二叉树有比较大的空间开销。例如，在实施一系列二叉搜索树的节点包含四个字段，key，left和right。由于key是你唯一真正感兴趣和left和right指针只是簿记数据结构，这是2/3的开销。

相比之下，三元搜索树节点将有五个领域：key1和key2，加上指针left，middle和right。这只是3/5的开销，并且对于更大的节点，开销的相对量进一步减少。当然，在某些时候，结构会变得太大而无法管理，所以您可以从更大的节点中挤出的性能数量受到限制;该限制取决于应用程序。 （我甚至没有考虑内存分配引起的开销，随着节点变大，这也会下降。还有其他的原因是有更大的节点，例如2-3 tree比二叉搜索树有更好的渐近复杂性。）

Answer 3

当操作是二进制的，你会使用二进制数据结构。当操作是三元时，您可以使用三元数据结构。二进制数据结构常见的一个原因是大多数操作是二进制的。对于例如如果你想比较4个元素，你一次可以比较2个元素。这与+,-,*,/一样。以TreeSet或TreeMap为例，它是一棵红黑树。您提供了一个比较器，然后执行：

这是比较2个参数的二进制操作。