是否可以建立一个二叉树并跟踪中值，仍然使用O(log(n))插入

Question

我正试图弄清楚这是否可能。

我尝试了一种算法：

m1,m2是中间的2个元素(如果树的大小是奇数，则m1=m2)。

以下是建造树的样子

----------------------------------
5 = m1,m2
----------------------------------
5 = m2
/
2 = m1
-----------------------------------
5 
/
2 = m1,m2
/
1
-----------------------------------  
5 
/
2 = m1
/  
1   3 = m2
-----------------------------------
5
/ 
2   9 
/  
1   3 = m1,m2
-----------------------------------
5 = m2
/  
2    9 
/    /
1    6   

3 = m1   

我开始尝试并实现方法

/// <summary>
/// Insert an element
/// </summary>
public void Insert(int val)
{
// If inserting first element, set _m1 and _m2.
if(_root == null)
{
_m1 = _m2 = val;
}
// Insert new node in proper spot in tree.
Node cur = _root;           
while(cur != null)
{
if(cur.Val > val)
cur = cur.Left;
else if(cur.Val < val)
cur = cur.Right;
else // found value on an existing node
return;
}
cur = new Node() { Val = val };
// Update median elements
if(val < _m1.Val)
{
// ???
}
else if(val > _m2.Val)
{
// ???
}
}       
}

但我不知道如何更新中位数。有可能做O(1)时间吗？

Answer 1

如果将树转换为订单统计树(另请参阅)，则可以在O(树高)中查找中值，如果树是平衡的，则可以查找O(log(n))中的中值。

为了跟踪中位数，只要修改树，就可以简单地执行中位数的查找。

要将树转换为订单统计树，您需要存储并更新节点内每个节点的子节点及其值。

有人在这个相关的答案中发布了这样一个树的c#-实现。