Version: 0.3.38

Trees#

Module:

Trees

Git Repository:

Lab 04—Trees

Objectives:

  • Understand the general concept of tree

  • Understand how a binary search tree works

  • Understand how a heap tree works

Caution

This is the second mandatory lab session. Organize yourself by groups of 2 to 3 students and write a short report, summarizing your answers. Here are some guidelines:

  • Justify every answer, especially calculations.

  • Do not exceed 8 pages

  • Do not attach a zip of your Java project

Submit your report, as a PDF file, on Blackboard by Friday October 27, 2023 at 23:30 at the latest.

Binary Search Tree (BST)#

Here we focus on the Binary search trees. For the questions that relate to programming, chec out the file BST.java.

Exercise (2 points)

Starting with an empty binary search tree, insert the keys A, L, P, D, R, E, I, and X (in this very order). Assume keys compare one another alphabetically (i.e. A < B < C < … ). Draw the tree after every insertion.

Exercise (1 point)

Consider the tree resulting from the previous question and delete the keys X, A, and L (in this very order). Draw the tree after every deletion.

Exercise (3 points)

Consider inserting the items A, B, and C in an empty BST.

  1. What are all the possible ways (i.e., orderings) to insert these three keys into a BST when done randomly?

  2. What are the possible tree “shapes” resulting from the insertion orders you have listed in the previous question.

  3. What can you say about the probability these various tree shapes? Have all tree shape the same probability?

  4. If we generalize to inserting \(n\), what can you conclude about the probability of obtaining specific tree shapes?

Exercise (2 points)

Implement the insert operation, which insert a new item into the tree.

Exercise (1 point)

Implement the size operation, which returns the number of items in a BST.

Exercise (2 points)

Implement the minimum and maximum operations, which returns the smallest and the largest item inserted in the tree, respectively.

Exercise (1 point)

Implement the operation format(), which converts the tree into a string with all the items listed in ascending order, separated by commas. What type of tree traversal does that require?

Minimum Binary Heap#

We look here at how one can implement a minimum heap in Java.

Exercise (1 point)

Look at the Heap class provided and implement the insert operation.

Exercise (1 point)

Implement the takeMinimum, we removes and returns the minimum of the heap.

Exercise (2 points)

How many elements does a binary heap of height h have at least? How many at most? (only a root has height 0)

Exercise (1 point)

Where can the second-smallest element be in a min-binary heap? What about the third-smallest? In general, give a rule at which level the k-smallest element in a binary heap with n elements could be. (you can assume a heap of an arbitrary size \(n = 2t − 1\) with \(t \in N\), the root is at level 0).

Exercise (2 point)

Implement the decreaseKey(i, k), which set the element at position i to the value k and restore the heap property. It throws an error if k is greater or equal to the element stored at position i.