Алгоритм. Сумма расстояний между каждыми двумя узлами двоичного дерева поиска в 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.....
Решения, с которыми я столкнулся:
Теперь возникает вопрос: существует ли какое-либо решение порядка 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, полному расстоянию от его родителя.
1
/ \
2 3
/ \
4 5
Например, для 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).
