c# - 是否可以构建一个二叉树并跟踪中位数，仍然使用 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

如果你把你的树变成一棵 order statistics tree ( see also )，您可以在 O(tree-height) 中查找中位数，因此如果树是平衡的，则为 o(log(n))。

要跟踪中位数，您可以在修改树时简单地执行中位数查找。

要将您的树变成订单统计树，您需要存储和更新节点内每个节点的后代数量及其值。

有人在 this related answer 中发布了这样一棵树的 c# 实现.