Problem
• Say you set the key for each position p of a binary tree T equal to its pre-order rank. Under what circumstances is T a heap? In other words, what property should T have to be a heap? Discuss about such a property.
• If we are to insert "43," "18," and "2," on the binary tree shown below (it's also a heap!), what is the end result? Remember we need three steps to complete inserting in a heap: a) Place the new element in the next available position in the array. b) Compare the new element with its parent. If the new element is smaller, than swap it with its parent. c) Continue this process until either the new element's parent is smaller than the new element or it reaches the root.
• Consider a red-black tree (RBT) T storing 1,024 elements. What is the worst-case height of T? As you recall, the height is the black height. You do not have to be correct in terms of the answer, but try to show the reason why it should be that number.