Trees & Graphs

Nell Dale & John Lewis

(adaptation by Michael Goldwasser and Erin Chambers)

More complicated abstract data types

What if we want to store lists which access information in a particular order?

Think about standing in a line at the grocery store:

Where do you get added to the list?

Where do you get removed from?

Queues

Queue

An abstract data type in which items are entered at one end and removed from the other end

FIFO, for First In First Out

No standard queue terminology

Enqueue, Enque, Enq, Enter, and Insert
are used for the insertion operation

Dequeue, Deque, Deq, Delete, and Remove
are used for the deletion operation.

Name

three

everyday

structures

that are

queues

Stacks

Stack

An abstract data type in which accesses are made at only one end

LIFO, which stands for Last In First Out

The insert is called Push and the delete is called Pop

Name three everyday

structures that are stacks

How to make stacks and queues?

We can make a queue or stack by building on an array or linked list.

But performance might not be as good either way.

Do queues and stacks work best by using an array to make them, or a linked list?

9-5

Trees

Arrays and Linked Lists often represent data which is inherently linear.

More complex relationships require more complex structures.

A common set of relationships is a “hierarchy”

9-5

Organizational Chart

Figure taken from: http://www.state.gov/r/pa/ei/rls/dos/7926.htm

9-5

Biology Taxonomy

Figure taken from: http://ag.arizona.edu/pubs/garden/mg/entomology/intro.html

9-5

Genealogy

Figure taken from: http://www.bible.ca/b-bible-timeline-history.htm

9-5

Computer File System

Figure 11.4 A Windows directory tree

9-5

Hierarchies

Company Organization	(President, VPs, Managers, …)

Biology Taxonomy	(Kindom, Phylum, Class, …)

Genealogy (Abraham, Isaac, Jacob, …)

File Systems (Folders, Subfolders, …)

Table of Contents for a text book

Web Portals (e.g., Yahoo’s catagories)

Huffman Codes

9-5

Terminology

This is a tree

The positions are nodes

The topmost node is the root

Nodes at the other extreme	are	called leaves

A node may have a parent,	ancestors, children,	siblings or descendants

A natural recursive view	leads us to discussing	subtrees of the tree

Binary Trees

Binary trees

A tree in which each node has at most two children

The node to the left of a node, if it exists, is called its left child

The node to the right of a node, if it exists, is its	right child

Figure 9.16 A binary tree

9-5

Representation

We can represent a binary tree as a linked structure (similar to linked lists)

A node of the tree might be represented by three consecutive cells of memory

User’s Data

Explicit Pointer to Left Child

Explicit Pointer to Right Child

(we will use “null” pointer if no such child)

9-5

Representation (cont)

Page 315

9-5

A Simple Database

Let’s revisit idea of maintaining a list of names, while supporting the following operations:

search for the presence of an entry

print names in alphabetical order

insert new names

How should we accomplish this?

9-5

A Simple Database

Use an (alphabetized) array ?

can do binary search

straightforward to print alphabetically

but inserting new item can be costly

Use a (sorted) linked list?

easy to insert item, if we know the location

straightforward to print alphabetically

but cannot search efficiently

(can’t binary search; no way to jump to middle)

9-5

Binary Search Trees

A binary search tree is a special kind of binary tree.

Semantic property among the values in the nodes in the tree:

The value in any node is greater than the value in any node in its left subtree and less than the value in any node in its right subtree

9-5

Binary Search Tree

Figure 9.18 A binary search tree

9-5

Searching

isThere(current, item):

if (current = null)

return False

else

if (item = info(current))

return True

else:

if (item < info(current))

return IsThere(left(current), item)

if (item > info(current))

return IsThere(right(current), item)

9-5

Alphabetical Printing

PrintAll(tree):

if tree != null:

PrintAll(left(tree))

print info(tree)

PrintAll(right(tree))

Why does this work?

9-5

Insertion

Page 316

9-5

Example (Figure 9.19)

Let’s build a search tree by inserting names

john, phil, lila, kate, becca, judy, june, mari, jim, sarah

[example done in class]

9-5

Graphs

Graph: a data structure that consists of a set of nodes and a set of edges that relate the nodes to each other

Undirected graph: a graph in which the edges have no direction

Directed graph (Digraph): a graph in which each edge is directed from one vertex to another (or the same) vertex

9-5

Kevin Bacon?

Figure 9.21
Examples of graphs

9-5

Flight Plans

Figure 9.21
Examples of graphs

9-5

Prerequisites

Figure 9.21
Examples of graphs

PowerPoint Presentation

Jones & Bartlett Publishers

2002-06-09T13:46:17