AVL树和八字树的区别
我正在研究各种树，遇到了AVL树和八字树。我想知道
- AVL 树和 splay 树有什么区别？
- 我们选择这些树木的依据是什么？
- 这些树的优点和缺点是什么？
- 这些树在大 O 表示法中的表现是什么？
I am studying about various trees, and came across AVL trees and splay trees. I want to know
- What is difference between AVL trees and splay trees?
- On what basis do we select these tress?
- What are positive's and negative's of these trees?
- What are the performances of these trees in terms of big O notation?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
回答您的问题：
AVL树和展开树有什么区别？展开树和AVL树都是二叉搜索树，具有出色的性能保证，但它们不同之处在于他们如何实现这些保证的性能。在 AVL 树中，树的形状始终受到约束，以使树的形状保持平衡，这意味着树的高度永远不会超过 O(log n)。该形状在插入和删除时保持不变，并且在查找期间不会改变。另一方面，展开树通过重塑树来响应对树的查找来保持效率。这样，经常访问的元素就会向上移动到树的顶部，并且具有更好的查找时间。伸展树的形状不受限制，并且根据执行的查找而变化。
我们选择这些树的依据是什么？对此没有硬性规定。然而，这些结构之间的一个关键区别是 AVL 树保证每个操作的快速查找 (O(log n))，而展开树只能保证任何 n 个操作序列最多花费 O(n log n) 时间。这意味着如果您需要实时查找，AVL 树可能会更好。但是，平均而言，展开树往往要快得多，因此如果您想最大程度地减少树查找的总运行时间，则展开树可能会更好。此外，splay树非常高效地支持一些操作，例如分裂和合并，而相应的AVL树操作则更加复杂且效率较低。 Splay 树比 AVL 树更节省内存，因为它们不需要在节点中存储平衡信息。然而，AVL 树在具有大量查找的多线程环境中更有用，因为 AVL 树中的查找可以并行完成，而在展开树中则不能。由于展开树根据查找来重塑自身，因此如果您只需要访问树中元素的一小部分，或者如果您访问某些元素的次数远多于其他元素，则展开树的性能将优于 AVL 树。最后，展开树往往比 AVL 树更容易实现，因为旋转逻辑更容易。
这些树的优点和缺点是什么？请参阅我对上面 (2) 的回答。
这些树在大 O 表示法方面的性能如何？ AVL 树插入、删除和查找每次都需要 O(log n) 时间。八字树具有这些相同的保证，但保证只是摊销意义上的。任何长操作序列最多将花费 O(n log n) 时间，但单个操作可能花费多达 O(n) 时间。
To answer your questions:
What is the difference between AVL trees and splay trees? Both splay trees and AVL trees are binary search trees with excellent performance guarantees, but they differ in how they achieve those guarantee that performance. In an AVL tree, the shape of the tree is constrained at all times such that the tree shape is balanced, meaning that the height of the tree never exceeds O(log n). This shape is maintained on insertions and deletions, and does not change during lookups. Splay trees, on the other hand, maintain efficient by reshaping the tree in response to lookups on it. That way, frequently-accessed elements move up toward the top of the tree and have better lookup times. The shape of splay trees is not constrained, and varies based on what lookups are performed.
On what basis do we select these trees? There is no hard-and-fast rule about this. However, one key difference between the structures is that AVL trees guarantee fast lookup (O(log n)) on each operation, while splay trees can only guarantee that any sequence of n operations takes at most O(n log n) time. This means that if you need real-time lookups, the AVL tree is likely to be better. However, splay trees tend to be much faster on average, so if you want to minimize the total runtime of tree lookups, the splay tree is likely to be better. Additionally, splay trees support some operations such as splitting and merging very efficiently, while the corresponding AVL tree operations are more involved and less efficient. Splay trees are more memory-efficient than AVL trees, because they do not need to store balance information in the nodes. However, AVL trees are more useful in multithreaded environments with lots of lookups, because lookups in an AVL tree can be done in parallel while they can't in splay trees. Because splay trees reshape themselves based on lookups, if you only need to access a small subset of the elements of the tree, or if you access some elements much more than others, the splay tree will outperform the AVL tree. Finally, splay trees tend to be easier to implement than AVL trees, since the rotation logic is much easier.
What are the positives and negatives of these trees? See my answer to (2) above.
What are the performances of these trees in terms of big-O notation? AVL tree insertion, deletion, and lookups take O(log n) time each. Splay trees have these same guarantees, but the guarantee is only in an amortized sense. Any long sequence of operations will take at most O(n log n) time, but individual operations might take as much as O(n) time.
它们的结构和我们调用它们的操作相似。不同之处在于，在展开树中，每次操作后，我们都会尝试使树保持几乎完美的平衡，以便将来的操作花费更少的时间。
当您的应用程序处理树中的大量数据，但需要比其他应用程序更频繁地访问数据子集时，展开树总是比二叉搜索树更好。在这种情况下，由于展开，您经常访问的数据将接近根。此外，访问任何节点都可以用比以前更少的时间。
作为选择这些树的一般规则，如果您需要一段树操作的“平均”log(n) 时间，则使用展开树。二叉树不能保证这一点。
两者的优点是理论上你可以在这两种数据结构中绕过 log(n) 。
如前所述，展开树在多次操作中具有平均 log(n)。这意味着，也许您在该集合中至少有一次操作的时间复杂度。但是，当访问频繁的项目时，这将得到补偿。
二叉搜索树的缺点是，你需要幸运地始终拥有 log(n) 。如果键不是随机的，那么树将简化为只有一侧的列表形式。
一组树操作的平均展开树 Log(n)
仅当您的密钥是随机的时，二叉树 Log(n) 才有效。
运行时的结果是显而易见的 这里。
您可以看到使用和不使用展开搜索的运行时差异。
They are similar in structure and the operations we call on them. The difference is that in splay trees, after each operation, we try to keep the tree almost perfectly balanced so that future operations take less time.
Splay trees are always better than binary search trees when, your application deals with a lot of data in the tree but, will need access to a subset of the data very frequently than others. In this case the data you access frequently will come near the root as a result of the splay. Also, any node can then be accessed with less time than before.
As a general rule for selecting these trees, if you need "Average" log(n) time over a period of tree operations then use splay tree. Binary tree cannot guarantee this.
Positives for both is that you get around log(n) in both these data structures theoretically.
As mentioned splay trees have average log(n) over a number of operations. This means that, maybe you got n time complexity for an operation atleast once in that set. But this will be compensated when accessing the frequent items.
The negative of the binary search tree is that, you need to be lucky to have log(n) always. If the keys are not random, then the tree will reduce to a list like form with only one side.
Splay tree Log(n) on Average for a group of tree operations
Binary tree Log(n) only if your keys are going in random.
The results on the runtime are obvious here.
You can see the runtime difference in searching with and without splaying.