What is the difference between the binary-search-tree property and the min-heap property (see page 129)? Can the min-heap property be used to print out the keys of an n-node tree in sorted order in O(n) time? Explain how or why not.
Answer to relevant QuestionsShow that if a node in a binary search tree has two children, then its successor has no left child and its predecessor has no right child.Show that the longest simple path from a node x in a red-black tree to a descendant leaf has length at most twice that of the shortest simple path from node x to a descendant leaf.Observe that whenever the size field of a node is referenced in either OS-SELECT or OSRANK, it is used only to compute the rank of the node in the sub tree rooted at that node. Accordingly, suppose we store in each node its ...Which is a more efficient way to determine the optimal number of multiplications in a matrix chain multiplication problem: enumerating all the ways of parenthesizing the product and computing the number of multiplications ...With a b-bit counter, we can ordinarily only count up to 2b – 1. With R. Morris's probabilistic counting, we can count up to a much larger value at the expense of some loss of precision. We let a counter value of i ...
Post your question