Transcript Document

Data Structures and
Algorithm Design
(Review)
Data Structures and Algorithm Design:
Java basics
Object-oriented design
Stacks, queues, and deques
Vectors, lists and sequences
Trees and binary trees
……
Java Basics
Class
Class Modifiers
abstract, final, public
Variable Modifiers
public, protected, private, static, final
Methods
Method Modifiers
public, protected, private, abstract, final, static
Arrays
int[] a = new int[ 10 ];
float[][] x = new float[ 8 ][ 10 ];
a[ i ] = 138;
x[ i ][ i + 1 ] = 2.189 + x[ i ][ i ];
Java Basics
Recursion
public class RecursionExample {
public static int function(int n) {
if (n==0) return 1;
if (n==1) return 1;
if (n==2) return 3;
else return 3*function(n-3) + 4*function(n-2) + 5*function(n-1);
}
public static void main(String []args){
int num = Integer.parseInt(args[0]);
System.out.println(num);
int b = function(num);
System.out.println("f =" + " " + b);
}}
Object-Oriented Design
Inheritance
Polymorphism
method overriding
method overloading
Keyword: this
Exception
Interface, Abstract Classes
Type casting
import java.util.*;
import java.lang.*;
interface CanFight { void fight ( );}
interface CanSwim { void swim ( );}
interface CanFly {void fly ( );}
class ActionCharacter { public void fight( ) { }}
class Hero extends ActionCharacter
implements CanFight, CanSwim, CanFly {
public void fight ( ) {System.out.println(“Can
fight!”);}
public void swim ( ) {System.out.println(“Can
swim!”); }
public void fly ( ) {System.out.println(“Can fly!”);}
}
public class Adventure {
static void t(CanFight x) { x.fight();}
static void u(CanSwim x) { x.swim();}
static void v(CanFly x) { x.fly();}
static void w(ActionCharacter x) { x.fight();}
public static void main (String[ ] args) {
Hero h = new Hero( );
t(h); //Treat it as a CanFight
u(h); //Treat it as a CanSwim
v(h); //Treat it as a CanFly
w(h); //Treat it as an ActionCharacter
}
}
ActionCharacter
subclass
CanFight
CanSwim
CanFly
implementation
Hero
instantiation
h
static void t(CanFight x) { x.fight();}
static void u(CanSwim x) { x.swim();}
static void v(CanFly x) { x.fly();}
static void w(ActionCharacter x) { x.fight();}
Hero h = new Hero( )
t(h); //Treat it as a CanFight
u(h); //Treat it as a CanSwim
v(h); //Treat it as a CanFly
w(h); //Treat it as an ActionCharacter
Stacks, Queues, and Deques
Stacks
Queues
Deques
Singly linked lists
Doubly linked lists
Sample case study application
Stacks
Definition: A stack is a container of objects that are inserted and
removed according to the last-in first-out (LIFO) principle.
A stack S is an abstract data type (ADT) that supports following
two fundamental methods:
push(o): Insert object o at the top of the stack
Input: Object; Output: None.
pop(): Remove from the stack and return the top object on
the stack; an error occurs if the stack is empty.
Input: None; Output: Object
public interface Stack {
public void push( Object element );
public Object pop()
throws StackEmptyException;
public int size();
public boolean isEmpty();
public Object top()
throws StackEmptyException;
}
public class ArrayStack implements Stack {
public static final int CAPACITY = 1000;
private in capacity;
private Object [] S;
private int top = -1;
public ArrayStatck() {
this( CAPACITY );
}
public ArrayStack( int cap ) {
capacity = cap;
S = new Object[ capacity ];
}
public int size() {
return ( top + 1 );
}
public boolean isEmpty() {
return( top < 0 );
}
public void push( Object obj )
throws StackFullException
{
if( size() == capacity )
throw new StackFullException( "Stack overflow" );
S[ ++top ] = obj;
}
public Object top() throws StackEmptyException {
if( isEmpty() )
throw new StackEmptyException( "Stack is empty." );
return S[ top ];
}
public Object pop() throws StackEmptyException {
Object elem;
if( isEmpty() )
throw new StackEmptyException( "Stack is Empty." );
elem = S[ top ];
S[ top-- ] = null;
return elem;
}
}
Sample Case Study Application
We want to write a program to calculate the span of the stock’s
price on a given day.
The span of the stock’s price on a given day: The maximum
number of the consecutive days up to the current day such that the
stock price on each of those days has been less than or equal to
the price on the current day.
Java Implementation
public void computeDailyHighSpan( Quote Q[]) {
int prevHigh;
Stack D = new ArrayStack();
for( int i = 0; i < Q.length; i++ ) {
while( !D.isEmpty() &&
Q[ i ].getPrice() >= (( Quote )D.top()).getPrice() )
D.pop();
if( D.isEmpty() )
prevHigh = -1;
else
prevHigh = (( Quote )D.top()).getDay();
Q[ i ].setSpan( i - prevHigh );
D.push( Q[ i ]);
}
}
public class Quote {
private int day, price, span;
public Quote( int d, int p ) {
setDay( d );
setPrice( p );
}
public void setDay( int d ) { day = d; }
public int getDay() { return day; }
public void setPrice( int p ) { price = p; }
public int getPrice() { return price; }
public void setSpan( int s ) { span = s; }
public int getSpan() { return span; }
}
Main idea:
The span si on a certain day i can be easily computed
if we know the closest day preceding day i, such that the price
on that day is higher than the price on day i.
If such a preceding day exists for a day i, let us denote it with
h(i), and otherwise let us define h(i) = -1. Then, si = i – h(i).
si = i – h(i).
Example:
p0
48.97
p1
47.54
p2
45.83
p3
46.34
p4
45.68
p5
46.95
p6
48.17
h(0)
-1
h(1)
0
h(2)
1
h(3)
1
h(4)
3
h(5)
1
h(6)
0
s0
1
s1
1
s2
1
s3
2
s4
1
s5
4
s6
6
The problem is how to compute h(i) efficiently?
Step 1:
p0 = 48.97. h(0) = -1, s0 = 0 - h(0) = 0 – (-1) = 1
0
Day 0. It is possible that h(1) = 0.
Step 2:
p1 = 47.54. Pop days with prices less than or equal to p1.
At this point of time, we have only one element in the stack.
It is 0 and p0 > p1. So h(1) = 0, s1 = 1 - h(1) = 1 – 0 = 1.
1
0
Day 1. It is possible that h(2) = 1.
Step 3:
p2 = 45.83. Pop days with prices less than or equal to p2.
At this point of time, we have two elements in the stack.
The top one is 1 and p1 > p2. So h(2) = 1, s2 = 2 - h(2) = 2 – 1 = 1.
2
Day 2. It is possible that h(3) = 2.
1
0
Step 4:
p3 = 46.34. Pop days with prices less than or equal to p3.
The top one will be taken out since p3 > p2.
The second one is 1 and p1 > p3. So h(3) = 1, s3 = 3 - h(3) = 3 – 1 = 2.
3
1
0
Day 3. It is possible that h(4) = 3.
Step 5:
p4 = 45.68. Pop days with prices less than or equal to p4.
The top one is 3 and p3 > p4. So h(4) = 3, s4 = 4 - h(3) = 4 – 3 = 1.
4
3
Day 4. It is possible that h(5) = 4.
1
0
Step 6:
p5 = 46.95. Pop days with prices less than or equal to p3.
The top two will be taken out since p5 > p4 and p5 > p3.
The third one is 1 and p1 > p5. So h(5) = 1, s5 = 5 - h(5) = 5 – 1 = 4.
5
1
0
Day 5. It is possible that h(6) = 5.
Step 7:
p6 = 48.17. Pop days with prices less than or equal to p3.
The top two will be taken out since p6 > p5 and p6 > p1.
The third one is 0 and p0 > p6. So h(6) = 0, s5 = 6 - h(6) = 6 – 0 = 6.
6
0
Day 6. The price on day 6. The process stops.
How to calculate 1+2-3+4-5+6+7-8+9?
public class ExpressionAlculation {
public static void main(String [] args){
String s = "1+2-3+4-5+6+7-8+9";
char c = 0; int result = 0; Object temp;
Stack myStack = new ArrayStack();
myStack.push(new Integer(1));
for (int i = 1; i < s.length(); i++){
if (s.charAt(i) == ‘+’ || s.charAt(i) == ‘-’)
myStack.push(new Character(s.charAt(i)));
else {
temp = myStack.pop();
result = ((Integer)myStack.pop()).intValue();
c = s.charAt(i);
if (temp == ‘+’) result = result + (c-'0');
else result = result - (c-'0');
myStack.push(new Integer(result));}
}
System.out.println("Total is " + result);
}
}
Queues
Definition: A queue is a container of objects that are inserted and
removed according to the first-in first-out (FIFO) principle.
A queue Q is an abstract data type that supports the following
two fundamental methods:
enqueue(o): Insert object o at the rear of the queue
Input: Object; Output: None.
dequeue(): Remove and return from the queue the object at the
front; an error occurs if the queue is empty.
Input: None; Output: Object
public interface Queue {
public void enqueue( Object element );
public Object dequeue()
throws QueueEmptyException;
public int size();
public boolean isEmpty();
public Object front()
throws QueueEmptyException;
}
When we define an interface, we just indicate that
a class which implements it should provide all the
methods specified in it.
class ArrayQueue implements Queue
{
private Object[] elem;
private int front, rear;
private static final int DEFAULT_LENGTH = 100;
private int length;
public ArrayQueue()
{
this(DEFAULT_LENGTH);
}
public ArrayQueue(int length)
{
elem = new Object[length];
front = rear = 0;
this.length = length;
}
public void enqueue(Object element)
throws QueueFullException
{
if (size()==length-1)
throw new QueueFullException();
else
{
elem[rear] = element;
rear = (rear+1)%length;
}
}
public Object dequeue() throws QueueEmptyException
{
if (isEmpty())
throw new QueueEmptyException();
else
{
Object temp = elem[front];
elem[front] = null;
front = (front+1)%length;
return temp;
}
}
private boolean isFull()
{
return (rear-front)==(length-1);
}
public int size()
{
return (length-front+rear)%length;
}
public boolean isEmpty()
{
return front==rear;
}
public Object front() throws QueueEmptyException
{
if (isEmpty())
throw new QueueEmptyException();
else
return elem[front];
}
}
Queues
Application: Search a tree in the breadth-first-manner
1
2
3
4
8
5
9
10
6
11
12
7
13
14
15
enqueue(root);
while (the queue is not empty) do
{x := dequeue; print(x);
let x1, x2, …, xk be the children of x;
for (i = k to 1) do {enqueue(xi);}
}
Queues
Sample trace:
step1:
1
step5:
step2:
step3:
step4:
2 3
3 4 5
4 5 6 7
visit(1)
visit(2)
visit(3)
step6:
5 6 7 8 9
6 7 8 9 10 11
visit(4)
visit(5)
……
Singly Linked Lists
head
next
element
element
Baltimore
Rome
next
next
element
element
Seattle
next
Toronto
link: The next reference inside a node is a link or pointer to
another node.
Class Node
Here is an implementation of nodes in Java:
public class Node {
private Object element;
private Node next;
public Node() {
this( null, null );
}
public Node( Object e, Node n ) {
element = e;
next = n;
}
Object getElement() {
return element
}
Node getNext() {
return next;
}
void setElement( Object newElem ) {
element = newElem;
}
void setNext( Node newNext ) {
next = newNext;
}
}
Have a new node:
head
element
next
next
next
element
element
element
Baltimore
Rome
Seattle
next
Toronto
Node x = new Node();
x.setElement(new String(“Baltimore”));
After the insertion:
head
element
next
next
next
element
element
element
Baltimore
Rome
x.setNext(head);
head = x;
Seattle
next
Toronto
Remove the node from the list:
head
element
next
next
next
element
element
element
Baltimore
Rome
Seattle
head = head.getNext();
next
Toronto
How to generate a singly linked list?
public class Head_and_Tail {
Node head;
Node tail;
Head_and_Tail(Node x, Node y)
{
head = x;
tail = y;
}
}
public class GeneratingList {
Node head = null;
Node tail = null;
Public Head_and_Tail linked_list () {
Node x = null;
for (int i = 0; i < 10; i++)
{x = new Node(); x.setElement(new Integer(i));
if (i == 0 ) {x.setNext(null); tail = x;}
else x.setNext(head);
head = x;
}
return new Head_and_Tail(head, tail);}
}
Doubly Linked List
For convenience, a doubly linked list has a header node and a
trailer node. They are also called sentinel nodes, indicating
both the ends of a list.
header
trailer
Baltimore
Rome
Seattle
Difference from singly linked lists:
- each node contains two links.
- two extra nodes: header and trailer, which contain no
elements.
Class DLNode
Here is an implementation of nodes for doubly linked
lists in Java:
public class DLNode {
private Object element;
private DLNode next, prev;
public DLNode() {
this( null, null, null );
}
public DLNode( Object e, DLNode p, DLNode n )
{
element = e;
next = n;
prev = p;
}
void setElement( Object newElem ) {
element = newElem;
}
void setNext( DLNode newNext ) {
next = newNext;
}
void setPrev( DLNode newPrev ) {
prev = newPrev;
}
Object getElement() {
return element;
}
DLNode getNext() {
return next;
}
DLNode getPrev() {
return prev;
}
}
Have a new node:
header
trailer
Baltimore
Rome
Seattle
Toronto
DLNode x = new DLNode();
x.setElement(new String(“Toronto”));
(x.element  new String(“Toronto”))
Update the links:
trailer
header
Baltimore
Rome
Seattle
Toronto
x.setPrev(header);
x.setNext(header.getNext());
(header.getNext()).setPrev(x);
header.setNext(x);
x.prev  header;
x.next  header.next;
header.next.prev  x;
header.next  x;
Update the links:
trailer
header
Toronto
Baltimore
Rome
Seattle
((trailer.getPrev()).getPrev).setNext(trailer);
trailer.setPrev((trailer.getPrev()).getPrev());
trailer.prev.prev.next  trailer;
trailer.prev  trailer.prev.prev;
Deques
Definition: A double-ended queue is a queue that supports
insertion and deletion at both the front and the rear of the queue.
A deque D is an abstract data type that supports the following
four fundamental methods:
insertFirst(e): Insert a new element e at the beginning of D.
Input: Object; Output: None.
insertLast(e): Insert a new element e at the end of D.
Input: Object; Output: None.
removeFirst(): Remove and return the first element of D; an error occurs
if D is empty.
Input: None; Output: Object
removeLast(): Remove and return the last element of D; an error occurs if
D is empty.
Input: None; Output: Object
public interface Deque {
void insertFirst(Object e);
void insertLast(Object e);
Object removeFirst();
Object removeLast();
Object first();
Object last();
int size();
boolean isEmpty();
}
Class MyDeque
public class MyDeque implements Deque {
DNode header, trailer;
int size;
public MyDeque() {
header = new DNode();
trailer = new DNode();
header.setNext( trailer );
trailer.setPrev( header );
size = 0;
}
… …
header
trailer
Implementing Stacks and Queues
with Deques
Stacks and queues can be easily implemented with a deque.
All we need to do is to map the operations.
Implementation of a stack with a deque:
Stack Method
size()
isEmpty()
top()
push(e)
pop()
Deque Implementation
size()
isEmpty()
last()
insertLast(e)
removeLast()
Implementation of a queue with a deque:
Queue Method
size()
isEmpty()
front()
enqueue(e)
dequeue()
Deque Implementation
size()
isEmpty()
first()
insertLast()
removeFirst()
Class DequeStack
public class DequeStack implements Stack {
private Deque D;
public DequeStack() {
D = new MyDeque();
}
public int size() {
return D.size();
}
public boolean isEmpty() {
return D.isEmpty();
}
public void push( Object obj ) {
D.insertLast( obj );
}
public void top() throws StackEmptyException {
try {
return D.last();
}
catch( DequeEmptyException ece ) {
throw new StackEmptyException( "Stack is empty." );
}
}
public Object pop() throws StackEmptyException {
try {
return D.removeLast();
}
catch( DequeEmptyException ece ) {
throw new StackEmptyException( "Stack is empty." );
}
}
}
Vectors, Lists, and Sequences
Vectors
Lists
Sequences
Iterators
Vector (interface)
extends
impl.
ArrayVector (class)
extends
List (interface)
extends
Sequence (interface)
impl.
impl.
ArraySequence (class)
NodeList (class)
extends
NodeSequence (class)
Vectors
public interface Vector {
public int size();
public boolean isEmpty();
public Object elemAtRank(int r);
public Object replaceAtRank(int r, Object e);
public void insertAtRank(int r, Object e);
public Object removeAtRank(int r);
}
public class ArrayVector implements Vector {
private Object[] A;
// array storing the elements of the vector
private int capacity = 16;
// initial length of array A
private int size = 0;
// number of elements stored in the vector
/** Creates the vector with initial capacity 16. */
public ArrayVector() {
A = new Object[capacity];
}
public Object elemAtRank(int r) {return a[r];}
public int size() {return size;}
public boolean isEmpty {return size()==0;}
public Object replaceAtRank (int r, Object e) {
Object temp=a[r];
a[r]=e;
return temp;
}
/** Inserts an element at the given rank. */
public void insertAtRank(int r, Object e)
throws BoundaryViolationException {
checkRank(r, size() + 1);
if (size == capacity) {
// an overflow
capacity *= 2;
Object[] B = new Object[capacity];
for (int i=0; i<size; i++)
B[i] = A[i];
A = B;}
for (int i=size-1; i>=r; i--) // shift elements up
A[i+1] = A[i];
A[r] = e;
size++;
}
/** Removes the element stored at the given rank. */
public Object removeAtRank(int r)
throws BoundaryViolationException {
checkRank(r, size());
Object temp = A[r];
for (int i=r; i<size-1; i++) // shift elements down
A[i] = A[i+1];
size--;
return temp;
}
public int size( ) {return size;}
Lists
public interface Position {
Object element();
}
public class DNode implement Position {
private DNode next, prev;
private Object element;
public DNode( DNode newPrev, DNode newNext, Object elem ){
prev = newPrev;
next = newNext;
element = elem;
}
public Object element() throws InvalidPositionException {
if(( prev == null ) && ( next == null ))
throw new InvalidPositionException(
"Position is not in a list!" );
return element;
}
public DNode getNext() {
return next;
}
public DNode getPrev() {
return prev;
}
public void setNext( DNode newNext ) {
next = newNext;
}
public void setPrev( DNode newPrev ) {
prev = newPrev;
}
public void setElement( Object newElement ) {
element = newElement;
}
}
Position
element();
impl.
Dnode
element(){…};
getNext(){…};
getPrev(){…};
setNext(){…};
setPrev(){…};
setElement(){…};
public interface List {
/** Returns the number of elements in this list. */
public int size();
/** Returns whether the list is empty. */
public boolean isEmpty();
/** Returns the first node in the list. */
public Position first();
/** Returns the last node in the list. */
public Position last();
/** Returns the node after a given node in the list. */
public Position next(Position p)
throws InvalidPositionException, BoundaryViolationException;
/** Returns the node before a given node in the list. */
public Position prev(Position p)
throws InvalidPositionException, BoundaryViolationException;
/** Inserts an element at the front of the list. */
public Position insertFirst(Object e);
/** Inserts and element at the back of the list. */
public Position insertLast(Object e);
/** Inserts an element after the given node in the list. */
public Position insertAfter(Position p, Object e)
throws InvalidPositionException;
/** Inserts an element before the given node in the list. */
public Position insertBefore(Position p, Object e)
throws InvalidPositionException;
/** Removes a node from the list. */
public Object remove(Position p) throws InvalidPositionException;
/** Replaces the element stored at the given node. */
public Object replace(Position p, Object e)
throws InvalidPositionException;
}
Class NodeList
public class NodeList implements List {
protected int numElts;
protected DNode header, trailer;
public NodeList() {
numElts = 0;
header = new DNode( null, null, null );
trailer = new DNode( header, null, null );
header.setNext( trailer );
}
header
trailer
protected DNode checkPosition( Position p )
throws InvalidPositionException {
if( p == null )
throw new InvalidPositionException(
"Null position passed to NodeList." );
if( p == header )
throw new InvalidPositionException(
"The header node is not a valid position." );
if( p == trailer )
throw new InvalidPositionException(
"The trailer node is not a valid position." );
try {
DNode temp = ( DNode )p;
if(( temp.getPrev() == null ) ||
( temp.getNext() == null ))
throw new InvalidPositionException(
"Position does not belong to a valid NodeList." );
return temp;
}
catch( ClassCastException e ) {
throw new InvalidPositionException(
"Position is of wrong type for this container." );
}
}
public int size() { return numElts; }
public boolean isEmpty() {
return( numElts < 1 );
}
public boolean isFirst( Position p )
throws InvalidPositionException {
DNode v = checkPosition(p);
return v.getPrev() == header;
}
public Position first()
throws EmptyContainerException {
if( isEmpty() )
throw new EmptyContainerException(
"List is empty" );
return header.getNext();
}
public Position last()
throws EmptyContainerException {
if( isEmpty() )
throw new EmptyContainerException(
"List is empty" );
return trailer.getPrev();
}
public Position before( Position p )
throws InvalidPositionException,
BoundaryViolationException {
DNode v = checkPosition( p );
DNode prev = v.getPrev();
if( prev == header )
throw new BoundaryViolationException(
"Cannot advance past the beginning of the list" );
return prev;
}
public Position insertBefore( Position p, Object element )
throws InvalidPositionException {
DNode v = checkPosition( p );
numElts++;
DNode newNode = new DNode( v.getPrev(), v, element );
v.getPrev().setNext( newNode );
v.setPrev( newNode );
return newNode;
}
header
trailer
v=p
newNode
element
public Position insertFirst( Object element ) {
numElts++;
DNode newNode = new DNode( header,
header.getNext(), element );
header.getNext().setPrev( newNode );
header.setNext( newNode );
return newNode;
}
header
newNode
element
trailer
public Object remove( Position p )
throws InvalidPositionException {
DNode v = checkPosition( p );
numElts--;
DNode vPrev = v.getPrev();
DNode vNext = v.getNext();
vPrev.setNext( vNext );
vNext.setPrev( vPrev );
Object vElem = v.element();
v.setNext( null );
v.setPrev( null );
return vElem;
}
header
vPrev
v=p
vElem
vNext
trailer
public Object replaceElement( Position p, Object element )
throws InvalidPositionException {
DNode v = checkPosition( p );
Object oldElt = v.element();
v.setElement( element );
return oldElt;
}
public void swapElements( Position a, Position b )
throws InvalidPositionException {
DNode pA = checkPosition( a );
DNode pB = checkPosition( b );
Object temp = pA.element();
pA.setElement( pB.element() );
pB.setElement( temp );
}
List
first(); last(); isFirst(); isLast(); before();
after(); replaceElement(); swapElement();
insertFirst(); insertLast();
impl.
NodeList
… ….
Sequence
The sequence abstract data type supports all the methods of both
the vector ADT and list ADT, plus the following two “bridging”
methods that provide connections between ranks and positions:
atRank(r): Return the position of the element with rank r.
Input: Integer; Output: Position
rankOf(p): Return the rank of the element at position p.
Input: Position; Output: Integer
In Java, the interface for sequences is an example of multiple
inheritance:
interface Sequence extends List, Vector {
public Position atRank( int rank )
throws BoundaryViolationException;
public int rankOf( Position position )
throws InvalidPositionException;
}
Vector interface
List interface
Sequence interface
Implementation of a sequence with a doubly linked list:
Sequence ADT
Position
rank
Doubly linked list
Node
atRank(r)
rankOf(p)
/** Implementation of a sequence by means of a doubly linked list. */
public class NodeSequence extends NodeList implements Sequence {
/** Checks whether the given rank is in the range [0, n - 1] */
protected void checkRank(int r, int n)
throws BoundaryViolationException {
if (r < 0 || r >= n)
throw new BoundaryViolationException("Illegal rank: " + r);
}
/** Returns the position containing the element at the given rank;
* O(n) time. */
public Position atRank (int rank) {
DNode node;
checkRank(rank, size());
if (rank <= size()/2) { // scan forward from the head
node = header.getNext();
for (int i=0; i < rank; i++)
node = node.getNext(); }
else { // scan backward from the tail
node = trailer.getPrev();
for (int i=1; i < size()-rank; i++)
node = node.getPrev();}
return node;
}
/** Gets an element at the given rank.*/
public Object elemAtRank(int r) {
return atRank(r).element();
}
/** Returns the rank of a given position.*/
public int rankOf(Position p) {
DNode node;
node = header.getNext();
for for (int i=1; i < size(); i++) {
if (p == node) return i;
else node = node.getNext();}
}
}
/** Inserts an element at the given rank; O(n) time. */
public void insertAtRank (int rank, Object element)
throws BoundaryViolationException {
checkRank(rank, size() + 1);
if (rank == size())
insertLast(element);
else {
insertBefore(atRank(rank), element);
}
}
/** Removes the element stored at the given rank; O(n) time. */
public Object removeAtRank (int rank)
throws BoundaryViolationException {
checkRank(rank, size());
return remove(atRank(rank));
}
public Object replaceAtRank (int rank, object element)
throws BoundadryViolationException {
checkRank(rank);
return replaceElement(atRank(rank), element);
}
}
Implementing a Sequence with
an Array
Baltimore
New York
0
Rome
2
1
Providence
3
S
0
1
2
3
N-1
Iterator
The iterator abstract data type supports the following
methods:
hasNext(): Test whether there are elements left in the iterator.
Input: None; Output: Boolean
nextObject(): Return and remove the next element in the iterator.
Input: None; Output: Object
Java provides an Iterator interface.
public interface Iterator
{
boolean hasNext();
Object next();
void remove();
}
An implementation of the Iterator is always related to container,
i.e., a vector, a list, or a sequence.
The following is an exemplary implementation of the List Iterator.
public class PositionIterator implements Iterator {
protected List list; // the underlying list
protected Position cur; // the current (next) position
public PositionIterator() { } // default constructor
public PositionIterator(List L) { // preferred constructor
list = L;
if (list.isEmpty()) cur = null; // list is empty
else cur = list.first(); // start with the first position
}
public boolean hasNext() { return (cur != null); }
public Object next() throws NoSuchElementException {
if (!hasNext())
throw new NoSuchElementException("No next position");
Position toReturn = cur;
if (cur == list.last()) cur = null; // no positions left
else cur = list.next(cur); // move cursor to the next position
return toReturn;
}
}
class NoSuchElementException extends Exception {
public NoSuchElementException() {super();}
public NoSuchElementException(String s) { super(s); }
}
In a similar way, we can establish an ElementIterator as follows.
public class ElementIterator implements Iterator {
protected List list; // the underlying list
protected Position cur; // the current (next) position
protected Object elementCur;// the current (next) element
public ElementIterator() { } // default constructor
public ElementIterator(List L) { // preferred constructor
list = L;
if (list.isEmpty()) cur = null; // list is empty
else cur = list.first(); // start with the first position
}
public boolean hasNext() { return (cur != null); }
public Object next() throws NoSuchElementException {
if (!hasNext())
throw new NoSuchElementException("No next position");
elementCur = cur.element();
if (cur == list.last()) cur = null; // no positions left
else cur = list.next(cur); // move cursor to the next position
return elementCur;
}
}
InspectableContainer
size
isEmpty
elements
InspectableList
first
last
before
after
positions
InspectableVector
elemAtRank
Vector
replaceAtRank
insertAtRank
removeAtRank
InspectableSequence
atRank
rankOf
Sequence
List
replaceElement
swapElements
insertFirst
insertLast
insertBefore
insertAfter
remove
Trees
What is a tree?
Tree ADT
Basic algorithms on trees
Tree traversal
What is a tree?
Family Felidae
(cats)
Order Carnivora
(carnivores)
Family Phocidae
(seals)
Subfamily
Acinonychinae
(cheetahs)
Subfamily Felinae
(small cats)
Order Chiroptera
(bats)
Family Ursidae
(bears)
Class Mammalia
...
...
Order Proboscidea
(elephants)
Subfamily
Pantherinae
(leopards, lions,
and tigers)
Tree Interface – Tree ADT
public interface Tree {
public int size();
public Boolean isEmpty();
public ElementIterator elements();
public PositionIterator positions();
public void swapElements( Position v, Position w );
public Object replaceElement( Position v, Object e );
public Position root();
public Position parent( Position v );
public PositionIterator children( Position v );
public boolean isInternal( Position v );
public boolean isExternal( Position v );
public boolean isRoot( Position v );
}
IspectableContainer
size
isElement
Elements
IspectablePositionContainer
positions
InspectableTree
root
parent
children
isRoot
isInternal
isExternal
PositionContainer
swapElement
replaceElement
Tree
A Binary Tree Interface in Java
Similar to the interfaces InspectableTree and Tree, we have
interfaces InspectableBinaryTree and BinaryTree.
public interface InspectableBinaryTree
extends InspectableTree {
public Position leftChild( Position v );
public Position rightChild( Position v );
public Position sibling( Position v );
}
public interface BinaryTree
extends InspectableBinaryTree, PositionalContainer {
}
InspectableContainer
size
isEmpty
elements
InspectablePositionalContainer
positions
InspectableList
first
last
before
after
positions
InspectableVector
elemAtRank
Vector
replaceAtRank
insertAtRank
removeAtRank
InspectableSequence
atRank
rankOf
Sequence
List
insertFirst
insertLast
insertBefore
insertAfter
remove
PositionalContainer
swapElements
replaceElement
InspectableTree
root
parent
children
isRoot
isInternal
isExternal
InspectableBinaryTree
leftChild
rightChild
sibling
Tree
BinaryTree
Since a binary tree is an ordered tree and has levels, it is
convenient to assign a number to each node.
1
2
3
4
8
5
9
10
6
11
12
7
13
14
15
With a level numbering of the nodes, it is convenient to use a
vector S to represent a tree.
Recall that we use ranks to access elements in a vector. So we
can place the node v in a tree T at rank p(v).
1
2
3
4
5
10
1
2
3
7
11
4
5
14
7
10 11
15
14 15
We can also use a linked structure to represent a tree. In this
case, the node v of a tree T is represented by an object with
four references.
parent
left
right
element
root
5
size
Baltimore
Chicago
New York
Providence
Seattle
Class BTNode
public class BTNode implements Position {
private Object element;
private BTNode left, right, parent;
public BTNode() {}
public BTNode( Object o, BTNode u, BTNode v, BTNode w ) {
setElement( o );
setParent( u );
setLeft( v ):
setRight( w );
}
public Object element() { return element; }
public void setElement( Object o ) { element = o; }
public BTNode getLeft() { return left; }
public void setLeft( BTNode v ) { left = v; }
public BTNode getRight() { return right; }
public void setRight( BTNode v ) { right = v; }
public BTNode getParent() { return parent; }
public void setParent( BTNode v ) { parent = v; }
}
Interface Hierarchy for Positions
Position
element();
DNode
element(){…};
getNext(){…};
getPrev(){…};
setNext(){…};
setPrev(){…};
setElement(){…};
BTNnode
element(){…};
getLeft(){…};
getRight(){…};
setLeft(){…};
setRight(){…};
getParent(){…}
setElement(){…};
public class LinkedBinaryTree implements BinaryTree {
private Position root;
private int size;
public LinkedBinaryTree() {
root = new BTNode( null, null, null, null);
size = 1;
}
public int size() { return size; }
public boolean isEmpty() { return ( size == 0 ); }
public boolean isInternal( Position v ) {
return ((( BTNode )v ).getLeft() != null &&
(( BTNode )v ).getRight() != null );
}
public boolean isExternal( Position v ) {
return ((( BTNode )v ).getLeft() == null &&
(( BTNode )v ).getRight() == null );
}
public boolean isRoot( Position v ) {
return ( v == root());
}
… …
Also see the complete program for “LinkedBinaryTree” posted on
the home page of Dr. Yangjun Chen.
IspectableContainer
size
isElement
Elements
IspectablePositionContainer
positions
PositionContainer
swapElement
replaceElement
Tree
InspectableTree
root, parent, children, isRoot
isInternal, isExternal
InspectableBinaryTree
leftChild, rightChild, sibling
BinaryTree
imple.
LinkedBinaryTree
… …, replaceElement, swapElement, expandExternal,
removeAboveExternal
Basic Algorithms on Trees
Tree depth:
public static int depth( InspectableTree T, Position v ) {
if( T.isRoot( v ))
return 0;
else
return 1 + depth( T, T.parent( v ));
}
Tree height:
public static int height2( InspectableTree T, Position v ) {
if( T.isExternal( v ))
return v;
else {
int h = 0;
PositionIterator children = T.childrens(v);
while( children.hasNext())
h = Math.max( h, height2( T,
children.nextPosition() ));
return 1 + h;
}
}
Inorder tree traversal
Algorithm inorder(T,v):
if v is an internal node
assign the left child of the node v to u
call method inorder(T, u)
perform the “visit” action for node v
if v is an internal node
assign the right child of the node v to u
call method inorder(T, u)
r
T
u
A
v
W
X
B
Y
C
inorder(T, r)
inorder(T, u)
inorder(T, w)
if …
if …
if …
inorder(T, u)
“visit” r 6
inorder(T, w)
“visit” u 2
“visit” w 1
If …
If …
if …
inorder (T, a)
inorder (T, v)
inorder(T, v)
inorder(T, v)
inorder(T, x)
if …
if …
inorder(T, x)
“visit” v 4
If …
inorder (T, y)
“visit” x
if …
3
inorder(T, y)
if …
inorder(T, y)
“visit” y
5
if …
inorder(T, a)
if …
inorder(T, a)
inorder(T, b)
“visit” a 8
If …
inorder (T, c)
7
9
Inorder traversal based on Stack data structure
Algorithm Stack-control-inorder(T, v)
establish stack S;
S.push(v);
while (S is not empty) do
{u := S.pop();
if u is leaf or u is marked, visit u;
else {let v1 and v2 be the left and right child node of
v, respectively;
S.push(v2); mark u; S.push(u*); S.push(v1);
}
}
r
x
v*
y
r*
a
print(r)
a
u
r*
a
w
u*
v
r*
a
v*
y print(x)
r*
a
b
a*
c
u*
v print(w)
r*
a
y print(v)
r*
a
print(y)
r*
a
print(b)
a*
c
v print(u)
r*
a
print(a)
c
print(c)