Homework 3

CS409 - Spring 2000

Due: Thursday, Feb 17

1. (10 pts) Suppose we wish to insert the keys A L G O R I T H M F U N into a Dictionary.  The keys are presented for insertion in the order given and are stored in alphabetical order within the Dictionary.
   1. Show the resulting Binary Search Tree (BST).
   2. Show the resulting 234-Tree.

    

2. (15 pts)  
   1. Show all the legal BSTs that can be made using the elements A, B, and C.  Note that for a tree to be legal it must satisfy the BST Property (i.e., the elements must remain in correct alphabetical order within the tree).
   2. How many different, legal BSTs can be made using the elements A, B, C, D, and E?  Show your work. Hint: You should be able to answer this question without listing all the trees.  Start by determining the number 4-node trees through use of your knowledge of the number of 1-, 2-, and 3-node trees.
   3. Show all the legal 234-Trees that can be made using the elements A, B, C, D, and E.

    

3. (5 pts) For a BST, is delete commutative?  In other words, if we delete x then y, do we always get the same answer as when we delete y then x?  Either argue that delete is commutative or give a counterexample.

    

4. (10 pts) Suppose we design a BST that contains some extra information at each node: each node will contain a field showing the number of items held within the corresponding subtree.
   1. Briefly explain how this information can be kept up-to-date when a new item is inserted.
   2. Briefly explain how this information can be used to do selection.  [Select(k) is meant to return the k-th smallest item that is currently in the Dictionary.  For example, Select(1) should return the smallest item and Select(n/2), where n is the number of items in the Dictionary, should return the median item.]