MarkAllenWeiss数据结构与算法分析课后习题答案12388.pdf

Chapter 12:Advanced Data Structuresand Implementation12.3Incorporate an additional field for each node that indicates the size of its subtree.Thesefields are easy to update during a splay.This is difficult to do in a skip list.12.6If there are B black nodes on the path from the root to all leaves,it is easy to show byinduction that there are at most 2Bleaves.Consequently,the number of black nodes on apath is at most log N.Since there cant be two consecutive red nodes,the height isbounded by 2log N.12.7Color nonroot nodes red if their height is even and their parents height is odd,and blackotherwise.Not all red black trees are AVL trees(since the deepest red black tree isdeeper than the deepest AVL tree).12.19See H.N.Gabow,J.L.Bentley,and R.E.Tarjan,Scaling and Related Techniques forComputational Geometry,Proceedings of the Sixteenth Annual ACM Symposium onTheory of Computing(1984),135-143,or C.Levcopoulos and O.Petersson,HeapsortAdapted for Presorted Files,Journal of Algorithms 14(1993),395-413.12.29Pointers are unnecessary;we can store everything in an array.This is discussed in refer-ence 12.The bounds become O(klog N)for insertion,O(k2log N)for deletion of aminimum,O(k2N)for creation(an improvement over the bound in 12).12.35Consider the pairing heap with 1 as the root and children 2,3,.N.A DeleteMinremoves 1,and the resulting pairing heap is 2 as the root with children 3,4,.N;the costof this operation is N units.A subsequent DeleteMin sequence of 2,3,4,.will taketotal time(N2).-66-