Floor and ceiling

Questions 1 to 5 of 7

1. 1. A tree holds the keys 10 and 20. closest_key is called with target 15. Which key does it return?

   201015none
2. 2. Which tree makes a floor query take about 1000 steps when the tree holds 1000 keys?

   A chain of 1000 keys inserted in sorted orderA balanced tree of 1023 keysThe seven-node tree from the first exampleAny tree where the target is missing
3. 3. The tree is built by inserting 8, 3, 10, 1, 6, 14, 4, 7 and 13 in that order. Using floor_key and ceiling_key from this lesson, what does this print? ``cpp std::cout << "floor=" << show(floor_key(root.get(), 11)) << " ceiling=" << show(ceiling_key(root.get(), 11)) << '\n'; ``

   floor=10 ceiling=10floor=11 ceiling=13floor=10 ceiling=13floor=13 ceiling=14
4. 4. Same nine-node tree. floor_key_buggy is the version that never saves the candidate. What does this print? ``cpp std::cout << "floor(5) = " << show(floor_key_buggy(root.get(), 5)) << '\n'; ``

   floor(5) = 4floor(5) = 6floor(5) = 3floor(5) = none
5. 5. On the nine-node tree, what is ceiling_key(root.get(), 15)? Write a number, or none if there is no answer.

   Type your answer.