c# - 是否仍然可以使用O(log(n))插入来构建二叉树并跟踪中位数？

我在想这是否可能。
我对算法的尝试：
m1,m2是中间的两个元素（如果树的大小是奇数，则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）次吗？

最佳答案

如果你把你的树变成order statistics tree（see also），你可以在o（树高）中查找中值，如果树是平衡的，则在o（对数（n））中查找中值。
为了跟踪中值，只要在修改树时执行中值查找即可。
要将树转换为顺序统计树，需要存储和更新节点内每个节点的子节点数及其值。
有人在this related answer中发布了这种树的c-实现。

关于c# - 是否仍然可以使用O(log(n))插入来构建二叉树并跟踪中位数？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41918474/