Алгоритм. Сумма расстояний между каждыми двумя узлами двоичного дерева поиска в O (n)?

Вопрос заключается в том, чтобы узнать сумму расстояний между каждыми двумя узлами BinarySearchTree, учитывая, что каждая пара родитель-ребенок разделяется единичным расстоянием. Он должен быть рассчитан после каждой вставки.

Пример:

 ->first node is inserted..

      (root)

   total sum=0;

->left and right node are inserted

      (root)
      /    \
  (left)   (right)

   total sum = distance(root,left)+distance(root,right)+distance(left,right);
             =        1           +         1          +         2
             =     4

and so on.....

Решения, с которыми я столкнулся:

перебор. Шаги:
- выполнить DFS и отслеживать все узлы: O(n).
- Выберите каждый из двух узлов и вычислите: O(nC2)_times_O(log(n))=O(n2log(n)) расстояние между ними, используя Самый низкий общий предок и добавьте их.
Общая сложность: -O(n2log(n)).
O(nlog(n)). Шаги: -
- Перед вставкой выполните DFS и отслеживайте все узлы: O(n).
- Рассчитайте расстояние между вставленными node и: O(nlog(n)). остальные узлы.
- Добавьте существующую сумму с суммой, вычисленной на шаге 2
Общая сложность: -O(nlog(n)).

Теперь возникает вопрос: существует ли какое-либо решение порядка O(n)??

Ответ 1

Мы можем сделать это, дважды пройдя дерево.

Сначала нам понадобится три массива

int []left, который сохранил сумму расстояния левого под дерева.

int []right, который сохранил сумму расстояния от правого под дерева.

int []up, который сохранил сумму расстояния родительского дерева (без текущего поддерева).

Итак, первый обход, для каждого node, мы вычисляем левое и правое расстояние. Если node является листом, просто возвращаем 0, если нет, мы можем иметь следующую формулу:

int cal(Node node){
    int left = cal(node.left);
    int right = cal(node.right);
    left[node.index] = left;
    right[node.index] = right;
    //Depend on the current node have left or right node, we add 0,1 or 2 to the final result
    int add = (node.left != null && node.right != null)? 2 : node.left != null ? 1 : node.right != null ? 1 : 0;
    return left + right + add;
}

Затем для второго обхода нам нужно добавить к каждому node, полному расстоянию от его родителя.

Например, для node 1 (корень) общее расстояние left[1] + right[1] + 2, up[1] = 0; (мы добавляем 2, поскольку корень имеет как левое, так и правое поддерево, точная формула для него:

int add = 0; 
if (node.left != null) 
    add++;
if(node.right != null)
    add++;

Для node 2 общее расстояние left[2] + right[2] + add + up[1] + right[1] + 1 + addRight, up[2] = up[1] + right[1] + addRight. Причина, по которой существует 1 в конце формулы, состоит в том, что к ее родительскому ребру есть край от текущего node, поэтому нам нужно добавить 1. Теперь обозначим дополнительное расстояние для текущего node is add, дополнительное расстояние, если есть левое поддерево в родительском node, равно addLeft и аналогично addRight для правого поддерева.

Для node 3 общее расстояние up[1] + left[1] + 1 + addLeft, up[3] = up[1] + left[1] + addLeft;

Для node 4 общее расстояние up[2] + right[2] + 1 + addRight, up[4] = up[2] + right[2] + addRight;

Так что в зависимости от текущего node находится слева или справа node, мы обновляем up соответственно.

Сложность времени O (n)

Ответ 2

Да, вы можете найти суммарное расстояние всего дерева между каждыми двумя node на DP в O (n). Вкратце, вы должны знать 3 вещи:

cnt[i] is the node count of the ith-node sub-tree
dis[i] is the sum distance of every ith-node subtree node to i-th node
ret[i] is the sum distance of the ith-node subtree between every two node

обратите внимание, что ret[root] является ответом на проблему, поэтому просто вычислите ret[i] вправо, и проблема будет выполнена... Как рассчитать ret[i]? Нужна помощь cnt[i] и dis[i] и рекурсивно решает ее. Основная проблема:

Указано ret [left] ret [right] dis [left] dis [right] cnt [left] cnt [right] to cal ret [ node] dis [node] cnt [node ].

              (node)
          /             \
    (left-subtree) (right subtree)
      /                   \
...(node x_i) ...   ...(node y_i)...
important:x_i is the any node in left-subtree(not leaf!) 
and y_i is the any node in right-subtree(not leaf either!).

cnt[node] легко, просто равен cnt[left] + cnt[right] + 1

dis[node] не так сложно, равно dis[left] + dis[right] + cnt[left] + cnt[right]. Причина: sigma (x _i → left) dis[left], поэтому sigma (x _i → node) является dis[left] + cnt[left].

ret[node] равна трем частям:

x _i → x _j и y _i → y _j, равно ret[left] + ret[right].
x _i → node и y _i → node, равно dis[node].
x _i → y _j:

equals sigma (x _i → node → y _j), фиксированный x _i, тогда мы получаем cnt [left ] * distance (x _i, node) + sigma (node → y _j), затем cnt [left] * distance (x _i, node) + сигма (node → left- > y _j),

и cnt[left]*distance(x_i,node) + cnt[left] + dis[left].

Сумма x _i: cnt[left]*(cnt[right]+dis[right]) + cnt[right]*(cnt[left] + dis[left]), тогда это 2*cnt[left]*cnt[right] + dis[left]*cnt[right] + dis[right]*cnt[left].

Суммируйте эти три части и получим ret[i]. Сделайте это рекурсивно, мы получим ret[root].

Мой код:

import java.util.Arrays;

public class BSTDistance {
    int[] left;
    int[] right;
    int[] cnt;
    int[] ret;
    int[] dis;
    int nNode;
    public BSTDistance(int n) {// n is the number of node
        left = new int[n];
        right = new int[n];
        cnt = new int[n];
        ret = new int[n];
        dis = new int[n];
        Arrays.fill(left,-1);
        Arrays.fill(right,-1);
        nNode = n;
    }
    void add(int a, int b)
    {
        if (left[b] == -1)
        {
            left[b] = a;
        }
        else
        {
            right[b] = a;
        }
    }
    int cal()
    {
        _cal(0);//assume root idx is 0
        return ret[0];
    }
    void _cal(int idx)
    {
        if (left[idx] == -1 && right[idx] == -1)
        {
            cnt[idx] = 1;
            dis[idx] = 0;
            ret[idx] = 0;
        }
        else if (left[idx] != -1  && right[idx] == -1)
        {
            _cal(left[idx]);
            cnt[idx] = cnt[left[idx]] + 1;
            dis[idx] = dis[left[idx]] + cnt[left[idx]];
            ret[idx] = ret[left[idx]] + dis[idx];
        }//left[idx] == -1 and right[idx] != -1 is impossible, guarranted by add(int,int)  
        else 
        {
            _cal(left[idx]);
            _cal(right[idx]);
            cnt[idx] = cnt[left[idx]] + 1 + cnt[right[idx]];
            dis[idx] = dis[left[idx]] + dis[right[idx]] + cnt[left[idx]] + cnt[right[idx]];
            ret[idx] = dis[idx] + ret[left[idx]] + ret[right[idx]] + 2*cnt[left[idx]]*cnt[right[idx]] + dis[left[idx]]*cnt[right[idx]] + dis[right[idx]]*cnt[left[idx]];
        }
    }
    public static void main(String[] args)
    {
        BSTDistance bst1 = new BSTDistance(3);
        bst1.add(1, 0);
        bst1.add(2, 0);
        //   (0)
        //  /   \
        //(1)   (2)
        System.out.println(bst1.cal());
        BSTDistance bst2 = new BSTDistance(5);
        bst2.add(1, 0);
        bst2.add(2, 0);
        bst2.add(3, 1);
        bst2.add(4, 1);
        //       (0)
        //      /   \
        //    (1)   (2)
        //   /   \
        // (3)   (4)
        //0 -> 1:1
        //0 -> 2:1
        //0 -> 3:2
        //0 -> 4:2
        //1 -> 2:2
        //1 -> 3:1
        //1 -> 4:1
        //2 -> 3:3
        //2 -> 4:3
        //3 -> 4:2
        //2*4+3*2+1*4=18
        System.out.println(bst2.cal());
    }
}

выход:

4
18

Для удобства (читателей, чтобы понять мое решение), я вставляю значение cnt[],dis[] and ret[] после вызова bst2.cal():

cnt[] 5 3 1 1 1 
dis[] 6 2 0 0 0
ret[] 18 4 0 0 0

PS: Это решение от UESTC_elfness, это простая проблема для него, и я sayakiss, проблема не такая уж сложная для меня.

Итак, вы можете доверять нам...

Ответ 3

Сначала добавьте четыре переменные к каждому node. Четыре переменные представляют собой сумму расстояния до левого отпрыска, сумму расстояния до правого потомства, число node в левом потомстве и число node в правом потомстве. Обозначим их как l, r, nl и nr.

Во-вторых, добавьте полную переменную в root node, чтобы записать сумму после каждой вставки.

Идея состоит в том, что если у вас есть общее количество текущего дерева, то новая сумма после вставки нового node (старая сумма + сумма расстояния нового node ко всем остальным узлам). То, что вам нужно вычислить при каждой вставке, - это сумма расстояния нового node ко всем другим узлам.

1- Insert the new node with four variable set to zero.
2- Create two temp counter "node travel" and "subtotal" with value zero.
3- Back trace the route from new node to root. 
   a- go up to parent node
   b- add one to node travel 
   c- add node travel to subtotal
   d- add (nr * node travel) + r to subtotal if the new node is on left offspring
   e- add node travel to l
   f- add one to nl
4- Add subtotal to total

1 - O (n)

2 - O (1)

3 - O (log n), a to f принимает O (1)

4 - O (1)

Ответ 4

Если вы имеете в виду O (n) для каждой вставки, то это можно сделать, если вы сделаете это после каждой вставки, начиная с корня.

0- Record the current sum of the distances. Call it s1: O(1).
1- Insert the new node: O(n).
2- Perform a BFS, starting at this new node.
   For each new node you discover, record its distance to the start (new) node, as BFS always does: O(n).
   This gives you an array of the distances from the start node to all other nodes.
3- Sum these distances up. Call this s2: O(n).
4- New_sum = s1 + s2: O(1).

Таким образом, этот алгоритм O (n).