Lab 6: Trees and Hash Tables

Task 1: Binary-tree basics

Consider the following binary tree in which the keys are letters:

1. What is the depth of node E? Of node A?

2. What is the height of the tree?

3. If a preorder traversal were used to print the keys, what would the output be?

4. What would be the output of an inorder traversal?

5. What would be the output of a postorder traversal?

6. What would be the output of a level-order traversal?

Task 2: Binary search trees

1. Insert the following sequence of keys into an initially empty binary search tree:

   15, 23, 20, 10, 13, 6, 18, 35, 9, 24
   

2. What does the tree look like after each of the following deletions, which are carried out in sequence:

   • delete 6
   • delete 15
   • delete 20

   Note: Students in the B1 lecture will cover the deletion algorithm in Friday’s lecture, and they are welcome to wait until after that lecture to try this part of Task 2.

Task 3: Balanced 2-3 trees

Recall that a binary tree is balanced if, for each of its nodes, the node’s subtrees have the same height or have heights that differ by 1. This is important because a balanced tree has a height of O(log n). Therefore, for a balanced binary search tree, the worst case for search, insert, and delete is O(h) = O(log n). Giving us the the best worst-case time complexity!

As discussed in lecture, a 2-3 tree is a search tree that is guaranteed to always be balanced, which ensures that all of the key operations will have a worst-case time complexity of O(log n), where n is the number of items in the tree.

1. Create a 2-3 tree from the following sequence of keys:

   45, 1, 25, 12, 26, 44, 4, 50, 43, 21
   

2. What does the tree look like after the following operations?

   • insert 5
   • insert 42

3. What items do I have to visit if I’m searching for an item with each of the following keys?

   • 44
   • 18

Task 4: Heap Trees, just the basics

Consider the following heap:

1. Which node would be in position 4 of the corresponding array?

2. Given the node in position 4, how could you use arithmetic to determine:

   • the position of its left child (if any) in the array
   • the position of its right child (if any) in the array
   • the position of its parent in the array

3. If we call the remove() method on this heap:

   • Which item will be removed?
   • Which item will be copied into the position of the removed item and then be sifted down to restore the heap?
   • What will the tree look like after this call to remove()?

4. What will the heap look like after a second call to remove()? After a third call?

5. After completing the three calls to remove(), we then use the insert() method to add an item with a key of 21. What will the tree look like after that insertion?

Task 5: Turn an array into a heap

1. Consider the following array:

   {5, 3, 12, 8, 7, 4, 6}
   

   Draw the corresponding complete tree.

2. Now turn the complete tree into a heap. Remember that you should start by sifting down the rightmost interior node in the corresponding array (or, to put in another way, the parent of the last item in the array).

Task 6: Trace heapsort

Heapsort begins by turning an array into a heap, and then it uses a sequence of heap removals to sort the array.

Each heap removal removes the largest remaining item from the heap, and the removed item is then placed in the correct position in the array – beginning with the rightmost position and working backwards from right to left.

In the prior task, you already turned an array into a heap. Now trace through the remaining steps that heapsort would take to sort that array, showing the state of the array after each new element is put into place.

Task 7: Review hash table basics

Consider the hash table shown below. Assume that:

• It was filled using the hash function from lecture:

  h(key) = key.charAt(0) - 'a'
  

  (In other words, the hash code of a key is the ASCII code of its first character minus the ASCII code of 'a'.)

• Collisions were resolved using linear probing.

• Gray cells are ones from which an item has been removed.

• White cells are ones in which an item has never been inserted.

• Occupied cells contain the key of their key-value pair.

1. Which item in the table has been inserted incorrectly? How can we be certain?

2. If we insert an item with a key of "ferret" into the table using linear probing, what is the probe sequence that would be used? (In other words, what sequence of positions would be considered by the insert() method to determine where the item should go?)

3. If we insert an item with a key of "ferret" into the table using linear probing, where would it end up?

Now consider the following hash table, which was filled using the same hash function but with quadratic probing.

4. If we insert an item with a key of "dolphin" into the table using quadratic probing, what is the probe sequence? Where would the item end up?

5. After inserting "dolphin", we now insert an item with a key of "ant" using quadratic probing. What is the probe sequence? Where would the item end up?

6. If this table were implemented using the same hash function but with separate chaining, what it would look like? Include both the original keys and the new ones ("dolphin" and "ant").