我有一个演讲幻灯片说如下: 为了找到 AVL 树中的中间元素，我按顺序遍历元素，直到它到达 moddile 元素。它需要 O(N)。
如果我没记错的话，在树结构中，查找元素以 2 O(logn) 为底，因为 AVL 是二叉树，总是分为 2 个 child 。
但为什么说 O(N)？
最佳答案
我只是想详细说明“A. Mashreghi 的评论。
因为，正在考虑的树是 AVL 树 - 保证在 O(log n) 中找到的元素与要查找的元素(键)一样保持为 log。
问题是 - 您正在尝试识别给定数据结构中的中间元素。由于它是 AVL 树(自平衡 BST)，按顺序旅行为您提供升序排列的元素。您想使用此属性来查找中间元素。
算法是这样的——对每个按顺序遍历的节点都有一个计数器增量，并返回第 n/2 个位置。这总和为 O(n/2)，因此总体复杂度为 O(n)。
关于algorithm - 运行时使用 AVL 树查找中间元素，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45471248/