Lecture 2 - Notes

January 7, 2016

Encoding Trees

Mark internal nodes with ones and leaves with zeros. We then do a preorder traversal. This gives us a sequence, e.g.,

$11100011000$

This tree sequence let's us create a well formed parenthesis string.

$\underset{1}(\underset{1}(\underset{1}(\underset{0})\underset{0})\underset{0})\underset{1}(\underset{1}( \underset{0}) \underset{0})$

This parenthesis string is unique to that tree.

Union Find

Given a set of $N$ object we would like to,

Connect two objects
Test if theirs a path between two objects

To find out if a static graph is connected you could use DFS or BFS which is $O(|V| + |E|)$.

In this dynamic environment we are adding edges to the graph. We assume "is connected to" to be an equivalence relation. We will therefor use sets to encapsulate components, when creating edges we will check which set each node is in then join the two sets.

class UF
{
    UF (int n)

    void union(int p,  int q)

    int find(int p)

    boolean connected(int p, int q)
}

Quick Find

Data structure

Integer array id[] of length N
Interpretation id[p] is the id of the component containing p

Example

          0 1 2 3 4 5 6 7 8 9
    id = [0,1,1,8,8,0,0,1,8,8]

So 0, 5 and 6 are connected, etc.

find(p): Lookup p by index
connected(p,q): Do p and q have the same id?
union(p,q): Change all entries were id is id[p] to id[q]

Quick Union

Data Structure

Integer array id[] of length N
Interpretation id[i] is the parent of i
Root of i is id[id[...id[i]...]]

          0 1 2 3 4 5 6 7 8 9
    id = [0,1,9,4,9,6,6,7,8,9]

find(p): What is the root of p
connected(p,q): Do p and q have the same root?
union(p,q): Set the id of p's root to the id of q's root

Issues

Both of the these operation are too expensive,

Algorithm	intialize	union	find	connected
Quick Find	$O(N)$	$O(N)$	$O(1)$	$O(1)$
Quick Union	$O(N)$	$O(N)$	$O(N)$	$O(N)$

Quick Find

Unions are expensive
Trees are flat but it's expensive to eep them flat

Quick Union

Trees can get very tall
Find/connect is expensive

Weighted Quick Union

Modify Quick Union to avoid tall trees
Keep track of the size of each tree
Balance by linking smaller tree to root of larger tree

Data Structure

Same as Quick Union but maintain an extra array sz[i] that counts the number of objects rooted at i.

find(p)/connected(p,q): Same as Quick Union
Union(p,q): Link the smaller tree to the larger tree, update sz[]

Efficiency

Algorithm	initialize	union	find	connected
Quick Find	$O(N)$	$O(N)$	$O(1)$	$O(1)$
Quick Union	$O(N)$	$O(N)$	$O(N)$	$O(N)$
Weighted Quick Union	$O(N)$	$O(\lg{N})$	$O(\lg{N})$	$O(\lg{N})$