使用给定信息在 o(log(n)) 时间内找到 AVL 树的中值？

Question

假设您知道 AVL 树的最小值和最大值，并且该树仅包含不同的整数，请找到树的中位数？

Answer 1

k,tree,direction,currentPosition 递归函数的参数（先行框架将 f(k,tree,null,null) 作为解决问题的参数。实现框架最初将收到此作为 null，方向和位置为 null，如果它是实现框架，则当前位置会相应调整，如果不是实现框架，那么我们通过某种方式来到这里，我们当前的位置和方向就会发生变化，所以现在我们在这个框架的当前位置将根据另一段逻辑进行调整也提供了。

//implementation by Anthony Toorie
f(k,tree,direction,currentPosition){ 
//   let currentPosition = currentPosition
   if(!direction && !currentPosition){
      currentPosition = tree.left
   }

   if(direction === "left"){
      currentPosition = currentPosition - |tree.right|
   }

   if(direction === "right"){
      currentPosition = currentPosition - |tree.left|
   }

   if(currentPosition === k){
      return tree.value
   }

   if(currentPosition < k){
      return f(k,tree.left,"left",currentPosition)
   }

   if(currentPosition > k){
      return f(k,tree.right,"right",currentPosition)
   }
}

来源：

https://en.wikipedia.org/wiki/Order_statistic_tree

|X|表示该树 X 或子树 X 的节点数。

主要基于快速选择算法。

如果树是高度保守的或平衡的，那么在给定一些输入 N 的最坏情况下，这只能给你 O(logN)。在最坏的情况下，对于常规的非平衡 BST，运行时间为 O(N)。此外，在常规树上，最坏情况下 O(N) 最好情况下 O(1) 和平均情况下 O(N) 也是如此。一棵树应该只包含不同的数字，树中的元素应该是可排序的。

使用给定信息在 o(log(n)) 时间内找到 AVL 树的中值？

Find the median of an AVL tree in o(log(n)) time using the given information?

sorting

tree

median