什麼時候非二進制數據結構比二進制數據結構更好？ （即堆，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個參數的二進制操作。