算法 - O(n)中二进制搜索树的每两个节点之间的距离之和？

Question

问题是找出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.....

我提出的解决方案:

1. 蛮力.脚步:

   1. 执行DFS并跟踪所有节点:O(n).
   2. 选择每两个节点并O(nC2)_times_O(log(n))=O(n2log(n))使用最低公共祖先方法计算它们之间的距离并将它们相加.

   整体复杂性:-O(n2log(n)).

2. O(nlog(n)).脚步:-

   1. 在插入之前执行DFS并跟踪所有节点:O(n).
   2. 计算插入节点与之间的距离:O(nlog(n)).剩下的节点.
   3. 使用步骤2中计算的总和添加现有总和

   整体复杂性:-O(nlog(n)).

现在的问题是"是否存在任何解决方案O(n)？

Answer 1

我们可以通过两次遍历树来完成此操作.

首先,我们需要三个数组

int []left 它存储了左子树的距离之和.

int []right 它存储了右子树的距离之和.

int []up 它存储了父树的距离之和(没有当前的子树).

因此,首先遍历,对于每个节点,我们计算左右距离.如果节点是叶子,只需返回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;
}

然后对于第二次遍历,我们需要向每个节点添加与其父节点的总距离.

             1
            / \
           2   3
          / \
         4   5

例如,对于节点1(根),总距离left[1] + right[1] + 2,up[1] = 0; (我们添加2,因为根有左右子树,它的确切公式是:

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

对于节点2,总距离为left[2] + right[2] + add + up[1] + right[1] + 1 + addRight,up[2] = up[1] + right[1] + addRight.1公式末尾有一个原因是因为当前节点到其父节点有一条边,所以我们需要添加1.现在,我代表当前节点的额外距离add,附加的距离如果在父节点的左子树是addLeft和同样addRight的右子树.

对于节点3,总距离up[1] + left[1] + 1 + addLeft,up[3] = up[1] + left[1] + addLeft;

对于节点4,总距离up[2] + right[2] + 1 + addRight,up[4] = up[2] + right[2] + addRight;

所以依赖于当前节点是左或右节点,我们相应地更新up.

时间复杂度为O(n)

Answer 2

是的,您可以通过DP在O(n)中找到每两个节点之间的整个树的总距离.简而言之,你应该知道3件事:

cnt[i] is the node count of the ith-node's sub-tree
dis[i] is the sum distance of every ith-node subtree's 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] 等于三部分:

1. x _i - > x _j和y _i - > y _j,等于ret[left] + ret[right].
2. x _i - > node和y _i - > node,equals dis[node].
3. x _i - > y _j:

等于sigma(x _i - > node - > y _j),固定x _i,然后我们得到cnt [left]*distance(x _i,node)+ sigma(node-> y _j),然后cnt [left]*distance (x _i,node)+ sigma(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's 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,问题对我来说并不那么难......

所以你可以相信我们......