Tutorial 14, CPSC 331, Winter 2017

home page -  news -  syllabus -  schedule -  assignments -  tutorials -  java -  references -  Mike Jacobson

Tutorial 1 -  Tutorial 2 -  Tutorial 3 -  Tutorial 4 -  Tutorial 5 -  Tutorial 6 -  Tutorial 7 -  Tutorial 8 -  Tutorial 9 -  Tutorial 10 -  Tutorial 11 -  Tutorial 12 -  Tutorial 13 -  Tutorial 14 -  Tutorial 15 -  Tutorial 16 -  Tutorial 17 -  Tutorial 18 -  Tutorial 19 -  Tutorial 20 -  Tutorial 21 -  Tutorial 22 -  Tutorial 23 -  Tutorial 24

 Binary Search Trees

About This Exercise

This exercise can be used by students to make sure that they are familiar with the properties, implementations, and applications of trees, binary trees, and binary search trees. Students should read through and try to solve the problems on this exercise before attending the tutorial.

Expected Background

It is expected that students have attended the lectures in which the above kinds of trees were discussed and have carefully reviewed the online lecture notes that are available. The supplementary information about operations on binary search trees that is now available will also be useful.

Warmup Exercises — To Check That You Understand the Basics

It is to be expected that all of the questions in this first section can be answered by any student who has successfully completed the prerequisites for this course, attended the lectures in which trees were discussed, and read through the material about this that is listed above.

Teaching assistants will not be spending very much time in tutorials discussing these questions! Students should look at them anyway to make sure that they know how to answer them.

Students who do have difficulty with these questions, after completing the suggested reading, should contact the course instructor to get extra help.

  1. Consider the following binary tree.

    Binary Tree

    1. Which node is the root of this tree?
    2. What is the size of this tree?
    3. What is the height of this tree?
    4. Which nodes are ancestors of the node with label d?
    5. Which nodes are proper ancestors of the node with label d?
    6. Which nodes are descendants of the node with label d?
    7. Which nodes are proper descendants of the node with label d?
    8. Which nodes are siblings of the node with label d?
    9. Which nodes are children of the node with label d?
    10. What is the depth of the node with label d?
    11. Which of the nodes of this tree are internal nodes?
    12. Which of the nodes of this tree are leaves?

  2. How are the size and depth of an arbitrary binary tree related?

  3. Consider the following binary search tree.

    A Binary Search Tree

    Draw the binary search trees that would be obtained if the following sequence of operations is performed.

    1. Insert 7
    2. Delete 6
    3. Insert 12
    4. Insert 1
    5. Insert 6
    6. Insert 5

  4. Repeat the above question, starting with the following binary search tree instead.

    Another Binary Search Tree

A Suggested Programming Exercise

  1. The algorithm for searching in a binary search tree that was presented in lectures uses “tail recursion:” it only calls itself once (if it does so at all) and this only happens at the end of its computation.

    Using this information, write a program that solves the same problem, as efficiently, without using recursion at all: Your algorithm should use a loop instead.

To Be Discussed in Tutorial

  1. Describe efficient recursive algorithms that can be used to compute the size as well as the height of a binary search tree that is given as input. Your algorithms should each use a number of steps that is at most linear in the size of the given binary search tree.

  2. Consider the following algorithm, which can be used to generate an ArrayList storing the same set of keys as a given binary search tree T, in increasing order.

    ArrayList<E> rInOrder(BST<E,V> T) { ArrayList<E> A = new ArrayList<E>(); if (T != null) { A.addAll(rInOrder(T.left)); A.add(T.key); A.addAll(rInOrder(T.right)); }; return(A); }

    It should be assumed, for the rest of this question, that the cost of addAll is the same as the cost to add each element of the ArrayList that is included its input using the method A.add, one element at a time.

    1. Sketch a proof that this algorithm is correct, that is, it always terminates, producing as output an ArrayList storing the same set of values as the given binary search tree T, with these values listed in increasing order in the ArrayList, and without changing the input tree.

    2. Let Steps(T) be the number of steps used by this algorithm on input T. Write a recurrence for Steps(T).

    3. Try to use your recurrence to prove that Steps(T) ∈ O(size(T) × height(T)).

    4. Now consider a value x stored in a node whose depth in T is a positive integer d. State (and justify) a lower bound for the number of copies of x that are written into ArrayLists’s when the above algorithm is executed on the input T.

    5. Here is a challenge problem: Show that in the worst case (that is, for some trees, of all possible sizes and depths)

      Steps(T) ∈ Ω(size(T) × height(T))

      as well.

    6. Here is another challenge problem: Prove that

      Steps(T) ∈ Ω(size(T) × log(size(T)))

      in the best case.

    7. Try to find asymptotic bounds on the amount of storage space (including space on the process stack) that is used, as well.

    8. Which algorithm for the inorder traversal of a binary search tree should be used when the input tree can be quite large — this one, or the one that is given in the lecture supplement? Why?

Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/Courses/cpsc331/W17/tutorials/tutorial14.html