Data structures#
Lists, stacks and queues, search trees, heaps, hash tables and graphs, with their running times.
About this chapter
The chapter goes from simple to structured. Lists, stacks and queues come first, with a few interview-style tricks (a stack that tracks its min, a queue made of two stacks). Then trees: plain binary search trees can degrade to depth \(n-1\) on sorted input, and AVL, red-black and splay trees are three ways to keep the depth logarithmic, either strictly or amortized.
Heaps give a priority queue stored in a plain array, and Huffman coding uses one to build prefix codes. Hash tables give constant-time find on average with no ordering, and most of that section is about collisions and the load factor \(\lambda\). The last section covers graphs: representations, topological sort, Dijkstra’s shortest paths, and Prim’s and Kruskal’s minimum spanning trees.
Lists#
The simplest containers: arrays, and linked nodes arranged as a queue (insert at the back, remove from the front) or a stack (push and pop at the top). The bullets are interview-style tricks built from these pieces.
Arrays and strings#
start by checking for null, length 0
ascii is 128, extended is 256
Queue - linkedlist#
has insert at back (enqueue) and remove from front (dequeue)
class Node {
Node next;
int val;
public Node(int d) { val = d; }
}
finding a loop is tricky, use visited
reverse a linked list
requires 3 ptrs (one temporary to store next)
return pointer to new end
Stack#
A stack is a linked list where push and pop both happen at the top node. Two stacks are enough to sort a stack or to simulate a queue, and storing the running min in each node gives a stack that reports its min.
class Stack {
Node top;
Node pop() {
if (top != null) {
Object item = top.data;
top = top.next;
return item;
}
return null;
}
void push(Object item) {
Node t = new Node(item);
t.next = top;
top = t;
}
}
sort a stack with 2 stacks
make a new stack called ans
pop from old
while old element is > ans.peek(), old.push(ans.pop())
then new.push(old element)
stack with min - each el stores min of things below it
queue with 2 stacks - keep popping everything off of one and putting them on the other
Trees#
Definitions first (height, depth, path length), then the binary search tree, where every key in the left subtree is smaller than the root and every key in the right subtree is larger. Find, insert and remove all cost the depth of the tree, which is why the balanced variants below exist.
Balanced binary trees are generally logarithmic
Root: a node with no parent; there can only be one root
Leaf: a node with no children
Siblings: two nodes with the same parent
Height of a node: length of the longest path from that node to a leaf
Thus, all leaves have height of zero
Height of a tree: maximum depth of a node in that tree = height of the root
Depth of a node: length of the path from the root to that node
Path: sequence of nodes n1, n2, …, nk such that ni is parent of ni+1 for 1 ≤ i ≤ k
Length: number of edges in the path
Internal path length: sum of the depths of all the nodes
Binary Tree - every node has at most 2 children
Binary Search Tree - Each node has a key value that can be compared
Every node in left subtree has a key whose value is less than the root’s key value
Every node in right subtree has a key whose value is greater than the root’s key value
void BST::insert(int x, BinaryNode * & curNode){ //we pass in by reference because we want a change in the method to actually modify the parameter (the parameter is the curNode *)
//left associative so this is a reference to a pointer
if (curNode==NULL)
curNode = new BinaryNode(x,NULL,NULL);
else if(x<curNode->element)
insert(x,curNode->left);
else if(x>curNode->element)
insert(x,curNode->right);
}
BST Remove
if no children: remove node (reclaiming memory), set parent pointer to null
one child: Adjust pointer of parent to point at child, and reclaim memory
two children: successor is min of right subtree
replace node with successor, then remove successor from tree
worst-case depth = n-1 (this happens when the data is already sorted)
maximum number of nodes in tree of height h is 2^(h+1) - 1
minimum height h ≥ log(n+1)-1
Perfect Binary tree - impractical because you need the perfect amount of nodes
all leaves have the same depth
number of leaves 2^h
AVL Tree#
AVL trees keep every node’s balance factor (right height minus left height) in \(\{-1, 0, 1\}\). An insert that pushes a node to \(\pm 2\) is fixed with one or two rotations on the way back up.
For every node in the tree, the height of the left and right sub-trees differs at most by 1
guarantees log(n)
balance factor := The height of the right subtree minus the height of the left subtree
“Unbalanced” trees: A balance factor of -2 or 2
AVL Insert - needs to update balance factors
same sign -> single rotation
-2, -1 -> needs right rotation
-2, +1 -> needs left then right
Find: Θ(log n) time: height of tree is always Θ(log n)
Insert: Θ(log n) time: find() takes Θ(log n), then may have to visit every node on the path back up to root to perform up to 2 single rotations
Remove: Θ(log n): left as an exercise
Print: Θ(n): no matter the data structure, it will still take n steps to print n elements
Red-Black Trees#
Red-black trees balance more loosely than AVL trees: five coloring rules, the last being that every path from a node down to a leaf has the same number of black nodes. Insert starts with a red node and fixes violations case by case, depending on the colors of the parent and uncle.
definition
A node is either red or black
The root is black
All leaves are black The leaves may be the NULL children
Both children of every red node are black Therefore, a black node is the only possible parent for a red node
Every simple path from a node to any descendant leaf contains the same number of black nodes
properties
The height of the right and left subtree can differ by a factor of n
insert (Assume node is red and try to insert)
The new node is the root node
The new node’s parent is black
Both the parent and uncle (aunt?) are red
Parent is red, uncle is black, new node is the right child of parent
Parent is red, uncle is black, new node is the left child of parent
Removal
Do a normal BST remove
Find next highest/lowest value, put it’s value in the node to be deleted, remove that highest/lowest node
Note that that node won’t have 2 children!
We replace the node to be deleted with it’s left child
This child is N, it’s sibling is S, it’s parent is P
Splay Trees#
Splay trees don’t store any balance information. Every access rotates the touched node up to the root, so a single operation can be slow but any sequence of \(m\) operations costs \(O(m \log n)\).
A self-balancing tree that keeps “recently” used nodes close to the top
This improves performance in some cases
Great for caches
Not good for uniform access
Anytime you find / insert / delete a node, you splay the tree around that node
Perform tree rotations to make that node the new root node
Splaying is Θ(h) where h is the height of the tree
At worst this is linear time - Θ(n)
We say it runs in Θ(log n) amortized time - individual operations might take linear time, but other operations take almost constant time - averages out to logarithmic time
m operations will take m*log(n) time
Other trees#
A grab bag of tree tasks: in-order traversal with an explicit stack instead of recursion, printing level by level, checking balance, and the trie, which stores a dictionary one character per node so that a prefix leads straight to its words.
to go through bst (without recursion) in order, use stacks
push and go left
if can’t go left, pop
add new left nodes
go right
breadth-first tree
recursively print only at a particular level each time
create pointers to nodes on the right
balanced tree = no 2 nodes differ in height by more than 1
(maxDepth - minDepth) <=1
trie is an infix of the word “retrieval” because the trie can find a single word in a dictionary with only a prefix of the word
root is empty string
each node stores a character in the word
if ends, full word
need a way to tell if prefix is a word -> each node stores a boolean isWord
Heaps#
A binary heap is an almost complete binary tree with each parent no larger than its children, so the minimum sits at the root. Because the tree is complete it fits in an array with no pointers. The section ends with compression, where Huffman coding builds its prefix codes from a min-heap of letter frequencies.
Priority Queue - Binary Heap is always used for Priority Queue
insert
inserts with a priority
findMin
finds the minimum element
deleteMin
finds, returns, and removes minimum element
perfect (or complete) binary tree - binary tree with all leaf nodes at the same depth; all internal nodes have 2 children.
height h, 2h+1-1 nodes, 2h-1 non-leaves, and 2h leaves
Full Binary Tree
A binary tree in which each node has exactly zero or two children.
Min-heap - parent is min
Heap Structure Property: A binary heap is an almost complete binary tree, which is a binary tree that is completely filled, with the possible exception of the bottom level, which is filled left to right
in an array - this is faster than pointers
left child: 2*i
right child: (2*i)+1
parent: floor(i/2)
pointers need more space, are slower
multiplying, dividing by 2 are very fast
Heap ordering property: For every non-root node X, the key in the parent of X is less than (or equal to) the key in X. Thus, the tree is partially ordered
Heap operations
findMin: just look at the root node
insert(val): put it at correct spot, percolate up
percolate - Repeatedly exchange node with its parent if needed
expected run time: ∑i=1..n 1/2^n∗n=2
deleteMin: put last leaf at root, percolate down
Remove root (that is always the min!)
Put “last” leaf node at root
Repeatedly find smallest child and swap node with smallest child if needed.
Compression
Lossless compression: X = X’
Lossy compression: X != X’
Information is lost (irreversible)
Compression ratio: \(\vert X\vert /\vert Y\vert \)
Where \(\vert X\vert \) is the number of bits (i.e., file size) of X
Huffman coding
Compression
Determine frequencies
Build a tree of prefix codes
no code is a prefix of another code
start with minheap, then keep putting trees together
Write the prefix codes to the output
reread source file and write prefix code to the output file
Decompression
read in prefix code - build tree
read in one bit at a time and follow tree
ASCII characters - 7 bits, 128 characters (extended ASCII uses 8 bits, 256 characters)
cost - total number of bits
“straight cost” - bits / character = log2(numDistinctChars)
Priority Queue Example
insert (x)
deleteMin()
findMin()
isEmpty()
makeEmpty()
size()
Hash tables#
A hash function maps a key to a slot. When two keys land in the same slot there are two fixes: keep a list in every slot (separate chaining), or probe other slots in a fixed order (open addressing). Either way the cost of a find is governed by the load factor \(\lambda\) = elements / table size.
java: load factor = .75, default init capacity: 16, uses buckets
string hash function: s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1] where n is length mod (table_size)
Standard set of operations: find, insert, delete
No ordering property!
Thus, no findMin or findMax
Hash tables store key-value pairs
Each value has a specific key associated with it
fixed size array of some size, usually a prime number
A hash function takes in a “thing” (string, int, object, etc.)
returns hash value - an unsigned integer value which is then mod’ed by the size of the hash table to yield a spot within the bounds of the hash table array
Three required properties
Must be deterministic
Meaning it must return the same value each time for the same “thing”
Must be fast
Must be evenly distributed
implies avoiding collisions
Technically, only the first is required for correctness, but the other two are required for fast running times
A perfect hash function has:
No blanks (i.e., no empty cells)
No collisions
Lookup table is at best logarithmic
We can’t just make a very large array - we assume the key space is too large
you can’t just hash by social security number
\(hash(s)=(\sum_{i=0}^{k−1} s_i * 37^i)\) mod table_size
you would precompute the powers of 37
collision - putting two things into same spot in hash table
Two primary ways to resolve collisions:
Separate Chaining (make each spot in the table a ‘bucket’ or a collection)
Open Addressing, of which there are 3 types:
Linear probing
Quadratic probing
Double hashing
Separate Chaining
each bucket contains a data structure (like a linked list)
analysis of find
The load factor, λ, of a hash table is the ratio of the number of elements divided by the table size
For separate chaining, λ is the average number of elements in a bucket
Average time on unsuccessful find: λ
Average length of a list at hash(k)
Average time on successful find: 1 + (λ/2)
One node, plus half the average length of a list (not including the item)
typical case will be constant time, but worst case is linear because everything hashes to same spot
λ = 1
Make hash table be the number of elements expected
So average bucket size is 1
Also make it a prime number
λ = 0.75
Java’s Hashtable but can be set to another value
Table will always be bigger than the number of elements
This reduces the chance of a collision!
Good trade-off between memory use and running time
λ = 0.5
Uses more memory, but fewer collisions
Open Addressing: The general idea with all of them is that, if a spot is occupied, to ‘probe’, or try, other spots in the table to use
3 Types:
General: pi(k) = (hash(k) + f(i)) mod table_size 1.Linear Probing: f(i) = i
Check spots in this order :
hash(k)
hash(k)+1
hash(k)+2
hash(k)+3
These are all mod table_size
find - keep going until you find an empty cell (or get back)
problems
cannot have a load factor > 1, as you get close to 1, you get a lot of collisions
clustering - large blocks of occupied cells
“holes” when an element is removed 2.Quadratic: f(i) = i^2
hash(k)
hash(k)+1
hash(k)+4
hash(k)+9
you move out of clusters much quicker 3.Double hashing: i * hash2(k)
hash2 is another hash function - typically the fastest
problem where you loop over spots that are filled - hash2 yields a factor of the table size
solve by making table size prime
hash(k) + 1 * hash2(k)
hash(k) + 2 * hash2(k)
hash(k) + 3 * hash2(k)
a prime table size helps hash function be more evenly distributed
problem: when the table gets too full, running time for operations increases
solution: create a bigger table and hash all the items from the original table into the new table
position is dependent on table size, which means we have to rehash each value
this means we have to re-compute the hash value for each element, and insert it into the new table!
When to rehash?
When half full (λ = 0.5)
When mostly full (λ = 0.75)
Java’s hashtable does this by default
When an insertion fails
Some other threshold
Cost of rehashing
Let’s assume that the hash function computation is constant
We have to do n inserts, and if each key hashes to the same spot, then it will be a Θ(n2) operation!
Although it is not likely to ever run that slow
Removing
You could rehash on delete
You could put in a ‘placeholder’ or ‘sentinel’ value
gets filled with these quickly
perhaps rehash after a certain number of deletes
hash functions
MD5 is a good hash function (given a string or file contents)
generates 128 bit hash
when you download something, you download the MD5, your computer computes the MD5 and they are compared to make sure it downloaded correctly
not reversible because when a file has more than 128 bits, won’t be 1-1 mapping
you can lookup a MD5 hash in a rainbow table - gives you what the password probably is based on the MD5 hash
SHA (secure Hash algorithm) is much more secure
generates hash up to 512 bits
Graphs#
A graph is a set of vertices and edges, stored as an adjacency matrix (fine when dense) or adjacency lists (better when sparse, like a road map). The algorithms that follow are topological sort for DAGs, BFS and Dijkstra for shortest paths, and Prim and Kruskal for minimum spanning trees. Dijkstra and Prim are both greedy, and Prim’s runs in \(\Theta(e \log v)\), the same as Dijkstra’s.
Edges are of the form (v1, v2)
Can be ordered pair or unordered pair
Definitions
A weight or cost can be associated with each edge - this is determined by the application
w is adjacent to v iff (v, w) \(\in\) E
path: sequence of vertices w1, w2, w3, …, wn such that (wi, wi+1) ∈ E for 1 ≤ i < n
length of a path: number of edges in the path
simple path: all vertices are distinct
cycle:
directed graph: path of length \(\geq\) 1 such that w1 = wn
undirected graph: same, except all edges are distinct
connected: there is a path from every vertex to every other vertex
loop: (v, v) \(\in\) E
complete graph: there is an edge between every pair of vertices
digraph
directed acyclic graph: no cycles; often called a “DAG”
strongly connected: there is a path from every vertex to every other vertex
weakly connected: the underlying undirected graph is connected
For Google Maps, an adjacency matrix would be infeasible - almost all zeros (sparse)
an adjacency list would work much better
an adjacency matrix would work for airline routes
detect cycle
dfs from every vertex and keep track of visited, if repeat then cycle
Topological Sort
Given a directed acyclic graph, construct an ordering of the vertices such that if there is a path from vi to vj, then vj appears after vi in the ordering
The result is a linear list of vertices
indegree of v: number of edges (u, v) – meaning the number of incoming edges
Algorithm
start with something of indegree 0
take it out, and take out the edges that start from it
keep doing this as we take out more and more edges
can have multiple possible topological sorts
Shortest Path
single-source - start somewhere, get shortest path to everywhere
unweighted shortest path - breadth first search
Weighted Shortest Path
We assume no negative weight edges
Dijkstra’s algorithm: uses similar ideas as the unweighted case
Greedy algorithms: do what seems to be best at every decision point
Dijkstra: v^2
Initialize each vertex’s distance as infinity
Start at a given vertex s
Update s’s distance to be 0
Repeat
Pick the next unknown vertex with the shortest distance to be the next v
If no more vertices are unknown, terminate loop
Mark v as known
For each edge from v to adjacent unknown vertices w
If the total distance to w is less than the current distance to w
Update w’s distance and the path to w
It picks the unvisited vertex with the lowest-distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor’s distance if smaller. Mark visited (set to red) when done with neighbors.
Shortest path from a start node to a finish node
We can just run Dijkstra until we get to the finish node
Have different kinds of nodes
Assume you are starting on a “side road”
Transition to a “main road”
Transition to a “highway”
Get as close as you can to your destination via the highway system
Transition to a “main road”, and get as close as you can to your destination
Transition to a “side road”, and go to your destination
Traveling Salesman
Given a number of cities and the costs of traveling from any city to any other city, what is the least-cost round-trip route that visits each city exactly once and then returns to the starting city?
Hamiltonian path: a path in a connected graph that visits each vertex exactly once
Hamiltonian cycle: a Hamiltonian path that ends where it started
The traveling salesperson problem is thus to find the least weight Hamiltonian path (cycle) in a connected, weighted graph
Minimum Spanning Tree
Want fully connected
Want to minimize number of links used
We won’t have cycles
Any solution is a tree
Slow algorithm: Construct a spanning tree:
Start with the graph
Remove an edge from each cycle
What remains has the same set of vertices but is a tree
Spanning Trees
Minimal-weight spanning tree: spanning tree with the minimal total weight
Generic Minimum Spanning Tree Algorithm
KnownVertices <- {}
while KnownVertices does not form a spanning tree, loop:
find edge (u,v) that is “safe” for KnownVertices
KnownVertices <- KnownVertices U {(u,v)}
end loop
Prim’s algorithm
Idea: Grow a tree by adding an edge to the “known” vertices from the “unknown” vertices. Pick the edge with the smallest weight.
Pick one node as the root,
Incrementally add edges that connect a “new” vertex to the tree.
Pick the edge (u,v) where:
u is in the tree, v is not, AND
where the edge weight is the smallest of all edges (where u is in the tree and v is not)
Running time: Same as Dijkstra’s: Θ(e log v)
Kruskal’s algorithm
Idea: Grow a forest out of edges that do not create a cycle. Pick an edge with the smallest weight.
When optimized, it has the same running time as Prim’s and Dijkstra’s: Θ(e log v)
unoptimized: v^2
Key ideas
A plain binary search tree costs its depth per operation, and sorted input makes that depth \(n-1\).
AVL and red-black trees keep the depth \(\Theta(\log n)\) with rotations, while splay trees only promise \(O(m \log n)\) for \(m\) operations.
A binary heap is an almost complete tree stored in an array, with children of slot \(i\) at \(2i\) and \(2i+1\), so findMin is the root and insert and deleteMin percolate along one path.
Huffman coding repeatedly merges the two lightest trees from a min-heap, so rare letters get long codes and no code is a prefix of another.
Hash tables give constant-time find on average but no ordering, and the load factor \(\lambda\) controls the cost of collisions under chaining or open addressing.
Adjacency lists suit sparse graphs, and Dijkstra and Prim are both greedy algorithms that grow a set one vertex at a time.