我被要求创建一个数据结构，其中插入节点和查找具有特定键值的节点等函数需要 O(logn)。 我被要求在 O(1) 时间内找到中位数。
我一直在考虑使用顺序统计树，选择排名为 N/2 的节点会找到中位数吗？
我在这里看到了类似的问题，但我想要更好的解释:(在二叉树中查找 O(1) 中的中位数)
有什么想法吗？
谢谢。
我相信 Enzo Nakamura 所说的找到第 k 个位置是 O(log n) 时指的是使用带有 某种扭曲 的 红黑二叉搜索树 。在每个节点上，您还存储该节点子树的大小。这样您就可以利用二叉搜索树的属性来查找哪个值是 O(log n) 中的第 k 个值。然而，只有当二叉搜索树的根节点是 a) 奇数个节点和 b) perfectly 平衡树时，才保证它是中位数，而红黑二叉搜索树不一定是完全平衡的，所以即使上面的方法也不能保证这一点。
有一种著名的问题叫做“运行中位数”，你从中位数开始，然后每次给你一个新元素时都必须计算新的中位数。您可以通过创建一个堆来解决这个问题，该堆的根是中位数，其左子树是最小堆，右子树是最大堆。插入到这个堆的时间是 O(log n) 时间，但是一旦树建立，中值检索总是 O(1)，因为该结构保证根节点在所有情况下都是中值。
我认为只要 k 不改变，应该可以将这个问题推广到在常数时间内找到第 k 个值。在运行中值问题中，每当左右子树比另一个大 2 个节点时，我们就需要重新平衡左右子树。我们可以概括这个问题，说每次左子树的大小超过 k 时，我们都会重新平衡左子树（如果它是第 k 个最小的）或右子树（如果它是第 k 个最大的），插入时间和重新平衡时间仍然都是 O(log n ）。现在我们不能像使用 RB 树那样使用这种方法来查找任何第 k 个值，但对于一个特定的 k 值，您将在恒定时间内检索其值。这篇paper中也引用了这个过程，其中特别指出了在恒定时间内检索第k个值的能力。
是的，ceil(n/2)位置上的元素（从1开始）确实是中位数（假设序列的大小是奇数）。然而，使用顺序统计树查找第 k 个位置上的元素是 O(lg n)，而不是 O(1)。
你应该知道的是：给定一个完美的二叉搜索树（一棵二叉搜索树，其中所有内部节点都有两个子节点，并且所有叶子都具有相同的深度或相同的级别），中位数就是根。更一般地，如果您有一个二叉搜索树结构，其中每个节点还存储其子树中的节点数，并且根的左子节点和右子节点恰好具有相同的数字，那么根就是中位数。这种情况非常有限，因此一个想法是平衡二叉搜索树以增加根成为中位数的概率。
另一个想法是：保留一个二叉搜索树和一个额外的变量（指针）来指示中位数现在在哪里。然后，对于每个插入/删除操作，更新此指针。
希望有帮助！
如果有人有资源可以清楚地解释如何解决这个特定问题，请分享。