52

我正在研究各种树，遇到了 AVL 树和张开树。我想知道

  1. AVL树和splay树有什么区别？
  2. 我们选择这些树的依据是什么？
  3. 这些树的正面和负面是什么？
  4. 这些树在大 O 符号方面的表现如何？
4

2 回答 2

93

要回答您的问题：

  1. AVL树和splay树有什么区别？展开树和 AVL 树都是具有出色性能保证的二叉搜索树，但它们在实现这些性能保证方面的方式不同。在 AVL 树中，树的形状始终受到约束，因此树的形状是平衡的，这意味着树的高度永远不会超过 O(log n)。此形状在插入和删除时保持不变，并且在查找期间不会更改。另一方面，展开树通过重塑树以响应对其的查找来保持高效。这样，经常访问的元素会向上移动到树的顶部，并具有更好的查找时间。展开树的形状不受限制，并根据执行的查找而变化。

  2. 我们选择这些树的依据是什么？对此没有硬性规定。然而，结构之间的一个关键区别是 AVL 树保证每个操作的快速查找 (O(log n))，而 splay 树只能保证 n 操作的任何序列最多花费 O(n log n) 时间。这意味着如果您需要实时查找，AVL 树可能会更好。但是，平均而言，展开树往往要快得多，因此，如果您想最小化树查找的总运行时间，则展开树可能会更好。此外，splay tree 非常有效地支持一些操作，例如拆分和合并，而相应的 AVL 树操作涉及更多且效率较低。展开树比 AVL 树更节省内存，因为它们不需要在节点中存储平衡信息。然而，AVL 树在具有大量查找的多线程环境中更有用，因为 AVL 树中的查找可以并行完成，而它们不能在展开树中完成。因为 splay 树会根据查找来重塑自身，所以如果您只需要访问树元素的一小部分子集，或者如果您访问的某些元素比其他元素多得多，则 splay 树的性能将优于 AVL 树。最后，展开树往往比 AVL 树更容易实现，因为旋转逻辑要容易得多。展开树将优于 AVL 树。最后，展开树往往比 AVL 树更容易实现，因为旋转逻辑要容易得多。展开树将优于 AVL 树。最后，展开树往往比 AVL 树更容易实现，因为旋转逻辑要容易得多。

  3. 这些树的优点和缺点是什么？请参阅我对上面（2）的回答。

  4. 这些树在大 O 符号方面的表现如何？AVL 树的插入、删除和查找都需要 O(log n) 时间。展开树也有同样的保证，但保证只是摊销的意义。任何长序列的操作最多需要 O(n log n) 时间，但单个操作可能需要 O(n) 时间。

希望这可以帮助！

于 2012-02-04T22:06:39.363 回答
2
  1. AVL树和splay树有什么区别？

它们在结构和我们调用它们的操作上相似。不同之处在于，在展开树中，在每次操作之后，我们都尽量保持树几乎完美平衡，以便未来的操作花费更少的时间。

  1. 我们选择这些树的依据是什么？

当您的应用程序处理树中的大量数据但需要比其他人更频繁地访问数据子集时，展开树总是比二叉搜索树更好。在这种情况下，由于展开，您经常访问的数据将靠近根目录。此外，任何节点都可以在比以前更短的时间内被访问。

作为选择这些树的一般规则，如果您需要在一段时间的树操作中“平均”log(n) 时间，则使用展开树。二叉树不能保证这一点。

  1. 这些树的正面和负面是什么？

两者的积极因素是理论上你可以在这两种数据结构中绕过 log(n)。

如前所述，展开树在许多操作中具有平均 log(n)。这意味着，也许您在该集合中至少有一次操作的时间复杂度为 n。但这将在访问频繁项时得到补偿。

二叉搜索树的不利之处在于，您需要幸运地始终拥有 log(n)。如果键不是随机的，则树将简化为只有一侧的列表形式。

  1. 这些树在大 O 符号方面的表现如何？

仅当您的键是随机的时，才可在一组树操作中平均展开树 Log(n) 二进制树 Log(n)。

运行时的结果在这里很明显。您可以看到有和没有张开搜索的运行时差异。

于 2012-01-18T03:40:56.683 回答