Data Structure

Lec-13 Concurrent Data Structures

& Review

* Part of the slides adopted from the companion slides for "The Art of Multiprocessor Programming” by Maurice Herlihy and Nir Shavit
* Part of the slides adopted from “Introduction to Algorithms” by Cormen T., Leiserson C., Rivest R. and Stein C.
Review: Sorting

• Heapsort
• Merge Sort
• Quicksort
• Bucket Sort
• Radix Sort
• Stable Sort
Review: Heapsort

11

13 12

16 19 18 66

33 57 22 24 40 37

• Step1: Build a Heap according to the input sequence

• Step2: Do DeleteMin() for n times and store the value in
a[0],a[1],…a[n-1]

How much storage do we use to do sorting?

Can we improve?
 Review: Heapsort

16 14 10 9 8
14 10 8 10 8 9 8 3 7 3
8 7 9 3 4 7 9 3 4 7 1 3 4 7 1 2 4 2 1 9
2 4 1 2 1 16 2 1416 10 1416 10 1416

7 4 3 2 1
4 3 2 3 2 1 1 3 2 3
1 2 8 9 1 7 8 9 4 7 8 9 4 7 8 9 4 7 8 9
10 1416 10 1416 10 1416 10 1416 10 1416

Running time of HeapSort? O(nlogn)

Review: Merge Sort

• a divide-and-conquer approach
• split the array into two roughly equal subarrays
• sort the subarrays by recursive applications of Mergesort
and merge the sorted subarrays
 Review: Merge Sort
At the beginning, a “So complicated!!, I’ll
5 2 4 7 1 3 2 6
MergeSort is called split them and call other
to sort: MergeSorts to handle.”

Both of them say “Still

Then 2 other complicated! I’ll split
MergeSorts are 5 2 4 7 1 3 2 6
them and call other
called to sort: MergeSorts to handle.”

Then 4 other All of them say “Still

MergeSorts are 5 2 4 7 1 3 2 6 complicated! I’ll split
called to sort: them and call other
MergeSorts to handle.”
Then 8 other
MergeSorts are All of them say ‘This
5 2 4 7 1 3 2 6
called to sort: is easy. No need to do
anything.’
 Review: Merge Sort
Then the first The first MergeSort
MergeSort succeeds
1 2 2 3 4 5 6 7
calls Merge to merge the
and returns. returned numbers

Then each of the 2 Both MergeSorts call

MergeSorts returns 2 4 5 7 1 2 3 6 Merge to merge the
the merged numbers. returned numbers

Then the 4 MergeSorts The 4 MergeSorts call

returns the merged 2 5 4 7 1 3 2 6 Merge to merge the
numbers. returned numbers

Then the 8
MergeSorts return. All of them say
5 2 4 7 1 3 2 6 ‘This is easy. No
need to do anything.’
 Review: Merge Sort
void merge(int x[ ], int lower_bound, int mid, int upper_bound)
-- merges 2 sorted sequences:
L: x[lower_bound], x[lower_bound+1], … , x[mid] L R
R: x[mid+1], x[mid+2] , …, x[upper_bound]

x = .. 2 4 5 7 1 2 3 6 ..
Step 1: Continuously copy the smallest x[lower_bound] x[upper_bound]
one from L and R to a result list x[mid]
until either L or R is finished.

Step 2: L may still have some numbers not

x = .. 22 44 55 77 11 22 33 66 ....
yet copied. So copy them in order. idLidLidLidLidRidRidRidRidR
Step 3: R may still have some numbers not
yet copied. So copy them in order. Result = .. 1 2 2 3 4 5 6 7 ..

idResult
idResult
idResult
idResult
idResult
idResult
idResult
idResult
Step 4: Copy the result list back to x.
Review: Quicksort
• A “partition-exchange” sorting method:
Partition an original array into: Eg. 25 10 57 48 37 12 92 86 33
(1) a subarray of small elements
=> 12 10 25 48 37 57 92 86 33
(2) a single value between (1) and (3) A possible arrangement:
simply use first element (ie.
(3) a subarray of large elements 25)
Then partition (1) and (3) independently for partitioning

using the same method.

x[0..N-1]
• For partitioning we need to choose a
value a. (simply select a = x[0]) Eg. 25 10 57 48 37 12 92 86 33

• During a partition process: pairwise => 12 10 25 48 37 57 92 86 33

exchanges of elements.
a
 Review: Quicksort
Original: 25 10 57 48 37 12 92 86 33
Partitioning: Select a = 25
Use 2 indices:
down up
25 10 57 48 37 12 92 86 33
Move down towards up until x[down]>25
(*)
Move up towards down until x[up]<=25

down up
25 10 57 48 37 12 92 86 33
down up
25 10 12 48 37 57 92 86 33 Swap
up down
Continue repeat (*) until up
25 10 12 48 37 57 92 86 33 crosses down (ie. down >= up)

12 10 25 48 37 57 92 86 33 up is at right-most of smaller
partition, so swap a with x[up]
Review: Quicksort
Original 25 10 57 48 37 12 92 86 33

12 10 25 48 37 57 92 86 33

=> 12 10 25 48 37 57 92 86 33
10 12 25 33 37 48 92 86 57

=> 10 12 25 33 37 48 92 86 57

10 12 25 33 37 48 57 86 92

=> 10 12 25 33 37 48 57 86 92

10 12 25 33 37 48 57 86 92

=> 10 12 25 33 37 48 57 86 92

=> 10 12 25 33 37 48 57 86 92 Sorted
Review: Bucket Sort
• Comparison-based sorting algorithms
require Ω(nlogn) time
• But we can sort in O(n) time using more
powerful operations
– When elements are integers in {0,…, M-1},
bucket sort needs O(M+n) time and O(M)
space
– When M=O(n), bucket sort needs O(2n)=O(n)
time
• Note: Some books call this counting sort
Review: Bucket Sort (cont.)
• Idea: Require a counter (auxiliary) array C[0..M-1] to
count the number of occurrences of each integer in
{0,…,M-1}
• Algorithm:
– Step 1: initialize all entries in C[0..M-1] to 0
– Step 2: For i=0 to n-1
o Use A[i] as an array index and increase C[A[i]] by
one
– Step 3: For j=0 to M-1
o Write C[j] copies of value j into appropriate places
in A[0..n-1]
Review: Bucket Sort (Example)
• Input: 3, 4, 6, 9, 4, 3 where M=10
0 1 2 3 4 5 6 7 8 9

Counter array A:

• Step 1: Initialization
0 1 2 3 4 5 6 7 8 9

0 0 0 0 0 0 0 0 0 0

• Step 2: Read 3
(A[3] = A[3] + 1) 0 1 2 3 4 5 6 7 8 9

0 0 0 1 0 0 0 0 0 0
• Read 4 0 1 2 3 4 5 6 7 8 9

(A[4] = A[4] + 1) 0 0 0 1 1 0 0 0 0 0

• Read 6 0 1 2 3 4 5 6 7 8 9

(A[6] = A[6] + 1) 0 0 0 1 1 0 1 0 0 0

• Read 9 0 1 2 3 4 5 6 7 8 9

(A[9] = A[9] + 1) 0 0 0 1 1 0 1 0 0 1

• Read 4 0 1 2 3 4 5 6 7 8 9

(A[4] = A[4] + 1) 0 0 0 1 2 0 1 0 0 1

• Read 3 0 1 2 3 4 5 6 7 8 9

(A[3] = A[3] + 1) 0 0 0 2 2 0 1 0 0 1
• Step 3: Print the result (from index 0 to 9)
• Result: 3, 3 0 1 2 3 4 5 6 7 8 9

0 0 0 2 2 0 1 0 0 1

• Result: 3, 3, 4, 4 0 1 2 3 4 5 6 7 8 9

0 0 0 0 2 0 1 0 0 1

• Result: 3, 3, 4, 4, 6 0 1 2 3 4 5 6 7 8 9

0 0 0 0 0 0 1 0 0 1

• Result: 3, 3, 4, 4, 6, 9 0 1 2 3 4 5 6 7 8 9

0 0 0 0 0 0 0 0 0 1
Review: Radix Sort
• Bucket sort is not efficient if M is large
• The idea of radix sort:
– Apply stable bucket sort on each digit (from
Least Significant Digit to Most Significant Digit)
• A complication:
– Just keeping the count is not enough
– Need to keep the actual elements
– Use a queue for each digit
Review: Radix Sort (Example) (1/3)
• Input: 170, 045, 075, 090, 002, 024, 802, 066
• The first pass
– Consider the least significant digits as keys and
move the keys into their buckets
0 170, 090
1
2 002, 802
3
4 024
5 045, 075
6 066
7
8
9
– Output: 170, 090, 002, 802, 024, 045, 075, 066
Review: Radix Sort (Example) (2/3)
• The second pass
• Input: 170, 090, 002, 802, 024, 045, 075, 066
– Consider the second least significant digits as
keys and move the keys into their buckets
0 002, 802
1
2 024
3
4 045
5
6 066
7 170, 075
8
9 090
– Output: 002, 802, 024, 045, 066, 170, 075, 090
Review: Radix Sort (Example) (3/3)
• The third pass
• Input: 002, 802, 024, 045, 066, 170, 075, 090
– Consider the third least significant digits as keys
and move the keys into their buckets
0 002, 024, 045, 066, 075, 090
1 170
2
3
4
5
6
7
8 802
9
– Output: 002, 024, 045, 066, 075, 090, 170, 802
(Sorted)
Review: Radix Sort Code (1/2)
// item is the type: {0,…,10d-1},
// i.e., the type of d-digit integers
void radixsort(item A[], int n, int d)
{
int i;
for (i=0; i<d; i++)
bucketsort(A, n, i);
}

// To extract d-th digit of x

int digit(item x, int d)
{
int i;
for (i=0; i<d; i++)
x /= 10; // integer division
return x%10;
}
Review: Radix Sort Code (2/2)
void bucketsort(item A[], int n, int d)
// stable-sort according to d-th digit
{
int i, j;
Queue *C = new Queue[10];
for (i=0; i<10; i++) C[i].makeEmpty();
for (i=0; i<n; i++)
C[digit(A[i],d)].EnQueue(A[i]);
for (i=0, j=0; i<10; i++)
while (!C[i].empty())
{ // copy values from queues to A[]
C[i].DeQueue(A[j]);
j++;
}
}
Review: Radix Sort: Time Complexity
• Assume d digits, each digit comes from {0,…,M-1}
• For each digit,
– O(M) time to initialize M queues,
– O(n) time to distribute n numbers into M
queues
• Total time = O(d(M+n))
• When d is constant and M = O(n), we can make
radix sort run in linear time, i.e., O(n).
Review: Stable Sort
• Definition: A stable sorting algorithm is one
that preserves the original relative order of
elements with equal key
• E.g., suppose the left attribute is the key
attribute Original relative order: (2,5) is before (2,2)

Initial array: (2,5) (3,2) (9,3) (2,2) (3,4)

Stable sort by
(2,5) (2,2) (3,2) (3,4) (9,3)
left attribute:

New relative order: (2,5) is still before (2,2)

Learning Objectives
1. Know insertion sort, Radix sort, Bucket
sort, Quicksort
2. Able to do heap sort manually
3. Catch the idea behind “merge-sort” and
able to use the idea to solve some other
related problems
4. Able to implement Various sorting
algorithms
D:1; C:1,2; B:1,2,3; A:1,2,3,4
Exercise 1
Suppose we are sorting an array of eight integers
using heapsort, and we have just finished some
deletions (either deleteMax or deleteMin) operations.
The array now looks like this: 16 14 15 10 12 27 28.
How many deletions have been performed on root of
heap?

a. 1
b. 2
c. 3 or 4
d. 5 or 6
Exercise 2
Which sorting algorithms is most efficient to sort
string consisting of ASCII characters?
a. Quick sort
b. Heap sort
c. Merge sort
d. Bucket Sort
Exercise 3
The maximum number of comparisons needed to
sort 9 items using radix sort is (assume each item is
a 5-digit decimal number):

a. 0
b. 45
c. 72
d. 360
e. 450
Exercise 4
Applying a QuickSort Program to sort numbers in
ascending order using the first element as pivot.
Let t1 and t2 be the number of comparisons made
by the Quicksort program for the inputs {1, 2, 3, 4, 5}
and {4, 1, 5, 3, 2} respectively. Which one of the
following is true?

a. t1=5
b. t1<t2
c. t1>t2
d. t1=t2
Outlines

• Basics of Concurrency
– Concepts and Terminology
– Amdahl’s Law
• Concurrent Data Structures
Microprocessor Trend Data
Parallel/Concurrent Programs

//independent iterations //loop-carried dependences

for(i = 0; i < L; i++) for(i = 0; i < L-1; i++)
{ {
A[i] = A[i] + B; A[i+1] = A[i] + B;
} }

unroll unroll

A[0] = A[0] + B; A[1] = A[0] + B;

A[1] = A[1] + B; A[2] = A[1] + B;
. ... ...
A[L-2] = A[L-2] + B; A[L-2] = A[L-3] + B;
A[L-1] = A[L-1] + B; A[L-1] = A[L-2] + B;
Basics of Concurrency

• Process
– has its own memory space and other resources.
– Difficult to communicate between processes:
Message Passing Communication

• Thread
– share all program features with that of their
parent process.
– Easy to communicate between threads:
Shared Memory Communication
 Processes and Threads

• A process is created by the

operating system.
• Requires a fair amount of
"overhead"
• Processes contain information
about program resources and
program execution state.
• Process ID, process group ID, user ID,
and group ID
• Environment
• Program instructions
• etc.

• Reference & Credit: Lawrence Livermore National Laboratory (LLNL),

• https://computing.llnl.gov/tutorials/parallel_comp/
• https://computing.llnl.gov/tutorials/pthreads/
 Processes and Threads (cont.)
• Threads use and exist within
process resources
• Duplicate only the bare essential
resources that enable them to
exist as executable code
• Changes made by one thread to
shared system resources will be
seen by all others
• E.g., closing a file
• Two pointers having the same
value point to the same data.

• Reference & Credit: Lawrence Livermore National Laboratory (LLNL),

• https://computing.llnl.gov/tutorials/parallel_comp/
• https://computing.llnl.gov/tutorials/pthreads/
Terms and definitions
• Concurrent Program
– Processes/threads which execute tasks in an ordering relative to
each-other that is not defined
– Essentially covers all multi-process/multi-threaded programs

• Parallelism
– Processes/threads that execute simultaneously
– Parallelism is usually applied to sections of a program

• Atomic action
– An action (instruction) that either completely happens without
interruption, or not at all
 Concurrency and Parallelism

Sequential

* From Rob Pike: Concurrency is not Parallelism

Example
• Let T1 and T2 be threads, X be a shared variable
between them
– X = 0; // initially
– T1::X++;
– T2::X++;
What’s the value of X?

• X++: read X; add 1; write X;

• the above instructions could occur in the following order:
– T1::read X; // reading 0
– T2::read X; // reading 0
– T1::add 1; // 0+1
– T2::add 1; // 0+1
– T1::write X; // writing 1
– T2::write X; // writing 1
Concurrent Example
• Let T1 and T2 be threads, X be a shared variable
between them
– X = 0; // initially
– T1::X++;
– T2::X++;
What’s the value of X?

• The non-determinism inherited from a concurrent

environment would cause desirable behavior

• Concurrent Data Structures

Concurrent Data Structures
• A concurrent data structure must abide by its sequential
counter-part's properties and guarantees when
operations are performed on it
• It must be 'thread-safe', no matter how many concurrent
calls are made to it, the data structure will never be
corrupted
• It should be free from any liveliness issues such as
Deadlock
• Just as sequential ones are constructed for abstraction,
concurrent data structures should be opaque in their
implementation
Properties
• Safety
– Assures that 'nothing bad will happen’,
for example, two calls to the 'push' function of a stack
should result in two elements being added to the stack

• Liveliness
– Assures that progress continues
– Deadlock
Concurrent Example
• Let T1 and T2 be threads, X be a shared variable
between them
– X = 0; // initially
– T1::X++;
– T2::X++;
What’s the value of X?

• must share properties and guarantees with the sequential

versions which they mimic, thus their operations must be
deterministic
• Mutual Exclusion and Locks
Mutual Exclusion and Locks

T1 T2

Lock(X)
X++ Wait and Query
Unlock(X)

Lock(X)
X++
Unlock(X)
Mutual Exclusion and Locks (cont.)
• allows only one thread to run over the data structure at
a time
• It essentially "locks out' all other threads from accessing
the object, thus 'mutex' and 'lock' are typically used
synonymously
• Varying algorithms exist for implementation, differing in
robustness and performance
• High overhead compared to other techniques and Can
cause problems such as Deadlock, Livelock, etc.
Other Concurrent Algorithms
• Implemented by a hardware operation
– Atomically combines a load and a store, e.g., Compare-And-
Swap (CAS)

• Lock-free
– While a given thread might be blocked by other threads, all
threads can continue doing other useful work without stalls

• Wait-free
– In addition to all threads continuing to do useful work, no
computation can ever be blocked by another computation
Concurrent Queue: Lock-based
class LockBasedQueue<T> {
int front, rear;
T[] items;
std::recursive_mutex lock;
LockBasedQueue(int capacity) {
front = 0; rear = 0;
items = new T[capacity];
} }

T dequeue(){
lock.lock();
if (front != rear){
T x = items[front % items.length];
front++;
lock.unlock();
return x;
}}
2-Thread Queue: Lock-free
class WaitFreeQueue {
int front = 0, rear = 0;
items = new T[capacity];

void enqueue(T x) {
while (rear-front == capacity);
// busy-wait
items[rear % capacity] = x; rear++;
}
T dequeue() {
while (rear == front); // busy-wait
T x = items[head % capacity];
front++;
return x;
}
}
Concurrent Linked List

X X
Coarse-Grained Locking
• A simple solution is to lock the entire list for each
operation, e.g., by locking the head

Works poorly with contention...

Void List::InsertNode(ListNode* newnode)
{
lock.lock();
ListNode* p=first;
while(p->next!=NULL && newnode->data>p->next->data)
p=p->next;
newnode->next=p->next;
p->next=newnode;
lock.unlock();
}

Void List::RemoveNode(ListNode* q)
{
lock.lock();
ListNode* p=first;
while(p->next!=q)
p=p->next;
p->next=q->next;
lock.unlock();
}

Simple and clearly correct!

Works poorly with contention
Fine-Grained Locking
• Split the list into nodes
– each node in the list has its own lock
– Methods that work on disjoint pieces need not
exclude each other
• Hand-over-hand locking: Use two locks when traversing
the list

X
Hand-Over-Hand Locking
• Assume two threads want to remove the nodes b and c
• One thread acquires the lock to a node, the other must
wait
• The same thread that acquired the lock can then lock the
next node
Void List::RemoveNode(ListNode* q)
{

ListNode* p1=first;
p1.lock();
ListNode* p2=p1->next;
p2.lock();

while(...){
… …
p1.unlock();
p1=p2;
p1.lock();
p2=p1->next;
p2.lock();
… …
}
p1.unlock();
p2.unlock();
}
Performance Analysis
• Speedup: ratio between sequential execution time and
concurrent execution time
sequential execution time
concurrent execution time

• Operations can be categorized into:

– Computations performed sequentially
– Computations performed concurrently.
– Concurrent Overhead

• Inherently sequential computations: 𝜎(𝑛)

• Potentially concurrent computations: 𝜑(𝑛)
• Communication operations: 𝜅(𝑛, 𝑝)
Speedup achieved for problem size n on p processors?
Speedup
• Concurrent Execution Time
!(#)
= 𝜎(𝑛) + + 𝜅(𝑛, 𝑝)
%
Amdahl’s Law

• Inherently sequential computations: 𝜎(𝑛)

• Potentially concurrent computations: 𝜑(𝑛)
• Communication operations: 𝜅(𝑛, 𝑝)

• Total Sequential Execution Time

= 𝜎(𝑛) + 𝜑(𝑛)
• Total Concurrent Execution Time
!(#)
= 𝜎(𝑛) + + 𝜅(𝑛, 𝑝)
%
Amdahl’s Law (cont.)

• Since 𝜅(𝑛, 𝑝) > 0

&(#)
• Let 𝑓 =
&(#) +!(#)

#
#"
" + $# ! " " ! !
 Illustration of Amdahl Effect

Speedup
n = 10,000

n = 1,000

n = 100
Processors

• Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Example 1

• 95% of a program’s execution time occurs over a data

structure that can be executed concurrently.
What is the maximum speedup we should expect from a
concurrent version of this program executing on 8
CPUs?

(
$ ! #"!
'"'# + )( " '"'#& % $
Example 2

• 20% of a program’s execution time is spent within

inherently sequential code.
What is the limit to the speedup achievable by a
concurrent version of the program?

% %
)*+ = =!
! #" $#" + (% ! $#"' & ! $#"
Tree-1
• Definition and Terminology
• Binary Tree
– Operations
– Recursive functions
– Traversal
• Binary Search Tree
– Insertion, deletion
• Binary Representation of General Tree
Definition and Terminology in Tree
Terminology:

Degree of a node The number of subtrees of a node

Terminal node or leaf A node of degree zero
Branch node or internal node A nonterminal node

Parent and Siblings Each node is said to be the parent of the roots of its
subtrees, and the latter are said to be siblings;
they are children of their parent.
A Path from n1 to nk a sequence of nodes n1,n2,…nk such that ni is the parent
of ni+1 for 0<i<k. The length of this path is the number
of edges on the path
Ancestor and Descendant If there is a path from n1 to nk, we say nk is the
descendant of n1 and n1 is the ancestor of nk .
Level or Depth of node The length of the unique path from root to this node.

Height of a tree The maximum level of any leaf in the tree.

Array Representation of Binary Tree
0 Children of a node at slot i:
A
1 2 Left(i) = 2i+1
B C
3 4 5 6 Right(i) = 2i+2
D E F G
7 8 9
H I J Parent of a node at slot i:
0 1 2 3 4 5 6 7 8 9 Parent(i) = ë (i-1)/2 û

A B C D E F G H I J ëxû: “Floor” The greatest integer less than x

éxù: “Ceiling” The least integer greater than x

For any slot i,

If i is odd: it represents a left son.
If i is even (but not zero): it represents a right son.
The node at the right of the represented node of i (if any), is at i+1.
The node at the left of the represented node of i (if any), is at i-1.
Linked Representation of Binary Tree
parent
• Each node can contain info, left, right, parent fields
• where left, right, parent fields are node pointers pointing info
to the node's left son, right son, and parent, respectively.
left right

• If the tree is always traversed in downward fashion class TreeNode

(from root to leaves), {
the parent field is unnecessary. private:
info
int info;
left right TreeNode* left;
T TreeNode* right;
};
left A right class Mytree
{
left B right left C right private:
TreeNode* root;
left E right__
__ left F right left G right }
__
__ __
__ __
__ __
__ __
__ __
__

• If the tree is empty, root = NULL; otherwise from root you can find all nodes.
• root->left and root->right point to the left and right subtrees of the root, respectively.
 Traversing Binary Tree
Traversing / Three principle ways:
walking through When the binary tree is empty, it is “traversed” by
doing nothing, otherwise:
A method of
examining the preorder traversal inorder traversal postorder traversal
nodes of the tree
systematically so Traverse the Traverse the
Visit the root
left subtree left subtree
that each node is
visited exactly
once. Traverse the Traverse the
Visit the root
left subtree right subtree
A
B C
D E F Traverse the Traverse the
Visit the root
right subtree right subtree
G H I

ABDCEGFHI DBAEGCHFI DBGEHIFCA

Traversing Binary Tree
Recursive Implementation
void Mytree::PreorderTraversal()
{
PreorderHelper(root);
}
void Mytree::PreorderHelper(TreeNode* node)
{
if (node!= NULL)
{
// visit the root
cout << node->info;
PreorderHelper(node->left); // traverse left subtree
PreorderHelper(node->right); // traverse right subtree
}
}

void Mytree::InorderTraversal()
{
InorderHelper(root);
}
 Binary Search Tree
q Application: Find all duplicates in a list of numbers.
Method 2 - Use a special binary tree (Binary Search Tree), T:
• Read number by number. W
Binarye’ll discuss
• Each time compare the number with the contents of T. S
in a latearch Tree
• If it is found duplicated, then output, otherwise add it to T. er topi
c.

Briefly, in a Binary Search Tree,

Each node of the tree contains a number. x
The number of each node is
• bigger than the numbers in the left subtree.
• smaller than the numbers in the right subtree.
Example: To find all duplicates in < 7 4 5 9 5 8 3 3>:
7 74 745 7459 74595 745958 7459583 74595833

7 7 7 7 7 7 7 7

4 4 4 9 4 9 4 9 4 9 4 9
5 5 5 5 8 3 5 8 3 5 8
 Binary Search Tree - Deletion
Delete a node in a BST: void Mytree::delete(TreeNode* node)

Case 1: Case 2: Case 3:

To delete a leaf node To delete a node that has To delete a node
1 subtree (left or right) that has 2 subtrees
8 8
8
3 11 3 11 3 11
1 5 9 14 1 5 9 14 1 5 9 14
___
__
__
6 101215 6 101215
6 10 12 15 7 13
7 13
7 13
• Set the parent node’s • Set the parent’s child pointer
child pointer to NULL to root of unwanted node’s
subtree (left or right). More complicated
Binary Search Tree - Deletion
Delete a node in a BST: void Mytree::delete(TreeNode* node)

Case 3:
To delete a node that has 2 subtrees
8 8
3 11 3 12
• Replace its value by its inorder
successor: 1 5 9 14 1 5 9 14
6 101215 6 101215
The inorder successor is the 7 13 7 13
leftmost node of right subtree.

8 8
• Delete the successor in turn: 3 12 3 12
1 5 9 14 1 5 9 14
6 101215 6 101315
7 13 7
Tree-2
• Game Tree
– MiniMax Rule
– α-β pruning
– Evaluation functions
• Heap
– Heap-order
– Heap operations
– Applications
The Minimax Algorithm
• Designed to find the optimal strategy or just best first
move for MAX

• Brute-force
1. Generate the whole game tree to leaves
2. Apply utility (payoff) function to leaves
3. Back-up values from leaves toward the root:
• a Max node computes the max of its child values
• a Min node computes the min of its child values
4. When value reaches the root: choose max value and the
corresponding move.

• Minimax
Search the game-tree in a DFS manner to find the value of the root
Alpha Beta Procedure

• Idea
– Do depth first search to generate partial game tree,
– Give evaluation function to leaves,
– Compute bound on internal nodes.
• Update α-β bounds
– α value for max node means that max real value is at least α.
– β for min node means that min can guarantee a value no more
than β

• Prune whenever α ≥ β
– Prune below a Max node whose alpha value becomes greater
than or equal to the beta value of its ancestors.
– Prune below a Min node whose beta value becomes less than
or equal to the alpha value of its ancestors.
Heap
• Structure Property
– A complete binary tree

• Heap-order Property
– The data in the root is smaller than the data in all the
descendants of the root.
Or
– The data in a node is smaller than the data in its
children
 ADT of Heap

Value:
#define TOTAL_SLOTS 100
A sequence of items that belong
class MyHeap
to some data type ITEM_TYPE
{
private:
Operations on heap h: int size;
1. void Insert(ITEM_TYPE e) int items[TOTAL_SLOTS];
public:
void Insert(int key);
2. /*return the value stored in the
root and then delete the root*/ int DeleteMin();
ITEM_TYPE DeleteMin() };
 Heap: Insert
To insert an item Step 1: Put the item at the first empty slot in the array
Step 2: Adjust the heap to satisfy heap-order property (float up)

11 11

13 18 insert 12 13 18

16 19 37 66 16 19 37 66

33 57 22 24 40 33 57 22 24 40 12
Heap: Insert
To insert an item Step 1: Put the item at the first empty slot in the array
Step 2: Adjust the heap to satisfy heap-order property (float up)

11 11

13 18 13 18
Float up
16 19 37 66 16 19 12 66

33 57 22 24 40 12 33 57 22 24 40 37
11

13 12

16 19 18 66

33 57 22 24 40 37
 Heap: DeleteMin
To delete the Min Step 1: Copy the last data to the root
Step 2: Adjust the heap to satisfy heap-order property (sink)

11 40

13 18 delete 11 13 18

16 19 37 66 16 19 37 66

33 57 22 24 40 33 57 22 24
Heap: DeleteMin
To delete the Min Step 1: Copy the last data to the root
Step 2: Adjust the heap to satisfy heap-order property (sink)

40 13

13 18 sink down 40 18

16 19 37 66 16 19 37 66

33 57 22 24 40 33 57 22 24

13 13

16 18 16 18

33 19 37 66 40 19 37 66

40 57 22 24 33 57 22 24
Tree-3
• AVL Tree
– Definition
– Rotations
• Splay tree
– Operations
AVL Trees

• Height of a tree = number of edges on a

longest root-to-leaf path
• Note: height of the tree below is
= max(hL, hR) +1

hL hR
L R
 Insertion
• Consider insert(u): only nodes along the path from
root to the point of insertion may be unbalanced
• Suppose node v unbalanced, 4 cases:
– Cases 1 & 4 are mirror image symmetries with respect to v
– Cases 2 & 3 are mirror image symmetries with respect to v

The root of v’s left subtree v The root of v’s right subtree

x y

A B C D
Case 1 Case 2 Case 3 Case 4
 Insertion
• In Case 1 (or Case 4), the insertion occurs on the
“outside” (i.e., left-left or right-right); it is fixed by a
single rotation
• In Case 2 (or Case 3), the insertion occurs on the
“inside” (i.e., left-right or right-left); it is handled by
double rotations
v
left right

x y
left right left right

A B C D
Case 1 Case 2 Case 3 Case 4
(Outside) (Inside) (Inside) (Outside)
Complexity
• Worst case time complexity of insertR(t, x):
– Local work requires constant time c
– At most 1 recursive call with tree height k-1 where k =
height of subtree pointed to by t
(Another approach)
– So, T(k) = T(k-1) + c
T(k)=T(k-1)+c
= T(k-2) + 2c

k equations
T(k-1)=T(k-2)+c
… T(k-2)=T(k-3)+c
= T(0) + kc …
= O(k) +) T(1)=T(0)+c
T(k)=T(0)+kc
• Worst case time complexity of insert(x)
= worst case time complexity of insertR(root, x)
= O(h)
where h = height of the whole tree
Theorem
• What is h (as a function of n)?
• Theorem: Every AVL-tree of height h has
≥ αh -1 nodes
– where α= (1+sqrt(5))/2 ≈1.618 (Golden ratio)
– Note: α2 = α+1
• Proof: (by induction on h)
Base Case (h=1)
– An AVL tree of height 1 has 1 node
– and 1 ≥ αh -1
 Splay Trees

• blind adjusting version of AVL trees

• doesn't care about differing heights of
subtrees
• amortized time for all operations is O(log n)
• worst case time is O(n)
• insert/find always rotates node to the root!

* Credits: https://courses.cs.washington.edu/courses/cse326/01au/lectures/SplayTrees.ppt
 Splay Tree Idea

10

You’re forced to make 17

a really deep access:

Since you’re down there anyway,

fix up a lot of deep nodes!

2 9

3
Splaying Cases

Node being accessed (n) is:

– Root
– Child of root
– Has both parent (p) and grandparent (g)
Zig-zig pattern: g à p à n is left-left or right-right
Zig-zag pattern: g à p à n is left-right or right-left
Disjoint Set
• Equivalence relations
• Equivalence classes
• Disjoint set Abstract Data Type
• Array Implementation
• Application——Maze generation
Array Implementation
• Array s[]
• s[i] stores the equivalence class name for i
0 1 2 3 4 5 6 7 8 9
• find(i): return s[i] worst case O( )
• Union(i,j): change all the value s[j] into s[i] in the array: O( )
• Example: For Find(), the return value is not
– Union(1,2) important.
– Union(3,1) The important thing is whether
Find(i) and Find(j) are the same
– Find(1): return __

0 1 2 3 4 5 6 7 8 9
0 1 1 3 4 5 6 7 8 9
0 3 3 3 4 5 6 7 8 9
Disjoint Set (Tree Implementation)

• Rule for Find(i)

– Follow upward links of node i until we can go no
further by following links
• Rule for Union(i,j)
Find(i): Find the root r(i) of the tree which i belongs to
Find(j): Find the root r(j) of the tree which j belongs to
r(i)->next=r(j)
Connecting rule: smaller tree to larger tree
shallower tree to deeper tree
Union-by-Height
• Guarantee all the trees have depth at most
O(log N), where N is the total number of
elements
• Running time for a find operation is O(log
N)
• The height of a tree increases one only
when two equally deep trees are joined.
Theorem 1

• Theorem 1: Union-by-height
guarantees that all the trees have
depth at most O(log N), where N is
the total number of elements.
• Lemma 1. For any root x, size(x) ≥
2height(x), where size(x) is the number
of nodes of x’s tree, including x.
Maze Generation
While the entrance cell is not connected to the exit cell
Randomly pick a wall (two adjacent cells i and j)
If (Find(i)!=Find(j))
Union(i,j) //Break the wall
What is suffixes?

T = innovation
Given a string ( or text ) S[1]= innovation
T = t1 t2 t3 … tn-1 tn S[2]= nnovation
then it has n suffixes, S[3]= novation
they are S[4]= ovation
Suffix(T,i) = S[i] S[5]= vation
= ti ti+1 ti+2 … tn S[6]= ation
for S[7]= tion
1≤i≤n S[8]= ion
S[9]= on
S[10]= n
Exact Pattern Matching

• How do you find the occurrence of a pattern P in

a text T?
– Test for each i whether P is a prefix of Suffix(T,i)
• Naïve implementation: O(PT) time, too slow!
• Knuth-Morris-Pratt ( 1977, SIAM J. Comput. )
– Key Point: ignore testing impossible suffixes
– O( P ) preprocessing P
• Calculate Next(k): which suffix should try next when the
first k chars of P are matched in the current suffix?
– O( P + T ) searching for any text T
– Will be covered in CS 4335
Graphs
• Terms & Definitions
• Representations of graphs
• Searching graphs
– BFS – Breath-first search
– DFS - Depth-first search
• Applications
Terms and definitions
• A graph G consists of:
– A non-empty set of vertices: V
– A set of edges: E
– E & V are related in a way that the vertices
on both ends of an edge are members of V
– Usually written as G = (V, E)

• Usually, Vertices are used to represent a

position or state meanwhile Edges are used to
represent a transaction or relationship
Representations of graphs
• When working with graph, we always perform one of the
following operation:
– Get the list of vertices connecting a given vertex.
– Is vertices A & B connected?
– What is the weight of edge from A to B?
– What is the in/out degree of a vertex?

• 3 standard representations
– Adjacency Matrix
– Adjacency List
Representations of graph
• Adjacency Matrix
– Use N*N 2D array to represent the weight (or T/F) of
one vertex to another

ABCD E FG
An undirected graph A 0010000
D B 0011000
F C 1101100
B
G D 0110010
E 0010011
C
A F 0001100
E
G 0000100
 Representations of graph
• Adjacency Matrix
– For undirected graph, only half of the array is used
– Fast query on edge weight & connection
– Total memory used: N2 (what if num of vertex = 10K?)
– Waste memory if the graph is sparse
i.e. #Edge is much smaller than half of (#Vertex)2
a large proportion of the array will be zero

– Slow when querying the list of neighboring vertices

if the graph is sparse
Representations of graph
• Adjacency List
 Representations of graph
• Adjacency List
– Use link list (or equivalent) to store the list of
neighboring vertex.
– Save memory if the graph is sparse
– Query on edge weight / connection can be slow
– Graph update is slow (especially if one have to
maintain order of neighbors)
– Enumeration of all neighbors is fast
Compressed Sparse Row (CSR)

• An efficient way to store sparse matrices or graphs

• The edge array is sorted by the source of each edge,
but contains only the targets for the edges.
• The vertex array stores offsets into the edge array,
providing the offset of the first edge outgoing from
each vertex.
Representations of graph
• If memory is sufficient and graph update is in-frequent,
can represent the graph in both methods at the same
time…
– If you need fast enumeration of neighbors together with fast
query of weight/connection
– e.g. List out all the neighbors of vertex A which do not connect to
vertex B or vertex C…
• Link-list can be replaced by 1D array with count
(enumeration of neighbor and query on degree will be fast)

• For un-weighted adjacency matrix, you may consider

other possibilities other than 0 & 1….
 Graph Searching
• To determine whether two vertices are connected
(indirectly via some intermediate)
– A is a relative of B, B is a relative of C, are A & C relative?
• To list out all members of a connected-component
– List out all the direct/indirect family members of A…
• To find the shortest path (of un-weighted graph)
from one vertex to another
– Travel from Shatin to Central with minimum number of
changes of transportation…

• TWO algorithms:
– DFS (Depth First Search)
– BFS (Breadth First Search)
DFS on Graphs
• Go as deep as you can
• Example DFS order (starting from 1):
– 1,2,4,6,8,5,3,7 2

– 1,5,7,3,2,8,4,6
• Using Stack to store nodes 1 3
– Put the starting node into the stack
4
– Repeat checking the top
• If top is unvisited
8
– Print this element
• If top has unvisited neighbors 5

– Push one of the neighbors on stack6 7

• If top has no unvisited neighbors
– Pop one element
BFS on Graphs
• Go as broad as you can
2
• Example BFS order (starting from 1):
– 1,2,5,4,8,3,7,6
– 1,5,2,7,3,8,4,6 1 3

• Using Queue to store nodes

4
– Put the starting node into queue
– Repeat the following “Remove”
8
• Remove:
5
– Remove a node from the queue
6
– Print this element 7
– Insert all his unvisited (haven’t been in the queue)
neighbors into the queue
 Spanning Trees

• Given (connected) graph G(V,E),

a spanning tree T(V’,E’):
– Is a subgraph of G; that is, V’ Í V, E’ Í E.
– Spans the graph (V’ = V)
– Forms a tree (no cycle);
– So, E’ has |V| -1 edges

Credits:
The CSE373 Web: © 1993-2022, Department of Computer Science and
Engineering, Univerity of Washington.
Minimum Spanning Trees

• Edges are weighted: find minimum cost

spanning tree
• Applications
– Find cheapest way to wire your house
– Find minimum cost to send a message on the
Internet
Review
• Preparations
– Worst case analysis
– Order of growth (Big-Oh)
– Program Complexity
– Abstract Data Types (for applications)
• Linked List
– How to change links
– List Traversal
• Stack & Queue
– Basic property
– Priority Queues
Review
• Hash
– Hash functions
– Open addressing (linear, quadratic, double)
– Rehashing
• Trees
– Binary tree
– Binary search tree
– Traversal (preorder, inorder, postorder)
– Recursive functions on binary trees
• Tree Applications
– Game tree (choosing the best move and pruning; alpha-
bata)
– Heap (how to insert into a heap and delete)
– Balanced binary search tree: AVL tree, splay tree
Review

• Disjoint Set
– Equivalence relation
– Tree Implementation
– Union and Find operations
– Maze Generation
• Suffix Tree/Array
• Graph
– Adjacency matrix
– BFS and DFS
– Minimum spanning tree
– Shortest Path
Review
• Sorting
– Binary search tree + inorder traversal
– Heap sort
– Merge sort
– Quicksort
– Bucket Sort
– Radix Sort
…
From CS3334, Hope
• You can learn new data structures or modify the
data structures you learned for your needs by
yourself
– A lot of materials on the web
– A lot of references in books
– Your motivation is most important

• Based on the running time analysis, you can choose

suitable data structures to use in your application
guaranteeing the worst-case performance
Final Exam
• There are 12 questions in TWO sections
– Section A: answer all 9 questions
– Section B: try 2 from 3 questions
Exercises 1
Explain whether the following statements
are correct or not.

(a) The running time of Merge sort and

Radix sort are both O(nlogn)
(b) The AVL tree can ensure the data in the
root is smaller than the data in all the
descendants of the root.
Exercises 2
Complexity Analysis
(A)
int count = 0;
for (int i=n/2; i<=n; i++)
for (int j=1; j+n/2<=n; j = j++)
for (int k=1; k<=n; k = k * 2)
count++;

(B) T(n)= 2T(n/2) +n; T(1) = 1

Exercises 3
Tree Traversal
Inorder: 3, 12, 6, 4, 7, 10, 11, 5, 2, 8
Preorder: 10, 12, 3, 4, 6, 7, 5, 11, 2, 8
Postorder:?

Preorder sequence: A B D E C F H I G
Inorder Sequence: B E A H F I C G D
Postorder:?
Exercises 4
AVL tree
Showing the final result of inserting the following numbers
into an AVL tree.
{12, 28, 8, 36, 30, 17, 45}
Exercises 5
Sorting:
Given an unsorted input array
[170, 45, 75, 90, 802, 24, 2, 66],
you need to use radix sort to get the corresponding sorted
array in ascending order. Write down the resulted array in
each step (i.e., after running on a place).

Step 1: 170, 90, 802, 2, 24, 45, 75, 66

Step 2: 802, 2, 24, 45, 66, 170, 75, 90
Step 3: 2, 24, 45, 66, 75, 90, 170, 802
Exercises 6
Given the following game tree, which node(s) can be
pruned?
Exercises 7
Coding:
Write down the codes for Counting Non-Leaf nodes in a
Binary Tree. You can write other functions to help you to
implement the nonleaf() function.
class TreeNode {
public:
int value;
TreeNode *left, *right;
};

Class Tree
{
public:
TreeNode* root;
int nonleaf();
...
}
Exercises 7
Coding:

int nonleaf() {return countNonLeafNodes(root);}

int countNonLeafNodes(TreeNode* node) {

if (node == nullptr || isLeafNode(node))
return 0;

return 1 + countNonLeafNodes(node->left) +
countNonLeafNodes(node->right);
}

bool isLeafNode(TreeNode* node) {

return node->left == nullptr && node->right == nullptr;
}
Pay attention to the Dues

• Don't wait until the last minute! Time flies!

– Course Project: Dec 5 at 11:59pm
– Assignment Questions: Dec 5 at 11:59pm

My office hours next week will be:

– Wed, Dec 4, 2024, 11:00am – 12:30pm
– Thur, Dec 5, 2024, 11:00am – 12:30pm
– https://calendar.app.google/aZrwMSCWAqZiuod69
Or email me to schedule a meeting.
And TLQ, Please ۶(◕‿◕(٩