data structures -快速插入大量节点的最佳自平衡BST

Translate

我已经找到了一些自我平衡的细节BST通过多个来源获得,但我还没有找到任何好的描述来详细说明在不同情况下(或实际上是否无关紧要)最好使用哪个。

我想要一个BST最适合存储超过一千万个节点。节点的插入顺序基本上是随机的,并且我永远不需要删除节点,因此插入时间是唯一需要优化的事情。

我打算用它在益智游戏中存储以前访问的游戏状态,以便我可以快速检查是否已经遇到了以前的配置。

This question and all comments follow the "Attribution Required."

所有的回答

Translate

红黑在繁重的插入应用中比AVL更好。如果您预见到相对统一的查询,那么红黑是最好的选择。如果您预见到相对不平衡的查找,其中最近查看过的元素更有可能再次被查看,则您想使用八角树.

来源
Translate

为什么要使用BST完全没有?根据您的描述,即使不是更好,字典也将同样有效。

使用的唯一原因BST如果要按关键顺序列出容器的内容,将是这样。当然,这听起来并不像您想要的那样,在这种情况下,请使用哈希表。O(1)插入和搜索,无需担心删除,还有什么更好的选择?

来源
Anastasia Lee
Translate

两种自我平衡BST我最熟悉的是红黑色和AVL,所以我无法确定是否有其他解决方案会更好,但是我记得,与之相比,红黑的插入速度更快,检索速度较慢AVL.

因此,如果插入的优先级高于检索的优先级,那么红黑色可能是更好的解决方案。

来源
Translate

[哈希表具有] O(1)插入和搜索

我认为这是错误的。

首先,如果将键空间限制为有限的,则可以将元素存储在数组中并执行O(1)线性扫描。或者,您可以对数组进行随机排序,然后在O(1)的预期时间内进行线性扫描。当填充为有限时,填充很容易为O(1)。

假设您的哈希表将存储任意位字符串;没关系,只要有无限个键集,每个键都是有限的。然后,您必须读取所有查询和插入输入的所有位,否则我将y0插入一个空散列并在y1上进行查询,其中y0和y1在您未查看的单个位位置上不同。

但是,可以说密钥长度不是参数。如果您的插入和搜索花费O(1),特别是散列花费O(1)时间,这意味着您仅查看散列函数的有限量的输出(从中可能会be只授予有限的输出)。

这意味着对于有限数量的存储桶,必须有无限个字符串集,这些字符串都具有相同的哈希值。假设我插入了很多,即ω(1),然后开始查询。这意味着您的哈希表必须依靠其他O(1)插入/搜索机制来回答我的查询。哪一个,为什么不直接使用它呢?

来源