this is all one question

Problem 4: Avocado Pastas? Please, Let's Eat! (20pt) The treap is a BST that is modified by combining it with a randomized heap. Each node contains a key and a secondary random key that is generated when the node is initialized. Nodes in the treap are organized so that the keys satisfy the standard BST property while the secondary keys satisfy the partial order of a min heap. Answer the following questions about treaps as you strive to escape the exam. Make sure that you justify your answer. 4.1 What is the asymptotic complexity of search in a Treap? Explain in your own words for full credit 4.2 What relationship, if any, would you expect to find between the treaps generated by two different programmers using the same keys and the same algorithm? Explain your answer for full credit. 4.3 Suppose that I have a file containing a binary tree where each node contains two pieces of data. Based only on the Ist data value, the structure is known to be a BST with the keys in ascending order. Explain an efficient algorithm that would examine the 2nd data value in each node to determine whether or not the structure is a treap. I want a clear, concise answer in English-no code or pseudocode. 4.4 Suppose that you have implemented the treap described above and receive a request from a potential customer to produce the keys in descending order. Explain how you would modify the existing treap to satisfy the new requirement in English again, no code or pseudo code. 4.5 Suppose that a colleague mistakenly implements a treap using a max heap. Explain the impact of this unauthorized modification on the expected behavior of the treap