您会在生产环境中的哪些地方使用 splay-tree。我指的是真实生活的例子。
我正在考虑使用尝试和拉伸(stretch)树实现自动完成。对于大型数据集，从节点 x 到叶子遍历 trie 以返回结果并不是一个好主意，因此我们的想法是在 trie 的节点内有一个 splay 树，因此当用户输入“sta”时，它将转到 s-t-a , 'a' - 节点然后返回 splay 树中的前 5 个元素(通过 BFS/level 遍历，这不一定会改变/修改树)
当然，在选择了自动完成变体之后，我们应该向上遍历 trie 并更新这些节点内的所有伸展树(Splay Tree)。
由于 splay 树在并发环境中很敏感，我质疑它在生产中的使用
你的想法？
最佳答案
伸展树(Splay Tree)不适合很少或从不更改的数据，尤其是在线程环境中。读取操作期间的额外突变会破坏内存缓存，并可能产生不必要的锁争用。在任何情况下，对于只读数据结构，您都可以一次性计算一棵最优树。即使该计算速度很慢，也不会对长期执行时间产生影响。
我并不完全相信大型尝试很慢的说法，当然在自动完成器的情况下也不是如此。即使在不太现代的硬件上，与用户键入字符所花费的时间，甚至是底层键盘驱动程序和输入处理器将按键传递到你的申请。
如果您真的需要优化一个 trie，那么有充分的理由相信，一旦备选方案可以放入缓存行，就可以将在根部带有 trie 的混合数据结构与线性(或二进制)搜索相结合。这最大限度地发挥了 trie 的大扇出的优势，同时避免了糟糕的缓存行为和行尾的过多存储开销。
伸展树(Splay Tree)在经常修改的数据结构上最有用(如果它们真的有用的话)。 ckassic 示例是一个“绳索”数据结构(字符串段树)，这是一种通过避免大字符串副本来尝试优化文本编辑器的方法。与确定性树平衡算法(如 RB 树)相比，伸展树(Splay Tree)算法具有简单的优点，并且只接触构成树遍历一部分的节点。
然而，自平衡树库(许多现代编程语言的标准库的一部分)的现成可用以及经常令人失望的实证结果使 splay 算法充其量只是一个小众产品，尽管它确实是一个迷人的想法.
关于algorithm - Splay tree 现实生活中的应用，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47654564/