Transcript Chapter2

Chapter 2: Basic Data Structures
Basic Data Structures
Stacks
Queues
Vectors, Linked Lists
Trees
Priority Queues and Heaps
Dictionaries and Hash Tables
Spring 2003
CS 315
2
Abstract Data Types (ADTs)
An abstract data
type (ADT) is an
abstraction of a
data structure
An ADT specifies:



Data stored
Operations on the
data
Error conditions
associated with
operations
Spring 2003
Attempting the execution
of an operation of ADT
may sometimes cause an
error condition, called an
exception
Exceptions are said to be
“thrown” by an operation
that cannot be executed
CS 315
3
Example: The Stack ADT
The Stack ADT stores
arbitrary objects
Insertions and deletions
follow the last-in first-out
scheme
Think of a spring-loaded
plate dispenser
Main stack operations:


push(object): inserts an
element
object pop(): removes and
returns the last inserted
element
Spring 2003
CS 315
Auxiliary stack
operations:



object top(): returns the
last inserted element
without removing it
integer size(): returns the
number of elements
stored
boolean isEmpty():
indicates whether no
elements are stored
4
Stack Exceptions
In the Stack ADT, operations pop and top
cannot be performed if the stack is
empty
Attempting the execution of pop or top
on an empty stack throws an
EmptyStackException
Spring 2003
CS 315
5
Performance and Limitations
Performance



Let n be the number of elements in the stack
The space used is O(n)
Each operation runs in time O(1)
Limitations


The maximum size of the stack must be defined a
priori and cannot be changed
Trying to push a new element into a full stack
causes an implementation-specific exception
Spring 2003
CS 315
6
Growable Array-based Stack
In a push operation, when Algorithm push(o)
the array is full, instead of
if t = S.length  1 then
throwing an exception, we
A  new array of
can replace the array with
size …
a larger one
for i  0 to t do
A[i]  S[i]
How large should the new
SA
array be?


incremental strategy:
increase the size by a
constant c
doubling strategy: double
the size
Spring 2003
CS 315
tt+1
S[t]  o
Cost O(n) per op
Cost O(1) per op
7
All ops cost O(1)
The Queue ADT
The Queue ADT stores arbitrary
objects
Insertions and deletions follow
the first-in first-out scheme
Insertions are at the rear of the
queue and removals are at the
front of the queue
Main queue operations:


enqueue(object): inserts an
element at the end of the
queue
object dequeue(): removes and
returns the element at the front
of the queue
Spring 2003
CS 315
Auxiliary queue
operations:



object front(): returns the
element at the front without
removing it
integer size(): returns the
number of elements stored
boolean isEmpty(): indicates
whether no elements are
stored
Exceptions

Attempting the execution of
dequeue or front on an
empty queue throws an
EmptyQueueException
8
Applications of Queues
Direct applications



Waiting lists, bureaucracy
Access to shared resources (e.g., printer)
Multiprogramming
Indirect applications


Auxiliary data structure for algorithms
Component of other data structures
Spring 2003
CS 315
9
Array-based Queue
Use an array of size N in a circular fashion
Two variables keep track of the front and rear
f index of the front element
r index immediately past the rear element
Array location r is kept empty
normal configuration
Q
0 1 2
f
r
wrapped-around configuration
Q
0 1 2
Spring 2003
r
f
CS 315
10
Growable Array-based Queue
In an enqueue operation, when the array is
full, instead of throwing an exception, we
can replace the array with a larger one
Similar to what we did for an array-based
stack
The enqueue operation has amortized
running time


Spring 2003
O(n) with the incremental strategy
O(1) with the doubling strategy
CS 315
11
The Vector ADT
The Vector ADT
extends the notion of
array by storing a
sequence of arbitrary
objects
An element can be
accessed, inserted or
removed by specifying
its rank (number of
elements preceding it)
An exception is
thrown if an incorrect
rank is specified (e.g.,
a negative rank)
Spring 2003
Main vector operations:
 object elemAtRank(integer r):
returns the element at rank r
without removing it
 object replaceAtRank(integer r,
object o): replace the element at
rank with o and return the old
element
 insertAtRank(integer r, object o):
insert a new element o to have
rank r
 object removeAtRank(integer r):
removes and returns the element
at rank r
Additional operations size() and
isEmpty()
CS 315
12
Applications of Vectors
Direct applications

Sorted collection of objects (elementary
database)
Indirect applications


Auxiliary data structure for algorithms
Component of other data structures
Spring 2003
CS 315
13
Array-based Vector
Use an array V of size N
A variable n keeps track of the size of the vector
(number of elements stored)
Operation elemAtRank(r) is implemented in O(1)
time by returning V[r]
V
0 1 2
Spring 2003
n
r
CS 315
14
Insertion
In operation insertAtRank(r, o), we need to make
room for the new element by shifting forward the
n  r elements V[r], …, V[n  1]
In the worst case (r = 0), this takes O(n) time
V
0 1 2
r
n
0 1 2
r
n
0 1 2
o
r
V
V
Spring 2003
CS 315
n
15
Deletion
In operation removeAtRank(r), we need to fill the
hole left by the removed element by shifting
backward the n  r  1 elements V[r + 1], …, V[n  1]
In the worst case (r = 0), this takes O(n) time
V
0 1 2
o
r
n
0 1 2
r
n
0 1 2
r
V
V
Spring 2003
CS 315
n
16
Performance
In the array based implementation of a Vector



The space used by the data structure is O(n)
size, isEmpty, elemAtRank and replaceAtRank run in
O(1) time
insertAtRank and removeAtRank run in O(n) time
If we use the array in a circular fashion,
insertAtRank(0) and removeAtRank(0) run in
O(1) time
In an insertAtRank operation, when the array
is full, instead of throwing an exception, we
can replace the array with a larger one
Spring 2003
CS 315
17
Singly Linked List
A singly linked list is a
concrete data structure
consisting of a sequence
of nodes
Each node stores


next
element
link to the next node
node
elem

A
Spring 2003
B
C
CS 315
D
18
Position ADT
The Position ADT models the notion of
place within a data structure where a
single object is stored
It gives a unified view of diverse ways
of storing data, such as


a cell of an array
a node of a linked list
Just one method:

Spring 2003
object element(): returns the element
stored at the position
CS 315
19
List ADT
The List ADT models a
sequence of positions
storing arbitrary objects
It establishes a
before/after relation
between positions
Generic methods:

size(), isEmpty()
Spring 2003


isFirst(p), isLast(p)



CS 315
first(), last()
before(p), after(p)
Update methods:

Query methods:

Accessor methods:
replaceElement(p, o),
swapElements(p, q)
insertBefore(p, o),
insertAfter(p, o),
insertFirst(o),
insertLast(o)
remove(p)
20
Doubly Linked List
A doubly linked list provides a natural
implementation of the List ADT
Nodes implement Position and store:



element
link to the previous node
link to the next node
prev
next
elem
node
Special trailer and header nodes
nodes/positions
header
trailer
elements
Spring 2003
CS 315
21
Insertion
We visualize operation insertAfter(p, X), which returns position q
p
A
B
C
p
A
q
B
C
X
p
A
Spring 2003
q
B
CS 315
X
C
22
Deletion
We visualize remove(p), where p = last()
p
A
B
C
A
B
C
D
p
D
A
Spring 2003
B
CS 315
C
23
Performance
In the implementation of the List ADT
by means of a doubly linked list




The space used by a list with n elements is
O(n)
The space used by each position of the list
is O(1)
All the operations of the List ADT run in
O(1) time
Operation element() of the
Position ADT runs in O(1) time
Spring 2003
CS 315
24
Sequence ADT
The Sequence ADT is the
union of the Vector and
List ADTs
Elements accessed by


List-based methods:

Rank, or
Position
Generic methods:

size(), isEmpty()
Vector-based methods:

elemAtRank(r),
replaceAtRank(r, o),
insertAtRank(r, o),
removeAtRank(r)
Spring 2003
first(), last(),
before(p), after(p),
replaceElement(p, o),
swapElements(p, q),
insertBefore(p, o),
insertAfter(p, o),
insertFirst(o),
insertLast(o),
remove(p)
Bridge methods:

CS 315
atRank(r), rankOf(p)
25
Applications of Sequences
The Sequence ADT is a basic, generalpurpose, data structure for storing an ordered
collection of elements
Direct applications:


Generic replacement for stack, queue, vector, or
list
small database (e.g., address book)
Indirect applications:

Building block of more complex data structures
Spring 2003
CS 315
26
Array-based Implementation
elements
We use a
circular array
storing
positions
A position
object stores:


Element
Rank
Indices f and l
keep track of
first and last
positions
0
1
3
positions
S
f
Spring 2003
2
CS 315
l
27
Sequence Implementations
Operation
size, isEmpty
atRank, rankOf, elemAtRank
first, last, before, after
replaceElement, swapElements
replaceAtRank
insertAtRank, removeAtRank
insertFirst, insertLast
insertAfter, insertBefore
remove
Spring 2003
CS 315
Array
1
1
1
1
1
n
1
n
n
List
1
n
1
1
n
n
1
1
1
28
Iterators
An iterator abstracts the
process of scanning through
a collection of elements
Methods of the ObjectIterator
ADT:




object object()
boolean hasNext()
object nextObject()
reset()

ObjectIterator elements()
Two notions of iterator:
Extends the concept of
Position by adding a traversal
capability
Implementation with an array
or singly linked list
Spring 2003
An iterator is typically
associated with an another
data structure
We can augment the Stack,
Queue, Vector, List and
Sequence ADTs with method:
CS 315


snapshot: freezes the
contents of the data
structure at a given time
dynamic: follows changes to
the data structure
29
Tree ADT
We use positions to abstract
nodes
Generic methods:




integer size()
boolean isEmpty()
objectIterator elements()
positionIterator positions()
Accessor methods:



position root()
position parent(p)
positionIterator children(p)
Spring 2003
CS 315
Query methods:



boolean isInternal(p)
boolean isExternal(p)
boolean isRoot(p)
Update methods:


swapElements(p, q)
object replaceElement(p, o)
Additional update methods
may be defined by data
structures implementing the
Tree ADT
30
Preorder Traversal
A traversal visits the nodes of a
tree in a systematic manner
In a preorder traversal, a node is
visited before its descendants
Application: print a structured
document
1
Make Money Fast!
2
5
1. Motivations
9
2. Methods
3
4
1.1 Greed
1.2 Avidity
Spring 2003
Algorithm preOrder(v)
visit(v)
for each child w of v
preorder (w)
6
7
2.1 Stock
Fraud
CS 315
2.2 Ponzi
Scheme
References
8
2.3 Bank
Robbery
31
Postorder Traversal
In a postorder traversal, a
node is visited after its
descendants
Application: compute space
used by files in a directory and
its subdirectories
9
Algorithm postOrder(v)
for each child w of v
postOrder (w)
visit(v)
cs16/
3
7
homeworks/
todo.txt
1K
programs/
1
2
h1c.doc
3K
h1nc.doc
2K
Spring 2003
8
4
5
DDR.java
10K
CS 315
Stocks.java
25K
6
Robot.java
20K
32
Binary Tree
A binary tree is a tree with the
following properties:


Applications:

Each internal node has two
children
The children of a node are an
ordered pair


A
We call the children of an internal
node left child and right child
Alternative recursive definition: a
binary tree is either


a tree consisting of a single node,
or
a tree whose root has an ordered
pair of children, each of which is a
binary tree
arithmetic expressions
decision processes
searching
B
C
D
E
H
Spring 2003
CS 315
F
G
I
33
Arithmetic Expression Tree
Binary tree associated with an arithmetic expression


internal nodes: operators
external nodes: operands
Example: arithmetic expression tree for the
expression (2  (a  1) + (3  b))
+



2
a
Spring 2003
3
b
1
CS 315
34
Properties of Binary Trees
Notation
Properties:
 e = i + 1
 n = 2e  1
 h  i
 h  (n  1)/2
h
 e  2
 h  log2 e
 h  log2 (n + 1)  1
n number of nodes
e number of
external nodes
i number of internal
nodes
h height
Spring 2003
CS 315
35
BinaryTree ADT
The BinaryTree ADT
extends the Tree
ADT, i.e., it inherits
all the methods of
the Tree ADT
Additional methods:



Update methods
may be defined by
data structures
implementing the
BinaryTree ADT
position leftChild(p)
position rightChild(p)
position sibling(p)
Spring 2003
CS 315
36
Euler Tour Traversal
Generic traversal of a binary tree
Includes as special cases the preorder, postorder and inorder traversals
Walk around the tree and visit each node three times:
 on the left (preorder)
 from below (inorder)
 on the right (postorder)
+
L
2


R
B

5
Spring 2003
3
2
1
CS 315
37
Data Structure for Trees
A node is represented by
an object storing



Element
Parent node
Sequence of children
nodes

B

Node objects implement
the Position ADT
A
B
D
A
C

D
F

E
C
Spring 2003
F
CS 315

E
38
Data Structure for Binary Trees
A node is represented by
an object storing





Element
Parent node
Left child node
Right child node
B
Node objects implement
the Position ADT

B
A
A
D
C
Spring 2003

D

E

C
CS 315


E
39