Radix trees Given two strings a D a0a1 :::ap and b D b0b1

Binary search trees with equal keys Equal keys pose a problem for the implementation of binary search trees. a. What is the asymptotic performance of TREE-INSERT when used to insert n items with identical keys into an initially empty binary search tree? We propose to improve TREE-INSERT by testing before line 5 to determine whether :key D x:key and by testing before line 11 to determine whether :key D y:key. 304 Chapter 12 Binary Search Trees If equality holds, we implement one of the following strategies. For each strategy, find the asymptotic performance of inserting n items with identical keys into an initially empty binary search tree. (The strategies are described for line 5, in which we compare the keys of and x. Substitute y for x to arrive at the strategies for line 11.) b. Keep a boolean flag x:b at node x, and set x to either x:left or x:right based on the value of x:b, which alternates between FALSE and TRUE each time we visit x while inserting a node with the same key as x. c. Keep a list of nodes with equal keys at x, and insert into the list. d. Randomly set x to either x:left or x:right. (Give the worst-case performance and informally derive the expected running time.)

Radix trees Given two strings a D a0a1 :::ap and b D b0b1 :::bq, where each ai and each bj is in some ordered set of characters, we say that string a is lexicographically less than string b if either 1. there exists an integer j , where 0 j min.p; q/, such that ai D bi for all i D 0; 1; : : : ; j 1 and aj < bj , or 2. p< 10110 by rule 1 (letting j D 3) and 10100 < 101000 by rule 2. This ordering is similar to that used in English-language dictionaries. The radix tree data structure shown in Figure 12.5 stores the bit strings 1011, 10, 011, 100, and 0. When searching for a key a D a0a1 :::ap, we go left at a node of depth i if ai D 0 and right if ai D 1. Let S be a set of distinct bit strings whose lengths sum to n. Show how to use a radix tree to sort S lexicographically in .n/ time. For the example in Figure 12.5, the output of the sort should be the sequence 0, 011, 10, 100, 1011.

Average node depth in a randomly built binary search tree In this problem, we prove that the average depth of a node in a randomly built binary search tree with n nodes is O.lg n/. Although this result is weaker than that of Theorem 12.4, the technique we shall use reveals a surprising similarity between the building of a binary search tree and the execution of RANDOMIZEDQUICKSORT from Section 7.3. We define the total path length P .T / of a binary tree T as the sum, over all nodes x in T , of the depth of node x, which we denote by d.x; T /. Problems for Chapter 12 305 011 0 100 10 1011 0 1 1 0 1 01 1 Figure 12.5 A radix tree storing the bit strings 1011, 10, 011, 100, and 0. We can determine each nodes key by traversing the simple path from the root to that node. There is no need, therefore, to store the keys in the nodes; the keys appear here for illustrative purposes only. Nodes are heavily shaded if the keys corresponding to them are not in the tree; such nodes are present only to establish a path to other nodes. a. Argue that the average depth of a node in T is 1 n X x2T d.x; T / D 1 n P .T / : Thus, we wish to show that the expected value of P .T / is O.n lg n/. b. Let TL and TR denote the left and right subtrees of tree T , respectively. Argue that if T has n nodes, then P .T / D P .TL/ C P .TR/ C n 1 : c. Let P .n/ denote the average total path length of a randomly built binary search tree with n nodes. Show that P .n/ D 1 n Xn1 iD0 .P .i / C P .n i 1/ C n 1/ : d. Show how to rewrite P .n/ as P .n/ D 2 n Xn1 kD1 P .k/ C .n/ : e. Recalling the alternative analysis of the randomized version of quicksort given in Problem 7-3, conclude that P .n/ D O.n lg n/. 306 Chapter 12 Binary Search Trees At each recursive invocation of quicksort, we choose a random pivot element to partition the set of elements being sorted. Each node of a binary search tree partitions the set of elements that fall into the subtree rooted at that node. f. Describe an implementation of quicksort in which the comparisons to sort a set of elements are exactly the same as the comparisons to insert the elements into a binary search tree. (The order in which comparisons are made may differ, but the same comparisons must occur.)

Number of different binary trees Let bn denote the number of different binary trees with n nodes. In this problem, you will find a formula for bn, as well as an asymptotic estimate. a. Show that b0 D 1 and that, for n 1, bn D Xn1 kD0 bkbn1k : b. Referring to Problem 4-4 for the definition of a generating function, let B.x/ be the generating function B.x/ D X1 nD0 bnxn : Show that B.x/ D xB.x/2 C 1, and hence one way to express B.x/ in closed form is B.x/ D 1 2x 1 p 1 4x : T. The Taylor expansion of f .x/ around the point x D a is given by f .x/ D X1 kD0 f .k/.a/ k .x a/k ; where f .k/.x/ is the kth derivative of f evaluated at x. c. Show that bn D 1 n C 1 2n n ! (the nth Catalan number) by using the Taylor expansion of p1 4x around x D 0. (If you wish, instead of using the Taylor expansion, you may use the generalization of the binomial expansion (C.4) to nonintegral exponents n, where for any real number n and for any integer k, we interpret n k to be n.n 1/.n k C 1/=k if k 0, and 0 otherwise.) d. Show that bn D 4n p n3=2 .1 C O.1=n// :