ALGORITHMS AND DATA STRUCTURES

Prof. Massimo Poncino

Lez 8 - Dynamic sets and dictionaries

Dynamic sets and

Algorithms dictionaries

Outline

Î Dynamic sets
and dictionaries
Dynamic sets
and dictionaries
Î Implementations of
dictionaries
Æ Binary Search Trees

Dynamic sets Dynamic sets

Sets managed by algorithms
are not fixed The set from which the keys
are taken can be ordered
Dynamic
May change over time Some operations on
sets are meaningful
Elements of the set are only if they are
objects containing: ordered
A key value
Satellite data

Copyright © Università Telematica Internazionale UNINETTUNO

1
 ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 8 - Dynamic sets and dictionaries

Dynamic sets: operations Dynamic sets: operations

Queries
Return information Search(S,k)
about the set Returns the element with key
k in S or NULL if an element
Modifying operations with key k is not in S
Change the set

Dynamic sets: operations Dynamic sets: operations

Insert (S,x) Is S is totally ordered
Adds element x to S Minimum (S)
If successful return Returns the element in S
true, false otherwise with smallest key value,
Delete (S,x) or NULL if S is empty
Removes the element Maximum (S)
x from S Returns the element in S
If successful return with largest key value, or
true, false otherwise NULL if S is empty

Dynamic sets: operations Dynamic sets: operations

Is S is totally ordered Auxiliary operations
Predecessor (S,k)
Returns the element in S with IsEmpty (S)
largest key value <k, or NULL Returns true is set if
if no such element exists empty, false otherwise
Successor (S,k)
Returns the element in S with Clear (S)
smallest key value >k, or Resets the set
NULL if no such element to the empty set
exists

Copyright © Università Telematica Internazionale UNINETTUNO

2
 ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 8 - Dynamic sets and dictionaries

Dynamic sets: operations Dictionaries

Auxiliary operations
A dynamic set that provides
Size (S) only the search(), insert ()
and delete () operations is
Returns the called a dictionary
cardinality of the set

List (S) When the set is totally

ordered the dictionary
List the elements is called ordered
of the set

Implementation
of dynamic sets
Arrays (sorted/unsorted)

Implementation Linked lists (sorted/unsorted)

of dynamic sets Priority Queues
Queue
Stack
Other?

Implementation
of dynamic sets
Search Insert Delete
Array Ο(n) Ο(1) Ο(n)
Sorted array Ο(logn) Ο(n) Ο(n) Binary search
List Ο(n) Ο(1)* Ο(n)
Sorted list Ο(n) Ο(n) Ο(n)
trees (BSTs)
Queue Ο(n) Ο(1)* Ο(1)*
Stack Ο(n) Ο(1)* Ο(1)*
Priority
queue (heap) Ο(n) Ο(logn) Ο(logn)

Copyright © Università Telematica Internazionale UNINETTUNO

3
 ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 8 - Dynamic sets and dictionaries

Binary search tree (BST) Binary search tree (BST)

Tree-based implementation
of an ordered dictionary
Binary tree In the best case it is
possible to arrange n keys
Achieves Ο(h) complexity in a tree of height h=logn
for search(), insert (),
and delete ()
h = tree height

Binary search tree (BST) Binary search tree (BST)

property property
For each node with key x For each node with key x
X
Nodes in the left
subtree have keys ≤ x

Nodes in the right

subtree have keys ≥ x
≤x ≥x

BSTs: example BSTs: basic operations

6 Binary tree ¨ operations

intrinsically recursive
2 8
One recursive call per child
1 4 12
Most primitives are however
iterative for efficiency
3 9 15 reasons

Copyright © Università Telematica Internazionale UNINETTUNO

4
 ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 8 - Dynamic sets and dictionaries

BST: search() BST: search() pseudocode

Works as in binary search Search(T,k)
Search(T,k)
{
Given x if ( T==NULL)
(T==NULL)
T==NULL)
return 0
If x < key of the root, if (k < key))
search left sub-tree Search (left[T
(left[T], k)
(left[T],
if (k> key(T))
If x > key of the root, Search(
Search(right[T], k)
right[T],
Search(right[T],
search right sub-tree if (k= key(T))
return 1
If x = key of the root, found }

BST: analysis of search() BST: analysis of search()

Master method
Divide-and-conquer algorithm
a=1 b=2 nlog
log221
1
= n00 = Θ(1)

Assuming a perfectly
f(n) = Θ(1)
balanced tree
Since f(n) and nlogbba have same
T(n) = T(n /2) + Θ(1) order
T(n) = Ο(logn)

BST: iterative search() BST: analysis of search()

Search (T, k)
{
while (T !=NULL)
!=NULL) Searching an item implies in
if (k = key(T)) the worst case traversing the
return 1 tree from the root to a leaf
else if (k < key(T))
key(T))
T ← left[T]
else
T ← right[T] T(n) = Ο(h)
endwhile
return 0
}

Copyright © Università Telematica Internazionale UNINETTUNO

5
 ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 8 - Dynamic sets and dictionaries

BST search(): example BST: insert()

Searching node with key “9” A new node is always
6 9>6 inserted as a leaf in a BST

2 8 9>8
Two-step insertion
Search of the node v which
will become parent of the
1 4 12 9 < 12 new node
Insertion of new node u as
3 9 15 left or right child of v

BST: insert() pseudocode BST: insert() pseudocode

-Insert (T, u
Tree-
Tree
Tree-Insert )
u) // Step2:Insert
{ (v is where to insert)
(v insert)
y ← NULL;
NULL; x ← root(T) if (v = NULL) then
// Step 1: find the position // empty tree (case I)
while x != NULL do
root[T] ← u
y ← x else
if ( key[u]
key[u] < key[x]
(key[u] key[x])
) then
key[x])
x ← left[x] // non-
non-empty tree (case II)
non-empty
else if ( key[u]
key[u] < key[v]
(key[u] key[v])
)
key[v])
x ← right[x] left [v] ← u
endwhile else
v ← y right[v] ← u
endif
}

BST: analysis of insert() BST insert(): example

Must traverse a path u T

from root to a leaf
Empty tree
5 NULL
T(n) = Ο(h)

Copyright © Università Telematica Internazionale UNINETTUNO

6
 ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 8 - Dynamic sets and dictionaries

BST insert(): example BST insert(): example

u T
5 6
u T root[T] = u
2 8
Empty tree
5 The newly inserted
node becomes the root 1 4 12

3 9 15

BST insert(): example BST insert(): example

u y T u T
5 6 5<6 5 6 5>2
x Search y Search
2 8 proper 2 8 proper
position position
x
1 4 12 1 4 12

3 9 15 3 9 15

BST insert(): example BST insert(): example

u T T
5 6 5>4 6
Search
2 8 proper 2 8
position:
y v ok v
1 4 12 1 4 12
x u
3 9 15 3 5 9 15
null

Copyright © Università Telematica Internazionale UNINETTUNO

7
 ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 8 - Dynamic sets and dictionaries

Algorithms

Copyright © Università Telematica Internazionale UNINETTUNO