Homework: Trees

   < Previous  Next >
Write your answers to the following questions in a flat text file hwkTrees.txt (not a Word document nor a Rich Text Format file):
  1. Binary Search Trees:
    1. Given an empty BST, insert the numbers 10, 5, 8, 7, 6, 9, 4, 3. Write the following traversals of the resulting tree:
      1. Pre-order Traversal
      2. In-order Traversal
      3. Post-order Traversal
      Pre-order Traversal: 
In-order Traversal: 
Post-order Traversal:
    2. Delete the following numbers from the BST: 7, 9 then 6. Write the pre-order traversal of the resulting tree.
    3. Using only BSTs, how can we make a copy of a BST and restore it so that it's in the exact same order as the original? (Hint: Think about tree traversal(s))
    4. How can we make a copy of a BST and restore it so that it's balanced?
  2. AVL Trees
    1. Given an empty AVL tree, insert the numbers 10, 5, 8, 7, 6, 9, 4, 3. For each insertion, indicate which (if any) AVL rotation was performed (see the example below). Record the pre-order traversal of the resulting tree. 
      Insert 10: No rotation
Insert 5:  No rotation
Insert 8:  Left Right
...
Pre-order Traversal:
    2. Delete the following numbers from the AVL tree: 7, 9 then 6. For each deletion, indicate which rotation was performed (if any). Record the pre-order traversal of the resulting tree.
  3. Splay Trees
    1. Given an empty Splay tree, insert the numbers 6, 4, 5, 3, 2. For each insertion, indicate which splaying was performed. Record the pre-order traversal of the resulting tree.
    2. Retrieve the following numbers from the Splay tree: 4, 3. For each retrieve, indicate which splaying was performed. Record the pre-order traversal of the resulting tree.
  4. For the following scenarios, choose the most appropriate tree structure to use among the following choices: binary tree, BST, AVL tree, Splay tree, and justify your choice:
    1. An emergency call center that needs to quickly retrieve arbitrary addresses
    2. A grocery store inventory system
    3. A sports or concert ticket sales system that stores events. It is very common for many of the queries (in a short amount of time) to be for the same event.
  5. Complete the following table for the minimum height required to store the specified number of Sequence objects:
    Number of objects BST B-Tree (with 4 children) B-Tree (with 512 children)
    10      
    100      
    1000      
    10000      

Submission

Submit your txt file at https://3110.cs.mtsu.edu/. For further instructions, please see the Miscellaneous page.

Rubric:

Points         Question
------------   --------------------------------------------------------------
_____ /  2     1A BSTs: Insertion
_____ /  2     1B BSTs: Deletion
_____ /  2     1C BSTs: Restored
_____ /  2     1D BSTs: Balanced
_____ /  3     2A AVL Trees: (Rotations: 1 point; traversal: 2 points)
_____ /  2     2B AVL Trees: (Rotations: 1 point; traversal: 1 point)
_____ /  2     3A Splay Trees: (Rotations: 1 point; traversal: 1 point)
_____ /  2     3B Splay Trees: (Rotations: 1 point; traversal: 1 point)
_____ /  1.5   4 Scenarios
_____ /  3     5 Minimum Number Nodes

_____ / 21.5   Total