每周学点大数据 | 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. 王:非常好,你的解释很到位。

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

内容来源:灯塔大数据

原文发布于微信公众号 - 灯塔大数据(DTbigdata)

原文发表时间:2017-03-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏落影的专栏

程序员进阶之算法练习(二)

前言 看完题目大意,先思考,再看解析;觉得题目大意不清晰,点击题目链接看原文。 A 题目链接 题目大意:n个点,坐标x[i]从小到大,每个点可以选择Le...

3056
来自专栏小红豆的数据分析

小蛇学python(18)pandas的数据聚合与分组计算

对数据集进行分组并对各组应用一个函数,这是数据分析工作的重要环节。在将数据集准备好之后,通常的任务就是计算分组统计或生成透视表。pandas提供了一个高效的gr...

2752
来自专栏数据结构与算法

P1789 【Mc生存】插火把

题目背景 初一党应该都知道...... 题目描述 话说有一天linyorson在Mc开了一个超平坦世界,他把这个世界看成一个n*n的方阵,现在他有m个火把和k个...

3665
来自专栏用户2442861的专栏

MATLAB 中有哪些命令,让人相见恨晚?

提问都说了是命令,大家回答那么多函数干什么... 我来给一个超级大杀器 在命令行敲入 dbstop if error

4401
来自专栏云霄雨霁

字符串查找----查找算法的选择

2880
来自专栏C语言及其他语言

【每日一题】1426: [蓝桥杯][历届试题]九宫重排

如下面第一个图的九宫格中,放着 1~8 的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面...

1113
来自专栏数据结构与算法

7828:最大公约数与最小公倍数

7828:最大公约数与最小公倍数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 两个正整数的最大公约数是G,最小公倍数是...

4638
来自专栏章鱼的慢慢技术路

2013年第四届蓝桥杯C/C++B组省赛题目解析

2373
来自专栏数据结构与算法

1893. [国家集训队2011]等差子序列(bitset)

★★   输入文件:nt2011_sequence.in   输出文件:nt2011_sequence.out 简单对比 时间限制:0.3 s   内存限制:5...

35410
来自专栏数据结构与算法

洛谷P1730 最小密度路径(floyd)

很显然的一个dp方程\(f[i][j][k][l]\)表示从\(i\)到\(j\)经过了\(k\)条边的最小权值

973

扫码关注云+社区

领取腾讯云代金券