search trees

ARIZONA STATE UNIVERSITY

CSE 310, All Sections — Data Structures and Algorithms — Spring

2016

Assignment #4

Available Tuesday, 03/15/2016; due Tuesday, 03/29/2016

This assignment covers Chapters 12–13 (BSTs and their balanced variants) and Chapter 15 (dynamic pro- gramming) of the text [100 marks total].

1. Traversals of BSTs. [5 marks total; 1 mark each] Suppose that we have numbers between 1 and 1000 in a binary search tree (BST), and we want to search for the number 363. For each of the following sequences, is it a valid sequence of nodes examined? How can you tell?

(a) 2, 252, 401, 398, 330, 344, 397, 363.

(b) 924, 220, 911, 244, 898, 258, 362, 363.

(c) 925, 202, 911, 240, 912, 245, 363.

(d) 2, 399, 387, 219, 266, 382, 381, 278, 363.

(e) 935, 278, 347, 621, 299, 392, 358, 363.

2. Operations on BSTs. [10 marks total; 5 marks each]

(a) Write a recursive function that returns the minimum key value in a binary search tree of distinct (positive) integers. Return -1 in case the tree is empty.

(b) Write a recursive function that returns the predecessor of the key value k in a binary search tree of distinct (positive) integers. This is the key value that precedes k in an inorder traversal of the tree. If k does not exist, or if k has no predecessor, your function should return -1.

3. Properties of BSTs. [10 marks total; 5 marks each]

(a) Professor Bunyan thinks he has discovered a remarkable property of BSTs. Suppose that the search for key value k in a BST ends up in a leaf. Consider three sets: A, the keys to the left of the search path; B, the keys on the search path; and C, the keys to the right of the search path. Professor Bunyan claims that any three keys a 2 A, b 2 B, and c 2 C must satisfy a  b  c. Give a smallest possible counterexample to the professor’s claim.

(b) Show that if a node in a BST has two children, then its successor has no left child, and its predecessor has no right child.

4. AVL Trees. [10 marks total; 5 marks each] An AVL tree is a BST in which the balance factor of every node, which is defined as the di↵erence between the heights of the node’s left and right subtrees, is either 0, or +1, or -1. In Figure 1, only the tree in part (a) is an AVL tree; (b) has two nodes (4 and 6) that violate the balance requirement; (c) is not a binary search tree because 2 is in the right subtree of 3, and 7 is in the left subtree of 6.

(a) For a n = 1, 2, 3, 4, and 5, draw all the binary trees with n nodes that satisfy the balance require- ment of AVL trees.

(b) Draw a binary tree of height 4 that can be an AVL tree and has the smallest number of nodes among all such trees.

5. Red-Black Trees. [15 marks total] Show the red-black trees that result after successively inserting the keys 41, 38, 31, 12, 19, 8 into an initially empty red-black tree. Show your work!

1

(a smallest BST and its search)

(It needs to be a BST.)

i.e., Show your tree after each insertion.

Exercises 6.3

1. Which of the following binary trees are AVL trees?

5

3

2

6

8

5

4

2

6

8

5

3

1 2

6

97

( a )

1 3 7 9

( b ) ( c )

2. a. For q = 1>2>3>4> and 5, draw all the binary trees with q nodes that satisfy the balance requirement of AVL trees.

b. Draw a binary tree of height 4 that can be an AVL tree and has

the smallest number of nodes among all such trees.

3. Draw diagrams of the single L-rotation and of the double RL-rotation in their general form.

4. For each of the following lists, construct an AVL tree by inserting their

elements successively, starting with the empty tree.

a. 1, 2, 3, 4, 5, 6

b. 6, 5, 4, 3, 2, 1

c. 3, 6, 5, 1, 2, 4

5. a. For an AVL tree containing real numbers, design an algorithm for

computing the range (i.e., the difference between the largest and smallest numbers in the tree) and determine its worst-case efficiency.

b.B True or false: The smallest and the largest keys in an AVL tree can always be found on either the last level or the next-to-last level?

6. Write a program for constructing an AVL tree for a given list of q distinct integers.

7. a. Construct a 2-3 tree for the list C, O, M, P, U, T, I, N, G. Use the

alphabetical order of the letters and insert them successively starting with

the empty tree.

b. Assuming that the probabilities of searching for each of the keys (i.e.,

the letters) are the same, find the largest number and the average number of key comparisons for successful searches in this tree.

23

Figure 1: Only the tree in (a) is an AVL tree.

6. B+-Trees. [10 marks; 5 marks each] In the B+-tree we consider here, all keys are stored at the leaves, in increasing order of key value. The intermediate nodes are used for indexing. Specifically, each interior node contains m � 1 ordered keys k1 < . . . < km�1 assumed for simplicity to be distinct. The keys are interposed with m pointers to the node’s children so that all the keys in subtree T0 are smaller than k1, all the keys in subtree T1 are greater than or equal to k1 and smaller than k2 (with k1 being equal to the smallest key in T1), and so on through the last subtree Tm�1 whose keys are greater than or equal to km�1 with km�1 being equal to the smallest key in Tm�1.

A B+-tree of order m � 2 satisfies the following structural properties:

• The root is either a leaf or has between 2 and m children. • Each node, except for the root and the leaves, has between dm/2e and m children (and hence between dm/2e � 1 and m � 1 keys).

• The tree is (perfectly) balanced; i.e., all its leaves are at the same level.

Figure 2 shows an example of a B+-tree of order 4.

3. If the tree’s root is stored in main memory, the number of disk accesses will be equal to the number of the levels minus 1, which is exactly the height of the tree. So, we need to find the smallest value of the order p so that the height of the B-tree with q = 108 keys does not exceed 3. Using the upper bound of the B-tree’s height, we obtain the following inequality

blogdp@2e q +1

4 c+1 ≤ 3 or blogdp@2e

q +1

4 c ≤ 2=

By “trial and error,” we can find that the smallest value of p that satisfies this inequality is 585.

4. Since there is enough room for 30 in the leaf for it, the resulting B-tree will look as follows

11 15

4, 7,10 11, 14 15, 16, 19

40.25 34

20, 24 25, 28, 30 34, 38

60

51, 55 60, 68, 8040, 43, 46

20 51

Inserting 31 will require the leaf’s split and then its parent’s split:

11 15

4, 7,10 11, 14 15, 16, 19

25 30

20, 24 25, 28 34, 38

60

51, 55 60, 68, 8040, 43, 46

5120 34

30, 31

34 40

5. Starting at the root, follow the chain of the rightmost pointers to the (rightmost) leaf. The largest key is the last key in that leaf.

6. a. Constructing a top-down 2-3-4 tree by inserting the following list of keys in the initially empty tree:

10, 6, 15, 31, 20, 27, 50, 44, 18.

24

Figure 2: A B+-tree of order 4.

(a) State two major di↵erences of B-trees compared to other balanced BSTs.

(b) An upper bounds on the height h of a B+-tree of order m with n nodes is: h  blogdm/2e n+1 4

c+1. Use this to find the minimum order of the B+-tree that guarantees that the number of disk accesses in searching a file of 100 million records does not exceed 3. Assume that the root’s page is stored in main memory.

7. Binomial Coe�cients. [15 marks; 5 marks each] You may recall that the binomial coe�cient, denoted C(n, k) or

� n k

� , is the number of combinations

2

(subsets) of k elements from an n-element set (0  k  n). The name “binomial coe�cients” comes from the participation of these numbers in the binomial formula:

(a + b) n = C(n, 0)an + . . . + C(n, k)an�kbk + . . . + C(n, n)bn.

Of the numerous properties of binomial coe�cients, we focus on two:

C(n, k) = C(n � 1, k � 1) + C(n � 1, k) for n > k > 0 C(n, 0) = C(n, n) = 1

(a) Give pseudocode for a dynamic programming algorithm to compute C(n, k) that uses only addi- tions. [5 marks]

(b) What is the time and space e�ciency of your algorithm? [5 marks]

(c) Find the exact number of additions made by your algorithm, i.e., set up an expression A(n, k) counting the total number of additions made by your algorithm in computing C(n, k) and solve it exactly. [5 marks]

8. The Coin Collection Problem. [25 marks] In the coin collection problem, coins are placed in cells of an n ⇥ m board, with no more than one coin per cell. A robot, located in the upper left cell, position (1, 1), of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell (position (n, m)). In each step, the robot can move either one cell to the right or one cell down from its current location. When the robot visits a cell with a coin, it always picks up the coin located there.

(a) Give pseudocode for a dynamic programming algorithm to find the maximum number of coins the robot can collect and a path it needs to follow in solving the coin collection problem. Analyze the time and space requirements of your algorithm. [10 marks]

(b) Now, modify the dynamic programming algorithm in part (a) for the case where some cells on the board are inaccessible to the robot. Are there any changes to the time or space requirements of your algorithm? [5 marks]

(c) Apply your algorithm to the board in Figure 3, where the inaccessible cells are marked by X’s. [5 marks]

(d) How many optimal paths are there for the board in Figure 3? [5 marks]

This file contains the exercises, hints, and solutions for Chapter 8 of the book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by

A. Levitin. The problems that might be challenging for at least some students

are marked by B; those that might be difficult for a majority of students are marked by I =

Exercises 8.1

1. Whatdoesdynamicprogramminghave incommonwithdivide-and-conquer?

What is a principal difference between them?

2. Solve the instance 5, 1, 2, 10, 6 of the coin-row problem.

3. a. Show that the time efficiency of solving the coin-row problem by straightforward application of recurrence (8.3) is exponential.

b. Show that the time efficiency of solving the coin-row problem by ex- haustive search is at least exponential.

4. Apply the dynamic programming algorithm to find all the solutions to the change-making problem for the denominations 1, 3, 5 and the amount

q = 9=

5. How would you modify the dynamic programming algorithm for the coin-

collecting problem if some cells on the board are inaccessible for the robot?

Apply your algorithm to the board below, where the inaccessible cells are

shown by X’s. How many optimal paths are there for this board?

6. B Rod-cutting problem Design a dynamic programming algorithm for the following problem. Find the maximum total sale price that can be

obtained by cutting a rod of q units long into integer-length pieces if the sale price of a piece l units long is sl for l = 1>2> ===>q= What are the time and space efficiencies of your algorithm?

1

Figure 3: An 5 ⇥ 6 board for the coin collection problem, Question 8, parts (c) and (d).

3

(State the maximum number of coins and a path the robot needs to follow to collect them.)

for all integers n >=0 , for all integers n >=0