Transcript dos trees
Algorithms Design
Fall 2016
Week 4
Linked Lists and Trees
class NewStack{
private:
queue<int> q1;
queue<int> q2;
public:
void push(int);
int pop();
};
void NewStack :: push(int x)
{
// Your Code
}
int NewStack :: pop()
{
// Your Code
}
Can you implement Stack push
and pop using 2 queues?
Can you implement Stack push and pop using 2 queues?
void NewStack :: push(int o) // o is the element to be pushed and s is stack
q2.enqueue(o);
While(not q1.empty()){
int x=q1.dequeue;
q2.enqueue(x);
}
//swap the names of q1 and q2
tmp=q1;
q1 =q2 ;
q2 =q1;
}
Int NewStack::pop() {
return q1.dequeue();
}
Stack with a Singly Linked List
• We can implement a stack with a singly linked list
• The top element is stored at the first node of the list
• The space used is O(n) and each operation of the Stack ADT
takes O(1) time
nodes
t
elements
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
1. a cell of an array
2. a node of a linked list
• Just one method:
• object element(): returns the element stored at the position
List ADT (§2.2.2)
• The List ADT models a sequence of
positions storing arbitrary objects
• It allows for insertion and removal in the
“middle”
• Query methods:
• isFirst(p), isLast(p)
Accessor methods:
• first(), last()
• before(p), after(p)
• Update methods:
• replaceElement(p, o),
swapElements(p, q)
• insertBefore(p, o),
insertAfter(p, o),
• insertFirst(o),
insertLast(o)
• remove(p)
Queue with a Singly Linked List
• We can implement a queue with a singly linked list
• The front element is stored at the first node
• The rear element is stored at the last node
• The space used is O(n) and each operation of the Queue
ADT takes O(1) time
r
nodes
f
elements
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
• Special trailer and header nodes
header
nodes/positions
elements
node
trailer
Insertion
• We visualize operation insertAfter(p, X), which returns position q
p
A
B
C
p
A
q
B
C
X
p
A
q
B
X
C
Deletion
• We visualize remove(p), where p = last()
p
A
B
C
A
B
C
D
p
D
A
B
C
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
• element() of the Position ADT runs in O(1) time
Applications of Sequences
• The Sequence ADT is a basic, general-purpose,
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
Array-based Implementation of Lists
(Stack,Queue etc)
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
2
3
positions
S
f
l
Can you implement Queue using pop and push and two
stacks, s1 and s2?
class NewQueue{
private:
stack<int> s1;
stack<int> s2;
public:
void enqueue(int);
int dequeue();
}; */
/* The method inserts X into the NewQueue */
void NewQueue :: enqueue(int x)
{
// Your Code?
}
/*The method dequeue which gets out of the NewQueue*/
int NewQueue ::dequeue()
{
// Your Code?
}
Trees
• In computer science, a tree is an
abstract model of a hierarchical
structure
• A tree consists of nodes with a
parent-child relation
• Applications:
• Organization charts
• File systems
• Programming environments
Computers”R”Us
Sales
US
Europe
Manufacturing
International
Asia
Laptops
Canada
Desktops
R&D
Another Tree example:
Unix/Dos File System
Tree Terminology
• Root: node without parent (A)
• Internal node: node with at least one child (A, B, C, F)
• External node (a.k.a. leaf ): node without children (E, I,
J, K, G, H, D)
• Ancestors of a node: parent, grandparent, grandgrandparent, etc.
• Depth of a node: number of ancestors
• Height of a tree: maximum depth of any node (3)
• Descendant of a node: child, grandchild, grandgrandchild, etc.
Subtree: tree consisting of a
node and its descendants
A
B
E
C
F
I
J
G
K
D
H
subtree
Trees
• In computer science, a tree is an
abstract model of a hierarchical
structure
• A tree consists of nodes with a
parent-child relation
• Applications:
• Organization charts
• File systems
• Programming environments
Computers”R”Us
Sales
US
Europe
Manufacturing
International
Asia
Laptops
Canada
Desktops
R&D
Tree Abstract Data Type (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)
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
Intuitive Representation of Tree Node
List Representation
( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )
The root comes first, followed by a list of links to sub-trees
How many link fields are needed in
such a representation?
Data
Link 1
Link 2
…
Link n
Trees
• Every tree node:
• object – useful information
• children – pointers to its children
Data
Data
Data
Data
Data
Data
Data
A Tree Representation
• A node is represented by an object storing
• Element
• Parent node
• Sequence of children nodes
B
A
D
F
B
D
A
C
F
E
C
E
Left Child, Right Sibling Representation
Data
Left
Child
Right
Sibling
A
B
E
J
F
K
C
D
G
H
L
I
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
Algorithm preOrder(v)
visit(v)
for each child w of v
preorder (w)
Make Money Fast!
2
5
1. Motivations
9
2. Methods
3
4
1.1 Greed
1.2 Avidity
6
2.1 Stock
Fraud
7
2.2 Ponzi
Scheme
References
8
2.3 Bank
Robbery
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
8
7
homeworks/
todo.txt
1K
programs/
1
2
h1c.doc
3K
h1nc.doc
2K
4
DDR.java
10K
5
Stocks.java
25K
6
Robot.java
20K
Inorder Traversal
Algorithm inOrder(v)
if isInternal (v)
inOrder (leftChild (v))
visit(v)
if isInternal (v)
inOrder (rightChild (v))
• In an inorder traversal of a binary tree, a
node is visited after its left subtree and
before its right subtree
• Application: draw a binary tree
• x(v) = inorder rank of v
• y(v) = depth of v
6
2
8
1
4
3
7
5
9