Homework 3 Solution

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.
    BST 234-Tree 
          A 
       \ 
        L 
      /   \ 
     G     O 
    / \   / \ 
   F   I M   R 
      /   \   \ 
     H     N   T 
                \ 
                 U 
           I
     /   \
   G       O
 /  \     /  \
AF   H  LMN  RTU

    2.  

  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).
      A
 \
  B
   \
    C
      		 
      A
 \
  B
 /
C
      		 
        B
 / \
A   C
      		 
          C
   /
  B
 /
A
      		 
        C
 /
A
 \
  B
    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.
      A 4-node tree can have either 3 nodes on the left (in the left subtree) and 0 on the right ( in the right subtree), 2 nodes on the left and 1 on the right, 1 node on the left and 2 on the right, or 0 nodes on the left and 3 on the right.  There are 5 different 3-node trees and 2 different 2-node trees.  Adding these up, we get 5+2+2+5 = 14 4-node trees.  Similar reasoning can be used to determine the number of 5-node trees:
      14 trees of the form (4,0) [i.e., 4 in the left subtree and 0 in the right subtree]
      5 trees of the form (3,1)
      4 trees of the form (2,2) [There are two possible subtrees on each side; these are multiplied]
      5 trees of the form (1,3)
      14 trees of the form (0,4)
      Thus there are 42 possible 5-node trees.
    3. Show all the legal 234-Trees that can be made using the elements A, B, C, D, and E. 
        B
 / \
A   CDE
      		 
         C
  / \
AB   DE
      		 
          D
   / \
ABC   E
      		 
        B D
 / | \
A  C  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.
    Delete is not commutative.  The example below uses the rule that deletion of a node with two children is done by deleting its successor.
    Delete A, then B 
      A
 / \
B   D
   /
  C
    		 
      C
 / \
B   D
    		 
    C
 \
  D
    Delete B, then A 
      A
 / \
B   D
   /
  C
    		 
    A
 \
  D
 /
C
    		 
      D
 /
C

     

  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.
      When a new item is inserted, every node on the path from the root to the new leaf has its counter increased by one (because each of these subtrees has one more item in it than it did before).
    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.]
      This can be done using a simple recursive procedure.  First, determine how many items are in the left subtree of the root.  Call this number j.
      If k = j+1 then the root contains the desired item.
      If k < j+1 then the desired item is the k-th item in the left subtree.
      If k > j+1 then the desired item is the (k-1-j)th item in the right subtree.