Round 3: Trees

We have already seen trees many times:

• ​ Recursion trees in the CS-A1120 Programming 2 course and in this course.

• ​ “Parse trees” of formulas in the form of object diagrams in the “Expressions” part of the recursion round of CS-A1120 Programming 2.

• ​ And so on…

Example

A call tree of the quicksort algorithm:

Example

An object diagram for the parse tree of the expression \(-(2.0 x + y)\):

Trees are indeed a very common concept and data structure in computer science. In this round, we’ll take a closer look at trees

1. mathematically, and

2. as an underlying data structure for other data structures and algorithms.

For the second point above, we’ll see how to

• ​ implement priority queues with heaps, which are trees having some special properties, and

• ​ handle disjoint sets with union operations by using trees.

Trees are further discussed and used in following rounds as well.

Contents:

• Basic definitions
• Traversing trees
• Priority queues with binary heaps
• Disjoint-sets with the union-find data structure

Material in Introduction to Algorithms, 3rd ed. (online via Aalto lib):

• ​ Binary trees: Appendix B5

• ​ Representing trees: Section 10.4

• ​ Heaps: Chapter 6

• ​ Union-find: Chapter 21

Similar material elsewhere:

• ​ Union-find: Section 1.5 in Algorithms, 4th ed.

• ​ Heaps in the OpenDSA book

• ​ Union-find in the OpenDSA book

Some external links:

• ​ MIT 6.006 OCW video on heaps and heap sort