资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据关系的简化,长沙雅礼中学,何林,常用的数据关系：线性序列，树，图,1,2,4,3,6,5,1(1,1),2(2,1),4(3,1),3(4,4),5(5,4),6(6,4),1,2,3,4,5,7,8,1 2 4 2 5 8 5 2 7 2 1 3 1,坐船问题,雅礼中学有n个学生去公园划船。一条船最多可以坐两个人。如果某两个学生同姓或者同名就可以坐在一条船上。,学校希望每个同学都坐上船，同时学校想要租用最少的船。请问：学校至少要租多少船？,伍昱,伍平,何林,何刚,黄刚,何凡,伍昱,伍平,黄刚,何刚,何林,何凡,伍昱,伍平,黄刚,何刚,何林,何凡,最优解,OR,图-树,伍昱,伍平,黄刚,何刚,何林,何凡,一个包含,n,个点的无向图,同名或者同姓的人之间连一条边,图模型,最小边覆盖,任意图最大匹配！,伍昱,伍平,何林,何刚,黄刚,何凡,伍昱,伍平,黄刚,何刚,何林,何凡,树结构,一片森林,每个节点和左孩子同姓,每个节点和右孩子同名,树的构造,首先假设所有人是一个连通图,黄刚,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,周涛,张药师,树的构造,首先假设所有人是一个连通图,雷锋,雷涛,黄,涛,欧阳锋,黄,嘎,张嘎,雷震子,黄,药师,周涛,黄,刚,张药师,没有左儿子了,树的构造,首先假设所有人是一个连通图,雷锋,雷涛,黄,涛,欧阳锋,黄,嘎,张嘎,雷震子,黄,药师,周涛,黄,刚,张药师,树的构造,首先假设所有人是一个连通图,黄刚,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,周涛,张药师,欧阳涛,树的构造,首先假设所有人是一个连通图,黄刚,雷锋,雷,涛,黄,涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,周,涛,张药师,欧阳,涛,没有右儿子,树的构造,首先假设所有人是一个连通图,黄刚,雷锋,雷,涛,黄,涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,周,涛,张药师,欧阳,涛,树的匹配,黄刚,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,周涛,张药师,欧阳涛,分析叶子节点,独子！,树的匹配,黄刚,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,周涛,张药师,欧阳涛,独子的情况,他们坐一条船,剩下的树依然是连通的,树的匹配,黄刚,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,张药师,分析叶子节点,落单！,树不连通！,不是独子,树的匹配,黄刚,雷锋,雷涛,黄涛,欧阳锋,黄嘎,张嘎,雷震子,黄药师,张药师,分析叶子节点,树的匹配,非独子的情况,每次让两个人坐上一条船,树始终保持连通,假设树中有n个点，(n+1)/2条船即可容纳所有人。,这无疑是最优解。,树的匹配,设森林中有m棵树，所有树的规模是n,1,n,2,n,m,。,对每棵树分别处理。,答案是,(i=1.m),(n,i,+1)/2,森林的匹配,图-树小结,伍昱,伍平,黄刚,何刚,何林,何凡,任意图最大匹配！,伍昱,伍平,黄刚,何刚,何林,何凡,简单贪心,O(n,2,),或,O(n,3,),的时间复杂度,编程复杂度很高,O(n,),的时间复杂度,编程复杂度很低,树的统计,一棵树含有,n,个节点。,节点编号为,1,2,3,n,。,定义,t(v,),为,v,的后代中所有编号小于,v,的节点个数。,求,t(1),t(2),t(3),t(n,),。,树-线性,树-线性,7,10,1,9,3,4,11,6,8,5,15,12,2,14,13,t(9)=3,t(10)=1,t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,0 0 0 0 0 1 6 0 3 1 0 0 0 2 0,对每个点，逐个检查其后代。,时间复杂度,O(n,2,),。,当,n=30000,就不可承受。,树-线性,后代,如何把这个“先后”顺序表现出来呢,树-线性,7,10,1,9,3,4,11,6,8,5,15,12,2,14,13,线性,一个序列中元素之间的先后关系十分明显,7,10,14,2,13,1,9,11,6,5,8,3,15,12,4,树-线性,7,10,1,9,3,4,11,6,8,5,15,12,2,14,13,线性,一个序列中元素之间的先后关系十分明显,7,10,14,2,13,1,9,11,6,5,8,3,15,12,4,对应,后代,多出来的部分,9,树-线性,7,10,1,9,3,4,11,6,8,5,15,12,2,14,13,线性,逆序DFS遍历,7,10,14,2,13,1,9,11,6,5,8,3,15,12,4,树-线性,7,10,1,9,3,4,11,6,8,5,15,12,2,14,13,线性,对应,后代,多出来的部分,9,7,10,14,2,13,1,9,11,6,5,8,3,15,12,4,树-线性,7,10,1,9,3,4,11,6,8,5,15,12,2,14,13,7 10 14 2 13 1 9 11 6 5 8 3 15 12 4,7 4 3 12 15 9 6 8 5 11 1 10 14 13 2,DFS遍历,逆DFS遍历,树-线性,7,10,1,9,3,4,11,6,8,5,15,12,2,14,13,7 10 14 2 13 1 9 11 6 5 8 3 15 12 4,7 4 3 12 15 9 6 8 5 11 1 10 14 13 2,DFS遍历,逆DFS遍历,后代！,重叠-容斥原理,树-线性,7,10,1,9,3,4,11,6,8,5,15,12,2,14,13,7 10 14 2 13 1 9 11 6 5 8 3 15 12 4,7 4 3 12 15 9 6 8 5 11 1 10 14 13 2,DFS遍历,逆DFS遍历,9的直系祖先,红+蓝+黄=全部+后代,树-线性,7,10,1,9,3,4,11,6,8,5,15,12,2,14,13,7 10 14 2 13 1 9 11 6 5 8 3 15 12 4,7 4 3 12 15 9 6 8 5 11 1 10 14 13 2,DFS遍历,逆DFS遍历,红+蓝+黄=全部+后代,红：,DFS,序列中节点,v,后比他小的数的个数,蓝：逆,DFS,序列中节点,v,后比他小的数的个数,黄：,v,的直系祖先中比,v,小的节点个数,全部：,v-1,树-线性,红+蓝+黄=全部+后代,红：,DFS,序列中节点,v,后比他小的数的个数,蓝：逆,DFS,序列中节点,v,后比他小的数的个数,黄：,v,的直系祖先中比,v,小的节点个数,全部：,v-1,红：,DFS,序列中节点,v,后比他小的数的个数,问题：已知一个序列(DFS序列)，求每个数后面有多少个数比他小。,解答：用线段树即时更新。时间复杂度O(nlogn)。,树简化成线性结构后带来的“序”关系,树-线性,红+蓝+黄=全部+后代,红：,DFS,序列中节点,v,后比他小的数的个数,蓝：逆,DFS,序列中节点,v,后比他小的数的个数,黄：,v,的直系祖先中比,v,小的节点个数,全部：,v-1,蓝：逆,DFS,序列中节点,v,后比他小的数的个数,问题：已知一个序列(,逆,DFS序列)，求每个数后面有多少个数比他小。,解答：用线段树即时更新。时间复杂度O(nlogn)。,树简化成线性结构后带来的“序”关系,树-线性,红+蓝+黄=全部+后代,红：,DFS,序列中节点,v,后比他小的数的个数,蓝：逆,DFS,序列中节点,v,后比他小的数的个数,黄：,v,的直系祖先中比,v,小的节点个数,全部：,v-1,黄：,v,的直系祖先中比,v,小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,树-线性,红+蓝+黄=全部+后代,黄：,v,的直系祖先中比,v,小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7,树-线性,红+蓝+黄=全部+后代,黄：,v,的直系祖先中比,v,小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7 10,7,树-线性,红+蓝+黄=全部+后代,黄：,v,的直系祖先中比,v,小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7 10 14,7 10,7,树-线性,红+蓝+黄=全部+后代,黄：,v,的直系祖先中比,v,小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7 10 14 2,7 10 14,7 10,7,树-线性,红+蓝+黄=全部+后代,黄：,v,的直系祖先中比,v,小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7 10 14 13,7 10 14 2,7 10 14,7 10,7,树-线性,红+蓝+黄=全部+后代,黄：,v,的直系祖先中比,v,小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7 10 14 13,7 10 14 2,7 10 14,7 10,7,7 1,树-线性,红+蓝+黄=全部+后代,黄：,v,的直系祖先中比,v,小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7 10 14 13,7 10 14 2,7 10 14,7 10,7,7 1,7 9,树-线性,红+蓝+黄=全部+后代,黄：,v,的直系祖先中比,v,小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7 10 14 13,7 10 14 2,7 10 14,7 10,7,7 1,7 9,7 9 11,树-线性,红+蓝+黄=全部+后代,黄：,v,的直系祖先中比,v,小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7 10 14 13,7 10 14 2,7 10 14,7 10,7,7 1,7 9,7 9 11,7 9 6,树-线性,红+蓝+黄=全部+后代,黄：,v,的直系祖先中比,v,小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7 10 14 13,7 10 14 2,7 10 14,7 10,7,7 1,7 9,7 9 11,7 9 6,7 9 6 5,树-线性,红+蓝+黄=全部+后代,黄：,v,的直系祖先中比,v,小的节点个数,7,10,1,9,3,4,11,6,8,5,15,2,14,13,7 10 14 13,7 10 14 2,7 10 14,7 10,7,7 1,7 9,7 9 11,7 9 6,7 9 6 5,13的直系祖先,5的直系祖先,深度优先搜索中要用到一个栈来存储节点（比如递归）。,任意时刻，栈顶元素的直系祖先就是栈中其余的节点。,用一棵线段树来维护这个栈。求每个节点的直系祖先中有多少个比他本身小就能用,O(nlogn,),的时间复杂度实现。,树-线性,红+蓝+黄=全部+后代,红：,DFS,序列中节点,v,后比他小的数的个数,蓝：逆,DFS,序列中节点,v,后比他小的数的个数,黄：,v,的直系祖先中比,v,小的节点个数,全部：,v-1,综合上面的分析，红、蓝、黄我们都能在O(nlogn)的时间复杂度内求出。所以整个问题解决，时间复杂度是O(nlogn)。,树-线性 小结,7,10,1,9,3,4,11,6,8,5,15,12,2,14,13,7 10 14 2 13 1 9 11 6 5 8 3 15 12 4,7 4 3 12 15 9 6 8 5 11 1 10 14 13 2,DFS遍历,逆DFS遍历,9的直系祖先,红+蓝+黄=全部+后代,图,树，,树,序列。,有时候不需要包罗万象的所有信息,合理的组织数据之间的关系,利用简化数据关系实现数据的有序化,简化后的关系更明了，有利于窥见本质矛盾。,数据关系的简化,谢谢！,
展开阅读全文