### Unit 8: Hash Tables, Graphs, and Trees

This unit will identify various problems that computer scientists encounter when using array indexes and present Hash Tables as a solution. Students will learn about different Hash Tables categories, identifying their respective performance efficiencies. The unit will conclude with an introduction to graphs and special graph types known as trees and binary trees. We will learn how to implement these new Data Structures, discuss operations that accompany them, and identify different ways of traversing, searching, and sorting them.

**Completing this unit should take approximately 9 hours.**

Upon successful completion of this unit, you will be able to:

- demonstrate effective hash tables.
- define hashtable and hash function.
- describe the attributes of good hash functions.
- describe several common hash functions.
- apply hash tables and hash functions for insertion, deletion, and value access within a specific application.

- demonstrate effective graphs.
- define graph.
- state the components of a graph.
- describe the two principal graph traversal paradigms.
- demonstrate the use of graphs as a solution to a particular application requirement.
- know the difference between directed and undirected graph.
- define spanning tree.
- explain means of generating spanning trees.
- define graph cycle.

- demonstrate effective trees.
- state the difference between trees and graphs.
- define the basic components of a tree: root, leaf, branch, node, level.
- know the difference between binary and nonbinary trees.
- apply trees to solve specific application requirements.

- demonstrate effective hash tables.

### 8.1: Hash Tables

This lecture introduces the concept of key/value pairs and how to search for them via hash functions. Chaining is used to handle collisions, which are when multiple values share the same key.

This lecture expands upon the previous one to introduce the possibilities of running out of space in the hash table or of having chains that are too long. In those cases, we would want to increase the size of the hash table; this lecture discusses how to do that effectively.

Watch this lecture, which foregoes chaining as a means of handling collisions and uses table-probing instead.

Read this section on hashing, which presents a different perspective than the lectures above. This section uses C/C++ syntax.

### 8.2: Graphs

In computer science, the term "graph" refers to a set of vertices (points or nodes) and of edges (lines) that connect the vertices. The creation and traversal of graphs is an important topic when learning to solve complex problems that involve numerous relationships. Read this chapter for an excellent discussion on graphs and graph traversal.

Review these slides, which discuss different graph representations and the efficiency of various representations.

This article explains how to find all non-cyclical paths in a graph. Creating a traversal that visits nodes only once while still reaching the goal is a part of creating efficient solutions.

### 8.2.1: Graph Searches

There are many ways to traverse a graph; this article focuses on depth-first. This approach seeks a solution by going to the nodes furthest from the starting point.

Another way to traverse a graph is to seek solutions starting at the closest nodes. This article explains how that is accomplished.

### 8.2.2: Finding Lowest-Cost Paths

Getting from one node in a graph to another while expending the least cost is important in many domains. This article discusses Dijkstra's algorithm and its implementation.

An alternative approach to path finding is Bellman's algorithm. This page explains that approach and its implementation.

### 8.2.3: Finding a Minimum Spanning Tree

For a graph's vertices (nodes) and weighted edges connecting the vertices, a minimum spanning tree contains only the minimum number of edges connecting all vertices while having the minimum total weight when compared to all sets of edges that connect all vertices. Note that there may be more than one set of edges that has the minimum sum of weights. This article explains Kruskal's method of obtaining a minimum spanning tree.

Prim created another popular approach to creating a minimum spanning tree. Since there is an infinity of potential application requirements and situations, there is never any one best approach in computer science, regardless of any academic snobbery you may encounter. Your ability to solve problems depends on your creativity, objectivity, and flexibility. Do not be trapped by an attempt to force-fit someone's favorite tool to all situations.

### 8.3: Trees

Trees are a special case of graph, where the graph's nodes do not have multiple references. Tree traversal is only in one direction, downward, from root (top) to leaves (bottom). Read this page for basic definitions and illustrations.

Most discussion about trees concerns binary trees, whose nodes have no more than two branches. Read this chapter, which offers background and practical applications for binary trees.

Read this chapter, which extends the discussion on binary trees to those trees whose nodes have more than just two branches.

### Unit 8 Assessment

Take this assessment to see how well you understood this unit.

- This assessment
**does not count towards your grade**. It is just for practice! - You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
- You can take this assessment as many times as you want, whenever you want.

- This assessment