Exercises B#

Note

You must complete these exercises by Wednesday of W7.

Exercise 3.2.1 (True/False)#

True or False?

Binary Search Trees#

Note: BST is understood here as the implementation from the textbook, i.e., a tree that is not necessarily balanced. The 2-3 / red-black BST is also understood to be the one in the reference textbook.

We recommend that you first become familiar with the notions of tree traversals: inorder (infix), preorder (prefix), and postorder (postfix).

  • Given the output of an inorder traversal of a BST containing \(N\) distinct keys, is it possible to reconstruct the shape of the BST based on the result of the traversal? If so, write the pseudocode of an algorithm to do so; if not, give a counterexample that justifies your answer.

  • Given the output of a preorder traversal of a BST containing \(N\) distinct keys, is it possible to reconstruct the shape of the BST based on the result of the traversal? If so, write the pseudocode of an algorithm to do so; if not, give a counterexample that justifies your answer.

  • Given a binary search tree of \(N\) distinct keys and a key \(x\), is it possible to find the smallest key strictly greater than \(x\) in logarithmic time in the worst case?

  • The expected height of a BST resulting from inserting \(N\) distinct keys in a random order into an initially empty tree is on average logarithmic.

  • Let \(x\) be a node in a BST. The successor of \(x\) (the node containing the next key in ascending order) is the leftmost node in the right subtree of \(x\).

Red-Black Trees#

For the statements related to red-black trees, we advise you to first translate them into statements about 2-3 trees, as there is a one-to-one mapping between the two representations. In most cases, it is easier to evaluate the validity of the statement for 2-3 trees.

  • The maximum height of a 2-3 tree with \(N\) keys is \(\sim \log_3 N\).

  • When inserting \(N\) keys in ascending order into an initially empty red-black BST, the number of color changes for the last insertion is at most 3. The number of color changes is defined as the sum of the absolute differences between the number of red links after insertion and the number of red links before insertion.

  • Does a red-black BST obtained after inserting \(N > 1\) keys into an initially empty tree always have at least one red link? If not, give a counterexample.

  • In a red-black BST of \(N\) nodes, the black height (i.e., the number of black links on each path from the root to a null link) is at most \(\log_2 N\).

Exercise 3.2.2 (Sorting with BST)#

Imagine a sorting algorithm using a BST. What would this algorithm look like? What would be the complexity of your algorithm if the BST is replaced by a red-black BST?

Exercise 3.2.3 (Delete Complexity)#

What is the time complexity of deleting key 5 from the BST depicted below using the textbook implementation?

  15
    \
     x
    / \
   /   \
  /     \
 /n nodes\
/         \
-----------

Exercise 3.2.4 (Delete Commutativity)#

Is the delete operation (as implemented in the book) in a BST « commutative »? That is, deleting \(x\) and then directly \(y\) from a BST leaves the tree in the same state as if we had first deleted \(y\) and then \(x\)? Give a counterexample or argue why this is indeed always the case. To help you, consider the following tree and the deletion operations of 5 and 10.

  10
 / \
5   15
   /
  11

Exercise 3.2.5 (INGInious: BST Serialization)#

Data structure serialization refers to the process of converting a data structure (such as a list, tree, or graph) into a format that can be stored or transmitted and then reconstructed (deserialized) later. Here, we are interested in reconstructing (deserializing) a BST that has been serialized using a preorder traversal.

Implement the reconstruction of a BST from the preorder traversal: Preorder reconstruction

Exercise 3.2.6 (INGInious: BirthdayMap)#

An easy exercise to efficiently query persons by their birthday (exam 2023): BirthdayMap

Exercise 3.2.7 (INGInious: Skyline)#

Design an efficient algorithm to compute the Skyline from a set of building shapes (rectangles) that can overlap.

Exercise 3.2.8 (INGInious: Array BST, put and get)#

Special implementation of a binary search tree with ArrayLists (mid-term quiz 2022). ArrayBST put and get

Exercise 3.2.9 (INGInious: Array BST, delete)#

Implementation of the delete method in our array-based implementation of a BST (mid-term quiz 2023). ArrayBST with delete