《树的相关知识》由会员分享，可在线阅读，更多相关《树的相关知识（83页珍藏版）》请在金锄头文库上搜索。
1、树的相关知识,雅礼 朱全民,红楼梦贾府关系结构示意图,树,树的定义： 树是具有以下性质的有限结点集合：(1) 有一个被称为“根”的结点。(2) 根的所有孩子都是一颗子树的根。,树的相关术语,结点的度（degree）：该结点拥有的子数数目。右图中：degree(A) = 3, degree(F) = 0 叶子（leaf）：度为0的结点 双亲（parent）：拥有子树的结点 孩子（child）：某个双亲结点的子树的根 兄弟（sibling）：拥有同一个双亲结点的孩子 祖先（ancestor）：从某一个结点往上一直到根经过的所有结点 后代（descendants）：子树的所有结点 层次（level）
2、：双亲的层次 + 1; 根的层次 = 1. 高度（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=recorddata:datatype;parent:intege
3、r; end;,每个结点都指向它的双亲，可以很方便从叶子找到祖先，但不能从根结点往下找。,树的表示（孩子兄弟表示法）,二叉树,二叉树是度不超过2的树 二叉树的特性：第 i 层的最大结点数为2i1，高度为k的二叉树的最大结点数为2k1,二叉树的表示（数组表示法）,对于用数组表示的完全二叉树，对于任意结点i，有：,二叉树的表示（孩子表示法）,常用的存储结构 type bitree=nodenode=recorddata :datatype;lchild,rchild:bitree;end;,二叉树的遍历,遍历( 先序遍历, 中序遍历, 后序遍历) Proc preorder(bt:bitree);
4、if btNil then visit(bt)preorder(bt.lchild);preorder(bt.rchild); endP,二叉树的性质,在二叉树的第i层上最多有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,树与二叉树的转换,任意一棵树的孩子兄弟表示法都有唯一对应的一颗二叉
5、树,根结点的右孩子 总是为空,森林转化为二叉树,用“孩子兄弟表示法”可以将任意一棵树转化为二叉树的形式森林转化为二叉树如果F=T1, T2, ,Tm是森林，则可按如下规则转化为一棵二叉树。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)若它的左子树不
6、空，则左子树上所有结点的值均小于它的根结点的值 2) 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值 3)它左右子树分别为二叉排序树。,BST的特点,（1） 二叉排序树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。 （2） 二叉排序树中，各结点关键字是惟一的。实际应用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可将二叉排序树定义中BST性质(1)里的“小于“改为“大于等于“，或将BST性质(2)里的“大于“改为“小于等于“，甚至可同时修改这两个性质。 （3） 按中序遍历该树所得到的中序序列是一个递增有序序列。,二叉排序树,在二叉树中
7、，边有两种：红边： 表示是父亲的左儿子 蓝边： 表示是父亲的右儿子,实例,BST的查找,FUNC bstsrch(t:bitreptr;K:keytype):bitreeif (t=nil) or (t.key=K) then return(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不
8、为空，则将key和根的关键字比较：(i)二者相等，则说明树中已有此关键字key，无须插入。 (ii)keyTkey，则将它插入根的右子树中。 子树中的插入过程与上述的树中插入过程相同。如此进行下去，直到将key作为一个新的叶结点的关键字插入到二叉排序树中，或者直到发现树中已有此关键字为止。,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.
9、lchild:=s;else f.rchild:=s end;,BST的生成为进行不断插入的过程! 但在生成BST的时候,可能会由于根结点选择不好,使得树很斜,查找的效率降低,可以使用随机产生根结点的方法,使得BST较平衡,下图就是两棵关键字相同的BST树.,删除,分三种情况讨论 1)删除叶子节点不破坏树的结构,修改其双亲结点: f.lchild:=NIL 2)若只有左孩子Pl或者只有右孩子Pr,则只要令Pl或Pr直接为f的左孩子即可:f.lchild:=P.lchild;或者f.lchild:=P.rchild;3)左右孩子都有,设中序遍历的序列为ClC.QlQSlSPPrF,令P的左孩子为
10、f的右孩子,而P的右孩子为S的右孩子 q:=p;s:=p.lchild;while srchildnil do q:=s;s:=s.rchildp.data:=s.data;if qp then q.rchild :=s.lchildelse q.lchild :=s.lchilddispose(s),练习,写一个程序，读入n个整数，构建二叉排序树，输出二叉排序树的中序遍历结果。n=100000,样例,7 - 表示有7个数 3 2 6 5 7 4 1,二叉查找树时间复杂度分析,二叉查找树(Binary Search Tree) 可以被用来表示有序集合、建立索引或优先队列等。最坏情况下，作用于二
11、叉查找树上的基本操作的时间复杂度，可能达到O(n)。某些二叉查找树的变形，基本操作在最坏情况下性能依然很好，如红黑树、AVL树等。,Splay 树,Splay树是二叉查找树的改进。 对Splay树的操作的均摊复杂度是O(log2n)。 Splay树与二叉查找树一样，也具有有序性。即Splay树中的每一个节点x都满足：该节点左子树中的每一个元素都小于x，而其右子树中的每一个元素都大于x。Splay树的核心思想就是通过Splay操作进行自我调整，从而获得平摊较低的时间复杂度。,Splay操作,Splay操作是在保持Splay树有序性的前提下，通过一系列旋转操作将树中的元素x调整至树的根部的操作(Z
12、ig:右旋,Zag:左旋)。在旋转的过程中，要分三种情况分别处理：1)Zig 或 Zag2)Zig-Zig 或 Zag-Zag3)Zig-Zag 或 Zag-Zig,Splay操作 情况1,Zig或Zag操作： 节点x的父节点y是根节点。,Splay操作 情况2,Zig-Zig或Zag-Zag操作：节点x的父节点y不是根节点，且x与y同时是各自父节点的左孩子或者同时是各自父节点的右孩子。,Spaly操作 情况3,Zig-Zag或Zag-Zig操作：节点x的父节点y不是根节点，x与y中一个是其父节点的左孩子而另一个是其父节点的右孩子。,Splay操作举例,Splay(1,S),Spaly树基本操
13、作,查找：与二叉排序树查找类似，只是查找结束后要将找到的元素通过Splay操作旋转到根。插入：用查找过程找到要插入的位置，进行插入。然后将新元素旋转到根。删除：首先在树中找到要删除的元素，将他转到根节点并删去，这样原来的树就分裂成了两棵树，然后将左子树中拥有最大关键字的那一个元素转到根，由于它是左子树中的最大元素，所以他不存在有儿子，这样只要把原来的右子树作为他的右子树，就重新合并成了一棵树。可见在Splay树的基本操作中，处处要用到Splay旋转操作！,应用：Pet,宠物收养场提供两种服务：收养被离弃的宠物与让新的主人领养宠物。每个宠物有不相同的特点值。领养人所希望的特点值也不相同。如果领养
14、人/遗弃宠物过多，则当前来的宠物/领养人选择离其特点值最近的（如果有两个特点值与其同样接近，则选择较小的）领养人/宠物，被领养/领养。并且纪录两个特点值的差值。 输入N条请求(X,Y)，X=0表示宠物;X=1表示领养人，Y为特征值。 任务是计算所有差值的和。 （N=80000，等待的宠物/领养者数M=10000）,字典树（trie）,当关键字是串的时候，往往用trie。我们的动机是：利用串的公共前缀来节约内存，加快检索速度。 例如，需要保存“computer”和“command”，由于它们的前三个字母是相同的，所以希望它们共享前三个字母，而只有剩下部分才进行分开储存。,例如，需要保存以下8个单
15、词： because before beg beggar belong below day dead,Trie的特点,根节点不包含字母，除根节点外每一个节点都仅包含一个英文字母 从根节点到某一节点，路径上经过的字母依次连起来所构成的字母序列，称为该节点对应的单词。 每个节点的所有儿子包含的字母都不相同。 插入和删除的时间均为O(L) L为字符串的长度,应用：最长前缀,给定n个字符串，即基元 给定一个字符串T，即生物体的结构 要找出字符串T由基元构成的前缀，使得该前缀的长度最大 N=100,Len(T)=500000,基元长度L =20,样例 基元：A，AB，BBC，CA，BAT: ABABAC
16、ABAABCB 最长前缀构成有三种方法A+BA+BA+CA+BA+AB AB+AB+A+CA+BA+AB AB+A+BA+CA+BA+AB 长度为11,分析,为了尽快的查找到基元，我们把基元构成一个单词树，也叫trie树。如下图为样例的单词树。 该树最多为26叉树，任何单词要么是某个单词的前缀，要么为从根到叶子结点组成的单词。 这样我们只需要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,
