4. Trees and hierarchical orders

Before we proceed with looking at data structures for storing linearly ordered data, we must take a diversion to look at trees. At first glance, it appears as if trees are most appropriate for storing hierarchically ordered data; however, we will later see how trees can also be used to allow efficient storage of linearly ordered data, as well.

5. Ordered trees

A general tree is appropriate for storing hierarchical orders, where the relationship is between the parent and the children. There are many cases, however, where the tree data structure is more useful if there is a fixed number of identifiable children. This topic looks at binary trees as well as perfect and complete binary trees, N-ary trees, the concept of balance, binomial trees, and left-child right-sibling binary trees (a technique for storing general trees as binary trees).

6. Search trees

This topic looks at storing linearly ordered data in search trees. The focus is to ensure that operations on individual elements stored in the tree run in Θ(ln(-)) time.

7. Priority queues

A priority queue stores linearly ordered data based on the priority; however, by restricting the operations, those operations can be optimized.

8. Sorting algorithms

9. Hash functions and hash tables

Note that previously I used to teach linear probing and double hashing; however, it has been brought to my attention that quadratic hashing is better—especially when we consider the effects of caching and the additional cost of cache misses.

10. Equivalence relations and disjoint sets

11. Graph algorithms

12. Algorithm design

13. Theory of computation

14. Other topics

15. Concluding remarks

Algorithms and Data Structures
Department of Electrical and Computer Engineering
University of Waterloo
200 University Avenue West
Waterloo , Ontario , Canada N2L 3G1

• Feedback
• Faculty of Engineering
• Privacy statement
• © 2012 University of Waterloo