每周学点大数据 No.30前序计数
介绍父子判定的应用——前序计数，运用欧拉回路技术方法，及将树存储为链表的策略来详细讲解。...
点击上方“灯塔大数据”可以订阅哦
本文为灯塔大数据原创内容，欢迎个人转载至朋友圈，其他机构转载请在文章开头标注：
“转自：灯塔大数据；微信：DTbigdata”
编者按：灯塔大数据将每周持续推出《从零开始学大数据算法》的连载，本书为哈尔滨工业大学著名教授王宏志老师的扛鼎力作，以对话的形式深入浅出的从何为大数据说到大数据算法再到大数据技术的应用，带我们在大数据技术的海洋里徜徉~每周五定期更新，欢迎来做客呦！
上期回顾&查看方式：
在上一期中，我们学习了表排序的一种应用——欧拉回路技术，并详细讲解如何在内存中，实现树的欧拉回路。在本期，我们将介绍父子判定的应用——前序计数，运用欧拉回路技术的方法，及将树存储为链表的策略来详细讲解。
PS：了解上期详细内容，请在自定义菜单栏中点击“文章精选”—“技术连载”，进行查看。
在上一期中，我们学习了表排序的一种应用——欧拉回路技术，并详细讲解如何在内存中，实现树的欧拉回路。在本期，我们将介绍父子判定的应用——前序计数，运用欧拉回路技术的方法，及将树存储为链表的策略来详细讲解。
PS：了解上期详细内容，请在自定义菜单栏中点击“文章精选”—“技术连载”，进行查看。
No.30期
前序计数
前序计数
Mr. 王：我们再来说说父子关系判定的应用。前序计数是一种非常常用的对树进行处理的方法。前序计数实现的就是对各个节点按照其前序遍历的序列进行标号，第一个访问的记为1，第二个访问的记为2，依此类推。
小可：嗯，这个操作在内存中同样也是非常容易实现的，只要前序遍历一次树就可以了。
Mr. 王：在磁盘中，我们依然可以借助欧拉回路技术和将树存储为链表这种策略。
比如对于这样一棵树：
小可：我认为和前面的磁盘中的链表相类似。这些节点放置于随机的磁盘块中，当内存满了以后，在最坏情况下每次访问一个节点都要换入一个新的磁盘块，这样就造成了W(N) 的复杂度。这样的复杂度是不能接受的。
Mr. 王：那我们就来设计一种比较好的方法。我们完全可以利用前面的欧拉回路技术，但是在求解这个问题时，要做一个特殊的处理。
小可：父节点和子节点的判定刚好可以利用前面的父子关系判定！
Mr. 王：没错，这样欧拉回路构成的链表在顺序访问时，就会在从父节点向子节点遍历时增加1，这是在前序计数时我们所需要的；而在从子节点返回向父节点移动时，不增加值。在这个实例中，我们可以非常容易地得出结果，每一个节点的前序计数结果都是(parent(v),v) 这条边的rank，也就是：
Mr. 王：还有一类问题叫作求子树大小。求子树大小就是在树的每一个节点上标出其子树上节点的个数。这一次，我们依然采用欧拉回路技术。在从父节点去子节点的路上，我们依然在边上标注1 ；不同的是，在回来的路上，我们同样将权值设为1。这样，经过任何一条有向边，都会让ranking 的计数加1。
就像这样：
小可想了想，说 ：rank((v, p(v)))这个数描述了当遍历到达它时，已经经历过的边数，rank(( p(v),v))描述了当遍历从 v 的子树结束返回 v 时 ranking 的累积，两个 rank 作差，可以求出在这个子树中，究竟走了多少条边。
加上1 是为了调和v 自己本身；而除以2，是因为每一个节点的存在，都有一去一回两次。也就是说，rank 这个值会因为一个节点的存在而增加2。所以只要除以2，就可以让每个权值对应衡量一个节点的存在。
Mr. 王：非常好，你的解释很到位。
小可：对了，我想起来一个问题。我们前面提到了使用最大独立集，但还没有说怎么求最大独立集呢！
下期精彩预告：
经过学习，我们介绍了父子判定的应用——前序计数，运用欧拉回路技术的方法，及将树存储为链表的的策略来详细讲解。在下一期中，我们将讨论另一种磁盘中的大数据算法策略——时间前向处理方法，并讲解求解最大独立集的方法。更多精彩内容，敬请关注灯塔大数据，每周五不见不散呦！
内容来源：灯塔大数据经过学习，我们介绍了父子判定的应用——前序计数，运用欧拉回路技术的方法，及将树存储为链表的的策略来详细讲解。在下一期中，我们将讨论另一种磁盘中的大数据算法策略——时间前向处理方法，并讲解求解最大独立集的方法。更多精彩内容，敬请关注灯塔大数据，每周五不见不散呦！
点击
阅读原文
了解更多详情
阅读原文
了解更多详情
关注 灯塔大数据
微信扫一扫关注公众号
