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

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

我想要一个 BST ,它是存储超过一千万个节点的最佳选择。节点的插入顺序基本上是随机的,我永远不需要删除节点,所以插入时间是唯一需要优化的东西。

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

0
额外 编辑
意见: 3

2 答案

Red-black is better than AVL for insertion-heavy applications. If you foresee relatively uniform look-up, then Red-black is the way to go. If you foresee a relatively unbalanced look-up where more recently viewed elements are more likely to be viewed again, you want to use splay trees.

0
额外

为什么要使用 BST ?从你的描述来看,字典也可以起作用,如果不是更好的话。

使用 BST 的唯一原因是如果您想按键顺序列出容器的内容。这当然听起来不像你想要做的那样,在这种情况下去散列表。 O(1)插入和搜索,不用担心删除,有什么可以更好?

0
额外