.jpg)
Trees
Table of Contents
.png)
Session 3 (lecture): Trees (II)
.png)
Slides
-trans.png)
Readings
-
Data Structures and Problem Solving Using Java by Mark A. Weiss: chapter 18 on Priority Queues and Binary Heaps
-
Data Structures and Algorithms in Java by Michael T. Goodrich and Roberto Tamassia (4th edition): section 6.3 on Heaps
.png)
Homework
Recap
Review the contents of the class and read the recommended bibliography.
Exercise
Implement the insertion algortithm for binary search trees.
Question
Given two Binary Search Trees, tree1 and tree2, each of which is built inserting, with the previously implemented method, 10,000 Integer objects with values ranging from 1 to 10,000:
-
tree1: calling the insertion method with the values in increasing order
-
tree2: calling the insertion method with the values in random order
In general, which of the two trees will be more efficient for searching any given element?
Exercise
Implement the deletion algorithm for a binary heap.
Question
Let's set a priority queue implemented with a heap, using the priority as the criterion for ordering the elements. Can it be ensured that two elements with equal priority will be recovered in the same order as they entered the priority queue (as they should be)? If not, how could it be fixed?
Preparing the lab session
Read the exercises proposed for the lab session.
.png)
Additional Resources
-
Binary Heap Applet by Kubo Kovac. It also shows interactive animations of other tree-based data structures, like Binary Search Trees.