Exercises B¶
Note
You must complete these exercises by Wednesday of W7.
Faux c’est \(\mathcal{O}(1)\), si on a de la chance on tombe directement dessus.
Exercice 3.2.1 (True/False BinarySearch)¶
In the best case, the number of key comparisons for a binary search for a particular key in a sorted array of N distinct keys is \(\sim \log N\).
Exercice 3.2.2 (True/False BST)¶
Note: BST is understood here as the implementation of the book, 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 book.
We recommend that you first become familiar with the notions of tree traversals: infix, prefix and postfix.
Given the output of an infix 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 pseudo-code of an algorithm to do so, if not, give a counterexample that justifies your answer.
Given a the output of a prefix traversal of a BST containing \(N\) distinct keys. Is it possible to reconstruct the shape of the BST based on the result of the walk? If so, write the pseudo-code of an algorithm to do so, if not, give a counterexample that justifies your answer.
Given an ordered tree of \(N\) distinct keys and a \(x\) key, is it possible to find the smallest key strictly larger 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 tree on the right of \(x\).
Exercice 3.2.3 (True/False Redblack Trees)¶
For the statements related to red-black trees, we advise you to first translate it into a statement into 2-3 trees as there is a one-to-one mapping between the two representation. In most cases, it is easier to answer on 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\)
For the insertion of N keys in ascending order into an initially empty red-black BST. The number of color changes of the last insertion is at most 3. The number of changes is understood to be the sum of the absolute value differences between the number of reds after insertion minus the number of reds before insertion.
A red-black BST obtained after inserting \(N > 1\) keys into an initially empty tree has 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 in each path from the root to a null link) is maximum \(log 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 for deleting the key 5 from the BST depitected below with the implementation of the text book?
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)¶
Impement a method which returns the least key strictly greater than a given key: Higher key
Exercise 3.2.6 (Inginious)¶
Implement the reconstruction of a BST from the preorder traversal: Preorder reconstruction
Exercise 3.2.7 (Inginious)¶
Implement the get/put operations of a BST with an array-based data-structure instead of linked nodes: ArrayBST
Exercise 3.2.8 (Inginious)¶
An easy one to query efficiently persons by their Birthday (exam 2023) BirthdayMap
