Mark Allen Weiss 数据结构与算法分析 课后习题答案4.pdf

《Mark Allen Weiss 数据结构与算法分析 课后习题答案4.pdf》由会员分享，可在线阅读，更多相关《Mark Allen Weiss 数据结构与算法分析 课后习题答案4.pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Chapter 4:Trees4.1(a)A?.(b)G?,H?,I?,L?,M?,and K?.4.2For node B?:(a)A?.(b)D?and E?.(c)C?.(d)1.(e)3.4.34.4.4There are N?nodes.Each node has two pointers,so there are 2N?pointers.Each node butthe root has one incoming pointer from its parent,which accounts for N?1 pointers.Therest are NULL.?4.5Proof is

2、 by induction.The theorem is trivially true for H?=0.Assume true for H?=1,2,.,k?.A tree of height k?+1 can have two subtrees of height at most k?.These can have at most2k?+11 nodes each by the induction hypothesis.These 2k?+22 nodes plus the root prove thetheorem for height k?+1 and hence for all he

3、ights.4.6This can be shown by induction.Alternatively,let N?=number of nodes,F?=number offull nodes,L?=number of leaves,and H?=number of half nodes(nodes with one child).Clearly,N?=F?+H?+L?.Further,2F?+H?=N?1(see Exercise 4.4).Subtracting yieldsL?F?=1.4.7This can be shown by induction.In a tree with

4、 no nodes,the sum is zero,and in a one-nodetree,the root is a leaf at depth zero,so the claim is true.Suppose the theorem is true for alltrees with at most k?nodes.Consider any tree with k?+1 nodes.Such a tree consists of an i?node left subtree and a k?i?node right subtree.By the inductive hypothesi

5、s,the sum forthe left subtree leaves is at most one with respect to the left tree root.Because all leaves areone deeper with respect to the original tree than with respect to the subtree,the sum is atmost 12with respect to the root.Similar logic implies that the sum for leaves in the rightsubtree is

6、 at most 12,proving the theorem.The equality is true if and only if there are nonodes with one child.If there is a node with one child,the equality cannot be true becauseadding the second child would increase the sum to higher than 1.If no nodes have onechild,then we can find and remove two sibling

7、leaves,creating a new tree.It is easy to seethat this new tree has the same sum as the old.Applying this step repeatedly,we arrive at asingle node,whose sum is 1.Thus the original tree had sum 1.4.8(a)-*a b+c d e.(b)(a*b)*(c+d)-e.(c)a b*c d+*e-.-14-4.91234567912456794.11 This problem is not much dif

8、ferent from the linked list cursor implementation.We maintainan array of records consisting of an element field,and two integers,left and right.The freelist can be maintained by linking through the left field.It is easy to write the CursorNew?and CursorDispose?routines,and substitute them for malloc

9、 and free.4.12(a)Keep a bit array B?.If i?is in the tree,then B?i?is true;otherwise,it is false.Repeatedlygenerate random integers until an unused one is found.If there are N?elements already inthe tree,then M?N?are not,and the probability of finding one of these is(M?N?)/M?.Thus the expected number

10、 of trials is M?/(M?N?)=/(1).(b)To find an element that is in the tree,repeatedly generate random integers until analready-used integer is found.The probability of finding one is N?/M?,so the expectednumber of trials is M?/N?=.(c)The total cost for one insert and one delete is /(1)+=1+1/(1).Set-ting

11、 =2 minimizes this cost.4.15(a)N?(0)=1,N?(1)=2,N?(H?)=N?(H?1)+N?(H?2)+1.(b)The heights are one less than the Fibonacci numbers.4.16123456794.17 It is easy to verify by hand that the claim is true for 1 k?3.Suppose it is true for k?=1,2,3,.H?.Then after the first 2H?1 insertions,2H?1is at the root,an

12、d the right subtree isa balanced tree containing 2H?1+1 through 2H?1.Each of the next 2H?1insertions,namely,2H?through 2H?+2H?1 1,insert a new maximum and get placed in the right-15-subtree,eventually forming a perfectly balanced right subtree of height H?1.This followsby the induction hypothesis be

13、cause the right subtree may be viewed as being formed fromthe successive insertion of 2H?1+1 through 2H?+2H?1 1.The next insertion forces animbalance at the root,and thus a single rotation.It is easy to check that this brings 2H?tothe root and creates a perfectly balanced left subtree of height H?1.

14、The new key isattached to a perfectly balanced right subtree of height H?2 as the last node in the rightpath.Thus the right subtree is exactly as if the nodes 2H?+1 through 2H?+2H?1wereinserted in order.By the inductive hypothesis,the subsequent successive insertion of2H?+2H?1+1 through 2H?+1 1 will

15、 create a perfectly balanced right subtree of heightH?1.Thus after the last insertion,both the left and the right subtrees are perfectly bal-anced,and of the same height,so the entire tree of 2H?+1 1 nodes is perfectly balanced(andhas height H?).4.18 The two remaining functions are mirror images of

16、the text procedures.Just switch Right?and Left?everywhere.4.20 After applying the standard binary search tree deletion algorithm,nodes on the deletion pathneed to have their balance changed,and rotations may need to be performed.Unlike inser-tion,more than one node may need rotation.4.21(a)O?(log lo

17、g N?).(b)The minimum AVL tree of height 255(a huge tree).4.22_ _ _PositionDoubleRotateWithLeft(Position K3)Position K1,K2;K1=K3-Left;K2=K1-Right;K1-Right=K2-Left;K3-Left=K2-Right;K2-Left=K1;K2-Right=K3;K1-Height=Max(Height(K1-Left),Height(K1-Right)+1;K3-Height=Max(Height(K3-Left),Height(K3-Right)+1;

18、K2-Height=Max(K1-Height,K3-Height)+1;return K3;_ _ _-16-4.23 After accessing 3,12345678910111213After accessing 9,12345678910111213-17-After accessing 1,12345678910111213After accessing 5,12345678910111213-18-4.2412345789101112134.25(a)523776.(b)262166,133114,68216,36836,21181,13873.(c)After Find?(9

19、).4.26(a)An easy proof by induction.4.28(a-c)All these routines take linear time._ _ _/*These functions use the type BinaryTree,which is the same*/*as TreeNode*,in Fig 4.16.*/intCountNodes(BinaryTree T)if(T=NULL)return 0;return 1+CountNodes(T-Left)+CountNodes(T-Right);intCountLeaves(BinaryTree T)if(

20、T=NULL)return 0;else if(T-Left=NULL&T-Right=NULL)return 1;return CountLeaves(T-Left)+CountLeaves(T-Right);_ _ _-19-_ _ _/*An alternative method is to use the results of Exercise 4.6.*/intCountFull(BinaryTree T)if(T=NULL)return 0;return(T-Left!=NULL&T-Right!=NULL)+CountFull(T-Left)+CountFull(T-Right)

21、;_ _ _4.29 We assume the existence of a function RandInt(Lower,Upper),?which generates a uniformrandom integer in the appropriate closed interval.MakeRandomTree?returns NULL if N?isnot positive,or if N?is so large that memory is exhausted._ _ _SearchTreeMakeRandomTree1(int Lower,int Upper)SearchTree

22、 T;int RandomValue;T=NULL;if(Lower Element=RandomValue=RandInt(Lower,Upper);T-Left=MakeRandomTree1(Lower,RandomValue-1);T-Right=MakeRandomTree1(RandomValue+1,Upper);elseFatalError(Out of space!);return T;SearchTreeMakeRandomTree(int N)return MakeRandomTree1(1,N);_ _ _-20-4.30_ _ _/*LastNode is the a

23、ddress containing last value that was assigned to a node*/SearchTreeGenTree(int Height,int*LastNode)SearchTree T;if(Height=0)T=malloc(sizeof(*T);/*Error checks omitted;see Exercise 4.29.*/T-Left=GenTree(Height-1,LastNode);T-Element=+*LastNode;T-Right=GenTree(Height-2,LastNode);return T;elsereturn NU

24、LL;SearchTreeMinAvlTree(int H)int LastNodeAssigned=0;return GenTree(H,&LastNodeAssigned);_ _ _4.31 There are two obvious ways of solving this problem.One way mimics Exercise 4.29 byreplacing RandInt(Lower,Upper)with(Lower+Upper)/2.This requires computing2H?+11,which is not that difficult.The other m

25、imics the previous exercise by noting thatthe heights of the subtrees are both H?1.The solution follows:-21-_ _ _/*LastNode is the address containing last value that was assigned to a node.*/SearchTreeGenTree(int Height,int*LastNode)SearchTree T=NULL;if(Height=0)T=malloc(sizeof(*T);/*Error checks om

26、itted;see Exercise 4.29.*/T-Left=GenTree(Height-1,LastNode);T-Element=+*LastNode;T-Right=GenTree(Height-1,LastNode);return T;SearchTreePerfectTree(int H)int LastNodeAssigned=0;return GenTree(H,&LastNodeAssigned);_ _ _4.32 This is known as one-dimensional range searching.The time is O?(K?)to perform

27、theinorder traversal,if a significant number of nodes are found,and also proportional to thedepth of the tree,if we get to some leaves(for instance,if no nodes are found).Since theaverage depth is O?(log N?),this gives an O?(K?+log N?)average bound._ _ _voidPrintRange(ElementType Lower,ElementType U

28、pper,SearchTree T)if(T!=NULL)if(Lower Element)PrintRange(Lower,Upper,T-Left);if(Lower Element&T-Element Element);if(T-Element Right);_ _ _-22-4.33 This exercise and Exercise 4.34 are likely programming assignments,so we do not providecode here.4.35 Put the root on an empty queue.Then repeatedly Dequ

29、eue?a node and Enqueue?its left andright children(if any)until the queue is empty.This is O?(N?)because each queue operationis constant time and there are N?Enqueue?and N?Dequeue?operations.4.36(a)0,12:42,36:-4,58:-6,78,9(b)1,2,34:64,56,7,8-23-4.39ABDHIEJCFLOKMQPRGN4.41 The function shown here is cl

30、early a linear time routine because in the worst case it does atraversal on both T?1 and T?2._ _ _intSimilar(BinaryTree T1,BinaryTree T2)if(T1=NULL|T2=NULL)return T1=NULL&T2=NULL;return Similar(T1-Left,T2-Left)&Similar(T1-Right,T2-Right);_ _ _4.43 The easiest solution is to compute,in linear time,th

31、e inorder numbers of the nodes in bothtrees.If the inorder number of the root of T2 is x?,then find x?in T1 and rotate it to the root.Recursively apply this strategy to the left and right subtrees of T1(by looking at the valuesin the root of T2s left and right subtrees).If dN?is the depth of x?,then

32、 the running timesatisfies T?(N?)=T?(i?)+T?(N?i?1)+dN?,where i?is the size of the left subtree.In the worstcase,dN?is always O?(N?),and i?is always 0,so the worst-case running time is quadratic.Under the plausible assumption that all values of i?are equally likely,then even if dN?isalways O?(N?),the

33、 average value of T?(N?)is O?(N?log N?).This is a common recurrence thatwas already formulated in the chapter and is solved in Chapter 7.Under the more reason-able assumption that dN?is typically logarithmic,then the running time is O?(N?).4.44 Add a field to each node indicating the size of the tree it roots.This allows computation ofits inorder traversal number.4.45(a)You need an extra bit for each thread.(c)You can do tree traversals somewhat easier and without recursion.The disadvantage isthat it reeks of old-style hacking.-24-