Test 3 Study Guide

Tests in this course may contain any material covered in lecture up until this point, although much stronger emphasis will be placed on material for which you have received graded feedback. This page contains a collection of exercises that you may wish to complete to prepare yourself for the test. Note that you do not need to complete all of the offered exercises. More questions appear here than will appear on your test.

Standard 3A. Demonstrate an ability to properly perform proof by induction

You should be prepared to give inductive proofs for simple mathematical summations.

  1. Prove by induction that \(\sum\limits_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}\).

    2. Proof

  2. Prove by induction that \(\sum\limits_{i=0}^{n} 2^i = 2^{n+1} - 1\).

    3. Proof

Standard 3B. Demonstrate an understanding of how binary search trees function

  1. Define the following terms with respect to tree data structures:

    1. Leaf

      A leaf is a node in a tree that has no children.

    2. Height

      The height of a tree is the number of levels below the root, or the number of edges in the longest path from the root to a leaf, or one less than the number of levels in the tree.

    3. Binary tree

      A binary tree is a tree for which each node has at most one left child and at most one right child.

    4. Binary search tree

      A binary search tree is a binary tree in which, for each node, all keys in the left subtree are less than the node’s key and all keys in the right subtree are greater than the node’s key.

    5. AVL tree

      An AVL tree is a binary search tree in which, for every node, the height of the left subtree and the height of the right subtree differ by no more than one.

  2. Show the BST that would result from inserting the following keys into an initially empty tree: 12, 8, 5, 17, 1, 9, 22.

    1 5 9 8 22 17 12

  3. Is this the only BST that could contain these keys? If not, give at least one example of another BST that holds these same keys. If so, explain why the resulting BST is unique.

    No, this is not the only BST that could hold these keys. For example: if the keys were inserted in sorted order from 1 through 22, then the tree would be a long line of right branches with 1 at the root and 22 as the only leaf.

  4. Is the following tree a BST? If not, why not?

    1 7 4 17 12 29 30 20 10

    This is not a BST. The key 29 is to the right of the key 30, which violates the BST invariant.

  5. If we tried to find the key 22 in the following tree, where would it have to be?

    12 17 15 44 23 87 99 90 50

    If the key 22 were in this BST, it would have to be to the right of the key 17.

Standard 3c. Demonstrate an understanding of how balanced BSTs function

  1. Draw a diagram showing the "rotate left" operation on binary trees. When is it impossible to rotate a binary tree to the left?

    X Y Z b a

    →
    X Y a Z b

    It is only possible to perform left rotation if the root has a right child; a binary tree with no right child of the root cannot be left-rotated.

  2. Consider the following tree:

    2 5 4 10 9 6 13 16 14 19 17 12

    1. Write the heights of each node for the tree above.

      Writing the height of each node above the node itself, we have:

      2 0 5 0 4 1 10 0 9 1 6 2 13 0 16 0 14 1 19 0 17 2 12 3

    2. Consider the addition of the value 1 to the above tree. Which nodes' heights change?

      The heights down the leftmost spine of the tree change.

    3. What will the tree look like after the value 1 is inserted?

      We show the insertion of 1 and the updated heights as follows:

      1 0 2 1 5 0 4 2 10 0 9 1 6 3 13 0 16 0 14 1 19 0 17 2 12 4

    4. What will the tree look like after the value 15 is inserted into the original tree?

      The insertion of 15 into the original tree is drawn below. Note that a rebalancing is necessary because 17 was out of balance after 15 was added.

      2 5 4 10 9 6 13 15 14 19 17 16 12

    5. What will the tree look like after the value 5 is deleted from the original tree?

      The removal of 5 from the original tree is drawn below.

      2 4 10 9 6 13 16 14 19 17 12

    6. What will the tree look like after the value 9 is deleted from the original tree?

      The removal of 9 from the original tree is drawn below.

      2 5 4 10 6 13 16 14 19 17 12

    7. What will the tree look like after the value 6 is deleted from the original tree?

      The removal of 6 from the original tree is drawn below. Note that this is one of two options for how we might remove 6 from the original tree.

      2 4 10 9 5 13 16 14 19 17 12

    8. What will the tree look like after the value 19 is deleted from the original tree?

      The removal of 19 from the original tree is drawn below. After 19 was removed, 17 was out of balance and was rotated right.

      2 5 4 10 9 6 13 16 17 14 12

Standard 3D. Demonstrate an understanding of how heaps function

  1. Define the following terms with respect to heap data structures:

    1. Complete binary tree

      A complete binary tree is a binary tree in which all levels are full except the last, where all nodes are packed to the left and all empty spaces are packed to the right.

    2. Max-heap

      A max-heap is a complete binary tree in which every node’s prioiry is greater than or equal to the priorities of its children.

  2. What is the difference between a queue and a priority queue?

    A priority queue has a priority type as well as an element type. When elements are enqueued into a priority queue, they are paired with a priority (in contrast to a queue, which simply requires the element). In a queue, elements are dequeued in the order that they are enqueued; in a priority queue, they are dequeued in an order based upon their associated priorities.

  3. Consider the following lists of numbers. Write each as a complete binary tree by building the tree in level-order from the array values, and then use the heapify algorithm that we used in class to transform it into a heap.

    1. [2, 3, 9, 3, 6, 2]

      Here is the array as a complete tree:

      3 6 3 2 9 2

      Here is the complete tree after heapify:

      3 3 6 2 2 9

    2. [11, 4, 4, 3, 4, 6, 9, 10, 2]

      Here is the array as a complete tree:

      10 2 3 4 4 6 9 4 11

      Here is the complete tree after heapify:

      3 2 4 4 10 6 4 9 11

  4. Is the following statement true or false? If true, give a justification. If false, give a counterexample. "All BSTs are heaps."

    The statement that "all BSTs are heaps" is false. The following BST is a counter-example.

    3 5 4

    This binary tree is a BST because 3 < 4 (left subtree data are smaller) and 5 > 4 (right subtree data are larger). But it is not a max-heap because 4 < 5 and, in a max-heap, all parents must have a priority greater than or equal to the priority of their children. A similar argument shows that this is also not a min-heap.

  5. Give pseudocode for the heapify heap algorithm to turn these complete binary trees into heaps. Briefly explain why this algorithm is \(O(n)\).

    Method heapify()
  For index <- contents.size-1 Down To 0 Do
    bubbleDown(index)
  EndFor
End Function

    This algorithm is \(O(n)\) because, although the loop runs \(O(n)\) times and bubbleDown takes \(O(\log n)\) worst-case time, most bubbleDown operations are small — that is, most nodes are closer to the leaves of the tree rather than the root. As a result, the overall number of actual swaps that occurs is \(O(n)\).