chap non-binary trees devise series of equivalence statements for collection of sixteen items that yields tree of height when both the weighted union rule and path compression are used what is the total number of parent pointers followed to perform this series one alternative to path compression that gives similar performance gains is called path halving in path halvingwhen the path is traversed from the node to the rootwe make the grandparent of every other node on the path the new parent of write version of find that implements path halving your find operation should work as you move up the treerather than require the two passes needed by path compression analyze the fraction of overhead required by the "list of childrenimplementationthe "left-child/right-siblingimplementationand the two linked implementations of section how do these implementations compare in space efficiency using the general tree adt of figure write function that takes as input the root of general tree and returns binary tree generated by the conversion process illustrated by figure use mathematical induction to prove that the number of leaves in nonempty full -ary tree is ( ) where is the number of internal nodes derive the formulae for computing the relatives of non-empty complete -ary tree node stored in the complete tree representation of section find the overhead fraction for full -ary tree implementation with space requirements as follows(aall nodes store datak child pointersand parent pointer the data field requires four bytes and each pointer requires four bytes (ball nodes store data and child pointers the data field requires sixteen bytes and each pointer requires four bytes (call nodes store data and parent pointerand internal nodes store child pointers the data field requires eight bytes and each pointer requires four bytes (donly leaf nodes store dataonly internal nodes store child pointers the data field requires four bytes and each pointer requires two bytes (awrite out the sequential representation for figure using the coding illustrated by example (bwrite out the sequential representation for figure using the coding illustrated by example