最佳自平衡BST，可快速插入大量节点

Question

我已经找到了一些自平衡的详细信息 BST通过多个来源，但我还没有找到任何好的描述，详细说明哪一个最适合在不同情况下使用（或者如果它真的不重要）。

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

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

Answer 1

红黑 对于插入量大的应用来说，它比 AVL 更好。如果您预见到相对统一的查找，那么红黑就是正确的选择。如果您预见到相对不平衡的查找，其中最近查看的元素更有可能再次查看，那么您需要使用 八字树.

Answer 2

为什么要使用一个 BST 根本吗？根据您的描述，字典即使不是更好，也同样有效。

使用的唯一原因 BST 如果您想按关键顺序列出容器的内容，则会出现这种情况。听起来您肯定不想这样做，在这种情况下，请使用哈希表。 O(1) 插入和查找，不用担心删除，还有什么更好的呢？

Answer 3

两者自平衡 BST我最熟悉的是红黑和 AVL, ，所以我不能肯定地说是否还有其他解决方案更好，但据我记得，与相比，红黑具有更快的插入速度和更慢的检索速度 AVL.

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

Answer 4

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

我认为这是错误的。

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

假设您的哈希表将存储任意位字符串；这并不重要，只要有无限组键，每个键都是有限的。然后你必须读取任何查询和插入输入的所有位，否则我将 y0 插入一个空散列中并在 y1 上查询，其中 y0 和 y1 在你不看的单个位位置上不同。

但假设密钥长度不是参数。如果您的插入和搜索需要 O(1) 时间，特别是散列需要 O(1) 时间，这意味着您只查看散列函数的有限数量的输出（从中可能有 是 只有有限的输出，当然）。

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