AVL树和展开树之间的区别

Question

我正在研究各种树木,并遇到了AVL树木和树木.我想知道

1. AVL树和splay树有什么区别？
2. 我们在什么基础上选择这些发辫？
3. 这些树的积极和消极是什么？
4. 这些树的大O符号表现如何？

Answer 1

1. splay树和AVL树都是具有出色性能保证的二叉搜索树,但它们在如何保证性能方面存在差异.在AVL树中,树的形状始终受到约束,使树形状平衡,这意味着树的高度永远不会超过O(log n).此形状在插入和删除时保持不变,并且在查找期间不会更改.另一方面,Splay树通过重新形成树来响应对其的查找而保持高效.这样,经常访问的元素向上移动到树的顶部并具有更好的查找时间.展开树的形状不受约束,并且根据执行的查找而变化.

2. 对此没有严格的规定.然而,结构之间的一个关键区别是AVL树保证在每个操作上快速查找(O(log n)),而splay树只能保证n个操作的任何序列最多花费O(n log n)时间.这意味着如果您需要实时查找,AVL树可能会更好.但是,splay树的平均速度往往要快得多,因此如果要最小化树查找的总运行时间,splay树可能会更好.另外,splay树支持一些操作,例如非常有效地分割和合并,而相应的AVL树操作更复杂且效率更低.Splay树比AVL树更具内存效率,因为它们不需要在节点中存储余额信息.但是,AVL树在具有大量查找的多线程环境中更有用,因为AVL树中的查找可以并行完成,而不能在splay树中进行.因为splay树基于查找重塑自己,如果您只需要访问树的一小部分元素,或者如果您访问某些元素比其他元素更多,则splay树将胜过AVL树.最后,splay树比AVL树更容易实现,因为旋转逻辑更容易.

3. 见(2)

4. AVL树插入,删除和查找每个都需要O(log n)时间.Splay树有这些相同的保证,但保证只是在摊销意义上.任何长时间的操作都将花费最多O(n log n)时间,但是单独的操作可能花费O(n)时间.

希望这可以帮助!