运行时使用AVL树查找中间元素

我有一个演讲幻灯片说如下：要查找AVL树中的中间元素，我按顺序遍历元素，直到它到达moddile元素。它需要O（N）。运行时使用AVL树查找中间元素

如果我正确地知道，在树结构中，查找元素需要基2 O（logn），因为AVL是始终分为2个子元素的二叉树。

但为什么说O（N）？

2017-08-02 Kam

是的，如果你知道中间元素的值需要O（log n），但由于中间元素在手之前是未知的，所以必须计算树中最小的元素（n/2 - 1）下一个元素将是中间元素。 –

被分成2个孩子并不能保证完美的对称性。例如，考虑所有平衡二叉树中最不平衡的情况：每个正确的孩子的深度比相应的左孩子多一个。在这样的树，中间元素会在右支的左前分支的某处......

您需要确定N你有多少个节点，然后找到N/2个最大的节点。这不是O（log N）过程。

2017-08-02 21:39:25 Prune

由于所考虑的树是AVL树，因此我们不能假设O（n）的情况不是这种情况。关于数字（关键）值不详的解释 - 是因素。你有n/2个数字（为了遍历）确定中间元素。 – arunk2

我只是想详细说明'A. Mashreghi'的评论。

因为，所考虑的树是AVL树 - O（log n）中元素的保证查找结果保存为日志，因为您有要查找的元素（键）。

问题是 - 您试图在给定的数据结构中识别中间元素。因为它是AVL树（自平衡BST）按顺序旅行为您提供元素按升序排列。你想使用这个属性来找到中间元素。

算法是这样的 - 对于遍历的每个节点都有一个递增计数，并返回第n/2个位置。这总和为O（n/2），因此总体复杂度为O（n）。

2017-08-03 06:57:46 arunk2

回答