data-structures - 使用 2-3-4 树而不是展开树

Question

我现在正在学习数据结构课程，我们学习了 2-3-4 树和展开树。我想知道在什么情况下你会使用 2-3-4 树而不是 splay 树？它们都是自我平衡和排序的，所以我看不出它们之间有太大的区别。

Answer 1

2-3-4 树只在插入和删除时改变结构，而splay-tree也在搜索时重新组织节点。

如果您的典型使用模式碰巧在大多数时间查找一小部分元素，则展开树将由于查找时的重新组织而提供更快的响应。

可以实现一个 2-3-4 树，以便可以在 O(1) 中查找最小元素，但通常两者都在摊销 O(log n) 时提供插入和删除。