我已经可以通过多个来源找到有关多个自平衡BST的详细信息，但是我没有找到任何好的描述来详细说明哪种BST可以在不同情况下使用(或者，如果真的没有关系) 。

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

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

解决方案

回答

我最熟悉的两个自平衡BST是红黑和AVL，因此无法确定是否有其他解决方案更好，但是我记得红黑的插入速度更快与" AVL"相比，检索速度较慢。

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

回答

对于大量插入的应用，红黑优于AVL。如果我们预见到相对统一的查找方式，那么红黑是必经之路。如果我们预见到相对不平衡的查找，其中最近查看的元素更有可能再次被查看，则我们想使用展开树。

回答

为什么要全部使用" BST"？根据描述，即使不是更好，字典也将同样有效。

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

回答

[hash tables have] O(1) insertion and search

我认为这是错误的。

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

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

但是，可以说密钥长度不是参数。如果插入和搜索花费O(1)，特别是散列花费O(1)时间，这意味着我们仅查看来自散列函数的有限量的输出(从中可能仅获得有限的输出， )。

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