关于平衡树分析

我正在读一本关于树的书。这里是文本片段。关于平衡树分析

有很多通用算法来实现平衡树。大部分比标准二分查找树更复杂一些，平均需要更长的时间。然而，他们确实提供了针对令人尴尬的简单情况的保护。

一种较新的方法是放弃平衡条件并允许树任意深，但是在每次操作之后，应用重构规则，其趋于使未来的操作有效。这些类型的数据结构通常被归类为自我调整。在二叉搜索树的情况下，我们不能保证在任何单个操作上绑定O（log n），但可以显示m个操作的任何序列在最差情况下需要总时间O（m log n）案件。

上面的文字片段问题

如何笔者来到在第一段的结论是什么意思笔者尴尬简单的情况下如何平衡树的一般算法提供防范呢？
是什么作者的意思是“在最后一段米操作的任何顺序采取我们如何得出这一结论的总时间O（mlogn），请求与例子来解释。

谢谢！

来源

2011-08-31 venkysmarty

对于一个典型的，简单的实现二叉搜索树的，仅仅将序列1, 2, 3, ..., n会产生有n个级别的树。（插入每个元素都会沿着树的右边遍历树，然后在这边添加一个新元素，导致最大程度的不平衡树。）我相信这就是他们所说的“令人尴尬的简单”。
他们在谈论splay trees（与AVL或红/黑树相对）。 AVL和红/黑树保证O（log n）每个插入/删除/查找操作的最坏情况，但代价是复杂的代码和较大的常数因子。对于任何长操作顺序，Splay树不保证每个操作都可以保证O（log n），但它们确保每个操作的O（log n）平均为。所以从长远来看，它们的表现与更复杂的树木一样好，但具有更简单的实现和更小的常数因子。

来源

2011-08-31 05:55:32 Nemo

我认为在第二段中，它是O（mlogn）而不是O（logn） – venkysmarty

我更新它以读取“O（log n）每个操作”。 – Nemo

1）我相信作者意味着像一串节点基本上看起来像一个悬挂列表的情况下，树自动调整和旋转（看着AVL Trees），你可以打击“找到”或“删除”像这样的高度为O（n）的树。

2.）如果树是自我调整的，它的高度将是O（logn）。由于我们在树上执行了m个操作，因此我们可以假设，由于big-O是最差情况下的运行时间，因此操作的对象可能位于底部，因此在高度为O（logn）的树上进行m次操作（摊销运行因为再次旋转可能会发生）将是O（mlogn）。

来源

2011-08-31 05:40:52 Vinay

什么样的操作，可以用elobarate，为什么我们用log n来多重m？ – venkysmarty

操作意义标准的东西，如“查找”，“删除”和“插入”（所有在词典ADT中概述）。 m简单地表示我们执行了m个操作，每个操作都花费O（logn）时间。因此，这些m个操作序列将共同花费O（mlogn）时间。这就像做了三次需要12秒钟的事情。然后整个过程需要36秒。 – Vinay

您的“编辑”不正确。红色/黑色树中的旋转（例如）都经过精心设计，每一次操作都是O（log n），无论您按照什么顺序执行哪些操作。 – Nemo

简单二叉搜索树的最坏情况是当它变得如此不平衡以致每个节点只有一个孩子时。在这种情况下，具有N节点的树将具有高度N，并且树上的操作可能具有O(N)复杂性。平衡二叉搜索树通过在树操作之后以某种方式重新平衡树来防止发生这种情况。由于这些重新平衡操作，我认为可以说所有平衡树算法比简单的不平衡树更复杂。
他们正在谈论分期偿还的复杂性。实质上他们说，虽然单个操作的复杂性并不总是如此，但是如果我们执行一系列操作，每个操作将平均达到O（log（N））复杂度，因此M操作的总数是O(Mlog(N)).

希望这会有所帮助。

来源

2011-08-31 05:43:32

如果你从一个排序列表开始，并且你没有做任何重新平衡，你会得到一个完全不平衡的n级深度树的最坏情况。但是输入已经排序了，你应该能够在O（n）时间内把它放在一个合理的顺序中（选择中间的元素作为根，递归到根的孩子的左半部分和右半部分）。

来源

2011-08-31 05:53:37

关于平衡树分析

回答

相关问题