树的相关知识.ppt
《树的相关知识.ppt》由会员分享,可在线阅读,更多相关《树的相关知识.ppt(84页珍藏版)》请在三一办公上搜索。
1、树的相关知识,雅礼 朱全民,红楼梦贾府关系结构示意图,树,树的定义:树是具有以下性质的有限结点集合:(1)有一个被称为“根”的结点。(2)根的所有孩子都是一颗子树的根。,树的相关术语,结点的度(degree):该结点拥有的子数数目。右图中:degree(A)=3,degree(F)=0叶子(leaf):度为0的结点双亲(parent):拥有子树的结点孩子(child):某个双亲结点的子树的根兄弟(sibling):拥有同一个双亲结点的孩子祖先(ancestor):从某一个结点往上一直到根经过的所有结点后代(descendants):子树的所有结点层次(level):双亲的层次+1;根的层次=1
2、.高度(height)/深度(depth):max levels.,树的表示(列表表示法),(A),(A(B,C,D),(A(B(E,F),C(G),D(H,I,J),(A(B(E(K,L),F),C(G),D(H(M),I,J),树的结点的大小将会随着其子树的数目不同而变化,这对我们来说显然不是一个很好的方法。,树的表示(双亲表示法),双亲表示法 type tnode=record data:datatype;parent:integer;end;,每个结点都指向它的双亲,可以很方便从叶子找到祖先,但不能从根结点往下找。,树的表示(孩子兄弟表示法),二叉树,二叉树是度不超过2的树二叉树的特性
3、:第 i 层的最大结点数为2i1,高度为k的二叉树的最大结点数为2k1,二叉树的表示(数组表示法),对于用数组表示的完全二叉树,对于任意结点i,有:,二叉树的表示(孩子表示法),常用的存储结构 type bitree=node node=record data:datatype;lchild,rchild:bitree;end;,二叉树的遍历,遍历(先序遍历,中序遍历,后序遍历)Proc preorder(bt:bitree);if btNil then visit(bt)preorder(bt.lchild);preorder(bt.rchild);endP,二叉树的性质,在二叉树的第i层上
4、最多有2i-1个结点深度为K的二叉树最多有2k-1个结点在二叉树中,叶子结点的总数总比为度数为2的结点多1有n个结点的完全二叉树的结点按层序编号,则对任意一结点i,有(1)如果i=1,则结点i是二查树的根,无双亲;如果i1,则双亲是i/2(2)如果2in,则结点i无左孩子,否则左孩子为2i(3)如果2i+1n,则结点i无右孩子,否则右孩子为2i+1,树与二叉树的转换,任意一棵树的孩子兄弟表示法都有唯一对应的一颗二叉树,根结点的右孩子总是为空,森林转化为二叉树,用“孩子兄弟表示法”可以将任意一棵树转化为二叉树的形式 森林转化为二叉树 如果F=T1,T2,Tm是森林,则可按如下规则转化为一棵二叉树
5、。1)若F为空,即m=0,则B为空树 2)若F非空,即m0,则B的根root即为森林中第一棵树的根root(T1),B的左子树为从T1中子树森林F1=T11,T12,T1i转换而成的二叉树;其右子树Rb 是从森林F=T2,Tm中转换出来的二叉树,二叉排序树(Binary Sort Tree),二叉排序树又称为二叉查找(搜索)树(BST)它或者是一颗空树,或者是具有如下性质的二叉树:1)若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值2)若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值3)它左右子树分别为二叉排序树。,BST的特点,(1)二叉排序树中任一结点x,其左(右)
6、子树中任一结点y(若存在)的关键字必小(大)于x的关键字。(2)二叉排序树中,各结点关键字是惟一的。实际应用中,不能保证被查找的数据集中各元素的关键字互不相同,所以可将二叉排序树定义中BST性质(1)里的小于改为大于等于,或将BST性质(2)里的大于改为小于等于,甚至可同时修改这两个性质。(3)按中序遍历该树所得到的中序序列是一个递增有序序列。,二叉排序树,在二叉树中,边有两种:红边:表示是父亲的左儿子蓝边:表示是父亲的右儿子,实例,BST的查找,FUNC bstsrch(t:bitreptr;K:keytype):bitree if(t=nil)or(t.key=K)then return(
7、t)else if t.keyK then return(bstsrch(t.lchild,k)else return(bstsrch(t.rchild,k)endF,BST的插入,在二叉排序树中插入新结点,要保证插入后仍满足BST性质。其插入过程是:(a)若二叉排序树T为空,则为待插入的关键字key申请一个新结点,并令其为根;(b)若二叉排序树T不为空,则将key和根的关键字比较:(i)二者相等,则说明树中已有此关键字key,无须插入。(ii)keyTkey,则将它插入根的右子树中。子树中的插入过程与上述的树中插入过程相同。如此进行下去,直到将key作为一个新的叶结点的关键字插入到二叉排序树
8、中,或者直到发现树中已有此关键字为止。,BST插入的递归算法,PROC ins_bstree(var bst:bitree;k:keytp);采用链式存储结构 begin new(s);s.key:=k;s.lchild:=nil;s.rchild:=nil;if bst=nil then bst:=s;else if Kfkey then f.lchild:=s;else f.rchild:=send;,BST的生成为进行不断插入的过程!但在生成BST的时候,可能会由于根结点选择不好,使得树很斜,查找的效率降低,可以使用随机产生根结点的方法,使得BST较平衡,下图就是两棵关键字相同的BST树
9、.,删除,分三种情况讨论1)删除叶子节点不破坏树的结构,修改其双亲结点:f.lchild:=NIL2)若只有左孩子Pl或者只有右孩子Pr,则只要令Pl或Pr直接为f的左孩子即可:f.lchild:=P.lchild;或者f.lchild:=P.rchild;3)左右孩子都有,设中序遍历的序列为ClC.QlQSlSPPrF,令P的左孩子为f的右孩子,而P的右孩子为S的右孩子 q:=p;s:=p.lchild;while srchildnil do q:=s;s:=s.rchild p.data:=s.data;if qp then q.rchild:=s.lchild else q.lchild
10、:=s.lchild dispose(s),练习,写一个程序,读入n个整数,构建二叉排序树,输出二叉排序树的中序遍历结果。n=100000,样例,7-表示有7个数3265741,二叉查找树时间复杂度分析,二叉查找树(Binary Search Tree)可以被用来表示有序集合、建立索引或优先队列等。最坏情况下,作用于二叉查找树上的基本操作的时间复杂度,可能达到O(n)。某些二叉查找树的变形,基本操作在最坏情况下性能依然很好,如红黑树、AVL树等。,Splay 树,Splay树是二叉查找树的改进。对Splay树的操作的均摊复杂度是O(log2n)。Splay树与二叉查找树一样,也具有有序性。即S
11、play树中的每一个节点x都满足:该节点左子树中的每一个元素都小于x,而其右子树中的每一个元素都大于x。Splay树的核心思想就是通过Splay操作进行自我调整,从而获得平摊较低的时间复杂度。,Splay操作,Splay操作是在保持Splay树有序性的前提下,通过一系列旋转操作将树中的元素x调整至树的根部的操作(Zig:右旋,Zag:左旋)。在旋转的过程中,要分三种情况分别处理:1)Zig 或 Zag 2)Zig-Zig 或 Zag-Zag 3)Zig-Zag 或 Zag-Zig,Splay操作 情况1,Zig或Zag操作:节点x的父节点y是根节点。,Splay操作 情况2,Zig-Zig或Z
12、ag-Zag操作:节点x的父节点y不是根节点,且x与y同时是各自父节点的左孩子或者同时是各自父节点的右孩子。,Spaly操作 情况3,Zig-Zag或Zag-Zig操作:节点x的父节点y不是根节点,x与y中一个是其父节点的左孩子而另一个是其父节点的右孩子。,Splay操作举例,Splay(1,S),Spaly树基本操作,查找:与二叉排序树查找类似,只是查找结束后要将找到的元素通过Splay操作旋转到根。插入:用查找过程找到要插入的位置,进行插入。然后将新元素旋转到根。删除:首先在树中找到要删除的元素,将他转到根节点并删去,这样原来的树就分裂成了两棵树,然后将左子树中拥有最大关键字的那一个元素转
13、到根,由于它是左子树中的最大元素,所以他不存在有儿子,这样只要把原来的右子树作为他的右子树,就重新合并成了一棵树。可见在Splay树的基本操作中,处处要用到Splay旋转操作!,应用:Pet,宠物收养场提供两种服务:收养被离弃的宠物与让新的主人领养宠物。每个宠物有不相同的特点值。领养人所希望的特点值也不相同。如果领养人/遗弃宠物过多,则当前来的宠物/领养人选择离其特点值最近的(如果有两个特点值与其同样接近,则选择较小的)领养人/宠物,被领养/领养。并且纪录两个特点值的差值。输入N条请求(X,Y),X=0表示宠物;X=1表示领养人,Y为特征值。任务是计算所有差值的和。(N=80000,等待的宠物
14、/领养者数M=10000),字典树(trie),当关键字是串的时候,往往用trie。我们的动机是:利用串的公共前缀来节约内存,加快检索速度。例如,需要保存“computer”和“command”,由于它们的前三个字母是相同的,所以希望它们共享前三个字母,而只有剩下部分才进行分开储存。,例如,需要保存以下8个单词:becausebeforebegbeggarbelongbelowdaydead,Trie的特点,根节点不包含字母,除根节点外每一个节点都仅包含一个英文字母从根节点到某一节点,路径上经过的字母依次连起来所构成的字母序列,称为该节点对应的单词。每个节点的所有儿子包含的字母都不相同。插入和
15、删除的时间均为O(L)L为字符串的长度,应用:最长前缀,给定n个字符串,即基元给定一个字符串T,即生物体的结构要找出字符串T由基元构成的前缀,使得该前缀的长度最大N=100,Len(T)=500000,基元长度L=20,样例基元:A,AB,BBC,CA,BA T:ABABACABAABCB最长前缀构成有三种方法 A+BA+BA+CA+BA+AB AB+AB+A+CA+BA+AB AB+A+BA+CA+BA+AB长度为11,分析,为了尽快的查找到基元,我们把基元构成一个单词树,也叫trie树。如下图为样例的单词树。该树最多为26叉树,任何单词要么是某个单词的前缀,要么为从根到叶子结点组成的单词。
16、这样我们只需要O(L)的时间即可查找到某个单词,L为单词的长度。,动态规划,我们设前j个字符已经匹配,考虑前i个字符是否能匹配,主要看从i+1j组成的字符串是否是单词因此设f(i)表示前i个字符是否已匹配,若能匹配则为真(用1表示),否则为假(用0表示)。则有:,时间复杂度分析,每次求f(i)需要向前找f(j),i-jL,每移动一次j需要判定word(j+1,i)是否是单词1=i=len(T),1=i-jL查找单词时间复杂度为O(L)因此总时间复杂度为O(len(T)*L2)。因为T=500000,L=20,因此,5*105*202=2*108,并查集引例,写一个数据结构,支持一下两种操作:现
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 相关 知识
链接地址:https://www.31ppt.com/p-2405034.html