在生产中，您将在哪里使用splay tree。我是说一个真实的例子。
我在考虑使用tries和splay树实现自动完成。对于大型数据集，从节点x遍历trie到叶子返回结果不是一个好主意，所以这个主意是在trie的节点内有一个splay树，所以当用户输入“s t a”时，它将转到s-t-a，“a”节点，然后返回splay树中的前5个元素（通过BFS/级别遍历不一定会变异/修改树）
当然，在选择了autocomplete变量之后，我们应该遍历trie并更新这些节点中的所有splay树。
因为splay树在并发环境中是敏感的，所以我质疑它在生产中的使用
你的想法？
最佳答案
Splay树与很少或从不更改的数据不太匹配，特别是在线程环境中读取操作期间的额外突变会破坏内存缓存，并可能造成不必要的锁争用。在任何情况下，对于只读数据结构，都可以一次性计算最优树即使计算速度很慢，也不会影响长期的执行时间。
我不完全相信这种说法，即大型尝试是缓慢的，当然不是在自动完成的情况下。即使在不那么现代的硬件上，trie遍历的成本与用户键入字符所需的时间，甚至与底层键盘驱动程序和输入处理器将按键发送到应用程序所需的时间相比，都是微不足道的。
如果您真的需要优化trie，那么有充分的理由相信，一旦备选方案可以放入缓存线，那么在根目录下使用trie的混合数据结构就可以与线性（或二进制）搜索相结合这最大限度地提高了TIE的大扇出的好处，同时避免了恶劣的缓存行为和过度的存储开销在线的末尾。
对于经常修改的数据结构，展开树是最有用的（如果它们很有用的话）ckassic示例是一个“rope”数据结构（字符串段树），这是一种通过避免大量字符串复制来优化文本编辑器的方法。与rb-trees等确定性树平衡算法相比，splay-tree算法具有简单性的优点，并且只涉及构成树遍历一部分的节点。
然而，自平衡树库（许多现代编程语言的标准库的一部分）的现成可用性，加上经常令人失望的经验结果，使得splay算法充其量只是一个小众产品，尽管它确实是一个迷人的想法。