Возможно ли построить двоичное дерево и отслеживать медиану, все еще с установкой 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 (высота дерева), поэтому o (log (n)), если дерево сбалансировано.

Чтобы отслеживать медиану, вы можете просто выполнить поиск медианы всякий раз, когда вы изменяете дерево.

Чтобы превратить дерево в дерево статистики заказа, вам необходимо сохранить и обновить нумер потомков для каждого узла внутри узла вместе со своим значением.

Кто-то отправил C# -Implementation такого дерева в this related answer.