Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Fall 22: CSci 5421—Advanced Algorithms and Data Structures

Homework 5

1. (12 points) Consider the routine  Tree delete  discussed in class (not the one in the text) for deleting items from a binary search tree T.   (See  11/07/22 slides.)   Suppose that an external application (e.g., a database) uses T as a data structure and stores pointers to each node of T.

Consider a node y in T and suppose that Tree delete(T, z) is called, where z is the in-order prede- cessor of y .

(a) Explain carefully what problem might potentially arise in this set-up.

(b) Rewrite the routine Tree delete from the slides to avoid this problem.  (Only a few modifica-tions are needed.)

Note: You have no access to the external application or its pointers. Work solely with T.

2. (12 points) Let T be an n-node binary search tree of height h.  Let k be some integer, where 0 < k < n. Suppose that we start at some node of T and make k calls, back-to-back, to the successor routine Tree succ .  (See 11/07/22 slides.)  The calls are back-to-back in the sense that each call, after the rst, is made from the node where the previous call terminates.   (So if  Tree succ(北) terminates at node y—the successor of 北—then the next call is Tree succ(y). And so on.)

We wish to prove that the total time taken for all k calls is O(k + h), no matter which node of T we start at.  We do this by classifying the edges traversed by the k calls into different types and upper-bounding the number of edges of each type, which implies the O(k + h) bound.

A left branch in T is an edge joining a node to its left child and a right branch is an edge joining a node to its right child.  An upward traversal of a branch happens when a parent is visited from a child and a downward traversal happens when a child is visited from a parent.  It is easy to see that during the k calls, a left or a right branch is traversed only downwards or only upwards, or both, and this happens at most once.  (You do not have to prove this but convince yourself of it.) Give careful answers for the each of the following:

(a) Prove that the total number of right branches traversed only downwards and left branches traversed only upwards, during the k calls, is upper-bounded by k .

(b) Prove that the total number of right branches traversed only upwards and left branches traversed only downwards, during the k calls, is upper-bounded by h.

(c) Prove that the total number of branches (left and right) traversed both upwards and down- wards, during the k calls, is upper-bounded by min{k, h}.

Note: A time bound of O(kh) is easy to establish but is not of interest in this problem (and will earn no credit).

3. (12 points) In class, we proved inductively that the height of a red-black tree, T, with n internal nodes is at most 2 log(n + 1). We now explore a different approach to proving this.

(a) Let L (resp.  S) be a path in T from the root to an external node with the largest (resp. smallest) number of edges. Let é (resp. s) be the number of edges in L (resp. S). Prove that é < 2s.

(b) Let n\  be the number of internal nodes in T that are at most s - 1 edges away from the root. Derive an expression for n\ .

(c) From parts (a) and (b) obtain the desired upper bound of 2 log(n + 1) on the height of T.

4. (10 points) Let T be a red-black tree formed by inserting n keys, one after the other, via the routine RB insert  into an initially-empty tree.  Prove that if n > 1, then T has at least one red node.

Give a careful proof that considers the effect of the various cases that can arise during insertion as well as the effect of the nal recoloring of the root (if any).

5. (16 points) Problem 13-2, p. 332-333 (about Join” operations on red-black trees).

Answer concisely the question posed in each part.  (Skip part (e) as it is symmetric to part (b).)   Supplement your answers for parts (a), (b), and (c) with suitable short pseudocode fragments  (not full-blown, read-to-run code).