我已经能够BST通过几个来源找到关于几个 self-balancing 的详细信息，但是我没有找到任何好的描述来详细说明在不同情况下哪个最好使用（或者如果它真的无关紧要）。
我想要一个BST最适合存储超过一千万个节点的设备。节点的插入顺序基本上是随机的，我永远不需要删除节点，所以插入时间是唯一需要优化的东西。
我打算用它来存储以前访问过的游戏状态在一个益智游戏中，这样我就可以快速检查以前的配置是否已经遇到过。
问问题
1361 次
4 回答
4
对于插入繁重的应用，红黑比 AVL 更好。如果您预见到相对统一的查找，那么红黑是要走的路。如果您预见到相对不平衡的查找，其中最近查看的元素更有可能再次被查看，您希望使用splay trees。
于 2008-08-05T15:59:27.563 回答
3
为什么要使用 a BST？根据您的描述，如果不是更好的话，字典也可以正常工作。
使用 a 的唯一原因BST是如果您想按键顺序列出容器的内容。听起来您当然不想这样做，在这种情况下，请使用哈希表。O(1)插入和搜索，不用担心删除，还有什么更好的呢？
于 2008-08-29T00:10:46.930 回答
0
BST我最熟悉的两个自平衡是 red-black 和AVL，所以我不能肯定是否有其他解决方案更好，但我记得，red-black 与 相比具有更快的插入和更慢的检索AVL。
因此，如果插入的优先级高于检索，那么红黑可能是更好的解决方案。
于 2008-08-05T15:50:05.120 回答
-2
[哈希表有] O(1) 插入和搜索
我认为这是错误的。
首先，如果将键空间限制为有限，则可以将元素存储在数组中并进行 O(1) 线性扫描。或者您可以对数组进行随机排序，然后在 O(1) 预期时间内进行线性扫描。当东西是有限的时，东西很容易 O(1)。
因此，假设您的哈希表将存储任意位字符串；没关系，只要有一组无限的键，每个键都是有限的。然后您必须读取任何查询和插入输入的所有位，否则我将 y0 插入一个空哈希并查询 y1，其中 y0 和 y1 在您不查看的单个位位置不同。
但是假设密钥长度不是参数。如果您的插入和搜索需要 O(1)，特别是散列需要 O(1) 时间，这意味着您只能查看来自散列函数的有限输出（可能只有有限输出，授予）。
这意味着对于有限多个桶，必须有无限的字符串集，它们都具有相同的哈希值。假设我插入了很多，即 ω(1)，然后开始查询。这意味着您的哈希表必须依靠其他一些 O(1) 插入/搜索机制来回答我的查询。哪一个，为什么不直接使用它呢？
于 2009-02-01T12:49:56.797 回答