每周学点大数据 | No.30前序计数

No.30期

前序计数

Mr. 王：我们再来说说父子关系判定的应用。前序计数是一种非常常用的对树进行处理的方法。前序计数实现的就是对各个节点按照其前序遍历的序列进行标号，第一个访问的记为1，第二个访问的记为2，依此类推。

小可：嗯，这个操作在内存中同样也是非常容易实现的，只要前序遍历一次树就可以了。

Mr. 王：在磁盘中，我们依然可以借助欧拉回路技术和将树存储为链表这种策略。

比如对于这样一棵树：

图中的数字就是其前序遍历的顺序。现在我们要对存在磁盘中的这样一棵树的节点求解出它的前序计数。想一想，如果不采用任何面向磁盘的特殊设计，而是采用朴素的搜索算法的话，复杂度会怎么样？

小可：我认为和前面的磁盘中的链表相类似。这些节点放置于随机的磁盘块中，当内存满了以后，在最坏情况下每次访问一个节点都要换入一个新的磁盘块，这样就造成了W(N) 的复杂度。这样的复杂度是不能接受的。

Mr. 王：那我们就来设计一种比较好的方法。我们完全可以利用前面的欧拉回路技术，但是在求解这个问题时，要做一个特殊的处理。

在每一条边上，我们将从父节点指向子节点的有向边的权值设为1 ；反之，将从子节点指向父节点的有向边的权值设为0。

小可：父节点和子节点的判定刚好可以利用前面的父子关系判定！

Mr. 王：没错，这样欧拉回路构成的链表在顺序访问时，就会在从父节点向子节点遍历时增加1，这是在前序计数时我们所需要的；而在从子节点返回向父节点移动时，不增加值。在这个实例中，我们可以非常容易地得出结果，每一个节点的前序计数结果都是(parent(v),v) 这条边的rank，也就是：

小可拿出纸笔，在纸上写画出了这个过程，说：结果就是这样：

Mr. 王：这个过程的时间复杂度就是O(Scan(N))+O(Sort(N))=O(Sort(N))。和进行表ranking的复杂度一致，相比W(N) 而言，真是快得太多了。

Mr. 王：还有一类问题叫作求子树大小。求子树大小就是在树的每一个节点上标出其子树上节点的个数。这一次，我们依然采用欧拉回路技术。在从父节点去子节点的路上，我们依然在边上标注1 ；不同的是，在回来的路上，我们同样将权值设为1。这样，经过任何一条有向边，都会让ranking 的计数加1。

就像这样：

那么每一个节点的子树大小为：

你来思考一下，为什么是这个数？

小可想了想，说 ：rank((v, p(v)))这个数描述了当遍历到达它时，已经经历过的边数，rank(( p(v),v))描述了当遍历从 v 的子树结束返回 v 时 ranking 的累积，两个 rank 作差，可以求出在这个子树中，究竟走了多少条边。

加上1 是为了调和v 自己本身；而除以2，是因为每一个节点的存在，都有一去一回两次。也就是说，rank 这个值会因为一个节点的存在而增加2。所以只要除以2，就可以让每个权值对应衡量一个节点的存在。

Mr. 王：非常好，你的解释很到位。

小可：对了，我想起来一个问题。我们前面提到了使用最大独立集，但还没有说怎么求最大独立集呢！

内容来源：灯塔大数据