运行时使用 AVL 树查找中间元素
runtime to find middle element using AVL tree
我有一个演讲幻灯片如下：
为了找到 AVL 树中的中间元素，我按顺序遍历元素，直到它到达 moddile 元素。需要 O(N).
如果我没记错的话，在树结构中，查找元素以 2 O(logn) 为底，因为 AVL 是二叉树，总是分为 2 个孩子。
但为什么说 O(N)？
分成2children并不能保证完全对称。例如，考虑所有平衡二叉树中最不平衡的：每个右 child 的深度比其对应的左 child 多一个。
在这样一棵树中，中间元素将位于右分支的左分支的下方某处 ...
您需要确定您有多少个节点N，然后找到第N/2个最大的节点。这不是 O(log N) 过程。
我只是想详细说明 'A. Mashreghi' 评论。
因为，正在考虑的树是 AVL 树 - 保证在 O(log n) 中找到元素与要查找的元素（键）保持一致。
问题是 - 您正在尝试识别给定数据结构中的中间元素。由于它是 AVL 树（自平衡 BST），按顺序旅行为您提供升序排列的元素。您想使用此 属性 来查找中间元素。
算法是这样的——对每个按顺序遍历的节点和 return @ n/2th 位置都有一个计数器增量。这总和为 O(n/2)，因此总体复杂度为 O(n)。
我有一个演讲幻灯片如下： 为了找到 AVL 树中的中间元素，我按顺序遍历元素，直到它到达 moddile 元素。需要 O(N).
如果我没记错的话，在树结构中，查找元素以 2 O(logn) 为底，因为 AVL 是二叉树，总是分为 2 个孩子。
但为什么说 O(N)？
分成2children并不能保证完全对称。例如，考虑所有平衡二叉树中最不平衡的：每个右 child 的深度比其对应的左 child 多一个。 在这样一棵树中，中间元素将位于右分支的左分支的下方某处 ...
您需要确定您有多少个节点N，然后找到第N/2个最大的节点。这不是 O(log N) 过程。
我只是想详细说明 'A. Mashreghi' 评论。
因为，正在考虑的树是 AVL 树 - 保证在 O(log n) 中找到元素与要查找的元素（键）保持一致。
问题是 - 您正在尝试识别给定数据结构中的中间元素。由于它是 AVL 树（自平衡 BST），按顺序旅行为您提供升序排列的元素。您想使用此 属性 来查找中间元素。
算法是这样的——对每个按顺序遍历的节点和 return @ n/2th 位置都有一个计数器增量。这总和为 O(n/2)，因此总体复杂度为 O(n)。