我正在研究各种树，遇到了 AVL 树和八角树。我想知道
- AVL 树和 splay 树有什么区别？
- 我们选择这些树的依据是什么？
- 这些树的正面和负面是什么？
- 这些树在大 O 表示法方面的表现如何？
最佳答案
回答您的问题:
AVL树和splay树的区别是什么？splay树和AVL树都是二叉搜索树，性能保证非常好，但是区别在于他们如何实现那些保证性能。在 AVL 树中，树的形状始终受到约束，使得树的形状是平衡的，这意味着树的高度永远不会超过 O(log n)。此形状在插入和删除时保持不变，并且在查找期间不会更改。另一方面，Splay 树通过 reshape 树以响应对它的查找来保持高效。这样，经常访问的元素就会向上移动到树的顶部，并有更好的查找时间。 splay 树的形状不受限制，并根据执行的查找而变化。
我们选择这些树的依据是什么？ 关于这一点没有硬性规定。然而，这两种结构之间的一个关键区别是 AVL 树保证每个操作的快速查找 (O(log n))，而 splay 树只能保证任何 n 个操作序列最多花费 O(n log n) 时间。这意味着如果您需要实时查找，AVL 树可能会更好。然而，平均而言，splay 树往往要快得多，所以如果你想最小化树查找的总运行时间，splay 树可能会更好。此外，splay tree 支持一些操作，如 split 和合并非常高效，而相应的 AVL tree 操作涉及更多且效率较低。 Splay 树比 AVL 树更节省内存，因为它们不需要在节点中存储余额信息。但是，AVL 树在具有大量查找的多线程环境中更有用，因为 AVL 树中的查找可以并行完成，而在 splay 树中则不能。由于 splay 树根据查找 reshape 自身，如果您只需要访问树元素的一小部分，或者如果您访问某些元素的次数比其他元素多得多，则 splay 树将优于 AVL 树。最后，splay 树往往比 AVL 树更容易实现，因为旋转逻辑要容易得多。
这些树的优点和缺点是什么？请参阅我对上面 (2) 的回答。
这些树在大 O 表示法方面的表现如何？ AVL 树的插入、删除和查找需要 O(log n) 时间每个。 Splay 树具有这些相同的保证，但保证仅在摊销意义上。任何较长的操作序列最多需要 O(n log n) 时间，但单个操作可能需要多达 O(n) 时间。
关于algorithm - AVL树和splay树的区别，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7467079/