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

Question

我已经能够BST通过几个来源找到几个自平衡的细节,但是我没有找到任何好的描述,详细描述哪个最适合在不同的情况下使用(或者如果它真的无关紧要).

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

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

Answer 1

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