EDITOR’S NOTE: I highly recommend watching videos/demos of these topics
and/or playing around with these algorithms and concepts yourself, the definitions and examples in
text form won’t be enough to fully understand the concept behind these algorithms - they are merely
here to provide a rough blueprint
try and do the tutorial exerices, solve old exams or use a tool like TUMGAD to automatically generate exercises
and corresponding solutions
5n^2-7n \in
\mathcal{O}(n^2)5n2−7n∈O(n2), but also \mathcal{O}(n^3),
\mathcal{O}(n^4)...O(n3),O(n4)... (also included
in “greater” sets, since \mathcal{O}O
defines the upper bound)
5n^2-7n \in
\Omega(n^2)5n2−7n∈Ω(n2), but also \Omega(n)Ω(n) (also included
in “lesser” sets, since \OmegaΩ defines the
lower bound)
5n^2-7n \in
\Theta(n^2)5n2−7n∈Θ(n2) (only one, since
\ThetaΘ defines the
intersection between the two previous sets!)
placeholders:
instead of g(n) \in O(f(n))g(n)∈O(f(n)), one can write
g(n) = O(f(n))g(n)=O(f(n))
instead of f(n) + g(n)f(n)+g(n) for g(n) \in
o(h(n))g(n)∈o(h(n)), one can write
f(n) + o(h(n))f(n)+o(h(n))
instead of O(f(n)) \subseteq O(g(n))O(f(n))⊆O(g(n)), one can write
O(f(n)) =
O(g(n))O(f(n))=O(g(n))
if the result of \lim_{n \to \infty}limn→∞
is undefined, e.g. \frac{0}{0}00,
0 \cdot \infty0⋅∞, \infty - \infty∞−∞, \frac{\infty}{\infty}∞∞,
0^000
or \infty^0∞0,
use L’Hospital’s rule
amortized analysis: analyze costs (time, memory) of an algorithm by averaging out
the worst operations over time for a sequence of nn operations (\sigma_1, ... ,
\sigma_n)(σ1,...,σn) (upper bound of actual
runtime TT)
e.g. for a dynamic array, when “pushing” a new element in a full array, the array size needs
to be increased (doubled, for the sake of simplicity), but this only happens very
rarely, so giving the method a runtime of O(n)O(n) is quite pessimistic
instead, using amortized costs, we classify the runtime as O(1)O(1), since that
is what happens most of the time
lecture method:
S = \{\sigma_1, ...,
\sigma_n\}S={σ1,...,σn}: set of operations
T(\sigma)T(σ): runtime /
upper bound of an operation \sigma \in Sσ∈S
map data (keys) to fixed-value sizes (values) using a
hash function to uniquely identify said data in a hash table
in other words, convert keys into other values and store these new values at corresponding
positions inside a table
implemented using a dictionary (stores a set of elements where each element is identified via a
unique key)
universe UU of keys
with |U| = N∣U∣=N (some
very large positive integer)
V \subseteq UV⊆U: subset of
actually used keys with |V| =
n∣V∣=n significantly
smaller than NN
general idea: let TT be an array
with space for mm elements (hash
table) and a function h : U
\to \{0, ..., m-1\}h:U→{0,...,m−1}
be used to map key to array index (hash function)
probability of hash collisions for equally spread out hash positions: 1 - o(1)1−o(1)
// implementing a hash table with hash function
// only for dynamic dictionaries
void insert(Object e){
T[h(key(e))] = e;
}
// only for dynamic dictionaries
void remove(Key k){
T[h(k)] = null;
}
// for static and dynamic dictionaries
Object find(Key k){
return T[h(k)];
}
// implementing a hash table with hash function // only for dynamic dictionariesvoidinsert(Object e){
T[h(key(e))] = e;
}
// only for dynamic dictionariesvoidremove(Key k){
T[h(k)] = null;
}
// for static and dynamic dictionaries
Object find(Key k){
return T[h(k)];
}
idea: avoid collisions (different keys mapped to the same value) by having
each cell of the hash table point to a linked list containing the hashed values
in other words, the hash table is an array, where each entry is a linked
list
mm:
size of hash, such that each hash function returns a hash code in range \{0,1,...,m-1\}{0,1,...,m−1}
a family of hash functions is cc-universal,
if the probability of a hash collision between two keys xx and yy when
randomly chosing a hash function h \in
Hh∈H is less
than or equal to \frac{c}{m}mc
in other words: |\{h \in H : h(x) = h(y)\}| \leq
\frac{c}{m}|H|∣{h∈H:h(x)=h(y)}∣≤mc∣H∣ for all x \neq yx=y
formally: \Pr[h(x) = h(y)] \leq \frac{c}{m}Pr[h(x)=h(y)]≤mc
for all x \neq yx=y
(1-)universal family: cc-universal family of
hash functions for c =
1c=1
in other words: |\{h \in H : h(x) = h(y)\}| \leq
\frac{1}{m}|H|∣{h∈H:h(x)=h(y)}∣≤m1∣H∣ for all x \neq yx=y
formally: \Pr[h(x) = h(y)] \leq \frac{1}{m}Pr[h(x)=h(y)]≤m1
for all x \neq yx=y
(*) how to determine, whether or not a given family is universal:
statement: you are given a hash table of size mm
(herem=4m=4), a set of keys (*here
A,B,C,D,EA,B,C,D,E)
and the given mappings for each hash function h_ihi
example:
h_1: A \mapsto 1, B \mapsto 1, C
\mapsto 1, D \mapsto 3, E \mapsto 3h1:A↦1,B↦1,C↦1,D↦3,E↦3
h_2: A \mapsto 2, B \mapsto 2, C
\mapsto 0, D \mapsto 0, E \mapsto 1h2:A↦2,B↦2,C↦0,D↦0,E↦1
h_3: A \mapsto 3, B \mapsto 1, C
\mapsto 0, D \mapsto 3, E \mapsto 2h3:A↦3,B↦1,C↦0,D↦3,E↦2
h_4: A \mapsto 0, B \mapsto 2, C
\mapsto 1, D \mapsto 2, E \mapsto 1h4:A↦0,B↦2,C↦1,D↦2,E↦1
h_5: A \mapsto 1, B \mapsto 3, C
\mapsto 1, D \mapsto 2, E \mapsto 0h5:A↦1,B↦3,C↦1,D↦2,E↦0
h_6: A \mapsto 3, B \mapsto 2, C
\mapsto 0, D \mapsto 1, E \mapsto 3h6:A↦3,B↦2,C↦0,D↦1,E↦3
question: is the hash family H_iHi
(here H_1 = \{h_1, h_2, h_4, h_5\}H1={h1,h2,h4,h5}) universal?
step 1: note collisions between each possible pair for
each hash function
A / B: h_1, h_2A/B:h1,h2
A / C: h_1, h_5A/C:h1,h5
A / D: \emptysetA/D:∅
A / E: \emptysetA/E:∅
B / C: h_1B/C:h1
B / D: h_4B/D:h4
B / E: \emptysetB/E:∅
C / D: h_2C/D:h2
C / E: h_4C/E:h4
D / E: h_1D/E:h1
step 2: check that the number of collisions at most 1 for
any given pair; if not, the function is not 1-universal, but
at least cc
universal with cc
being the number of collisions
since |h \in H_1 : h(A) = h(B)| = |\{h_1,
h_2\}| = 2∣h∈H1:h(A)=h(B)∣=∣{h1,h2}∣=2, the
family H_1H1
is cc-universal
for c \geq 2c≥2
parameterized hash families: a hash function h_b = b \cdot x \mod mhb=b⋅xmodm defines a family of
hash functions H =
\{h_b \; | \; b \in \Z\}H={hb∣b∈Z}
bb can be
freely chosen, e.g. h_2 = 2x \mod mh2=2xmodm, h_{-400} = -400x \mod
mh−400=−400xmodm
if mm is a
prime number, then H = \{h_a : a \in \{0, ... , m-1\}^k \}H={ha:a∈{0,...,m−1}k} with h_a(x) = a \cdot x \mod
mha(x)=a⋅xmodm is a
universal family of hash functions
lecture example - hashing an integer xx:
choose prime table size mm
e.g. m = 269m=269
let w = \lfloor \log_2
m\rfloorw=⌊log2m⌋
e.g. w = \lfloor \log_2 269\rfloor = 8w=⌊log2269⌋=8
separate bitstring xx (binary
representation) into kk
equal parts with ww
bits each
e.g. k = 4k=4, since 4 \cdot 8 =
324⋅8=32
interpret each part as an integer x_i \in [0, ..., 2^w-1]xi∈[0,...,2w−1]
e.g. x_i \in [0, ..., 255]xi∈[0,...,255] (an
unsigned byte)
interpret key xx to compute
hash value of as kk-vector
of x_ixi,
with x = (x_1, ..., x_k)^T, x_i
\in \{0, ..., 2^w-1\}x=(x1,...,xk)T,xi∈{0,...,2w−1}
e.g. x = (11, 7, 4, 3)^Tx=(11,7,4,3)T
define some vector a = (a_1, ..., a_k)^T, a_i \in \{0, ...,
m-1\}a=(a1,...,ak)T,ai∈{0,...,m−1}
e.g. a = (2,4,261,16)^Ta=(2,4,261,16)T
scalar product of aa and xx is a \cdot x = \sum_{i =
1}^ka_ix_ia⋅x=∑i=1kaixi
define h_a : x \to \{0, ..., m-1\}ha:x→{0,...,m−1} as h_a(x) = a \cdot x \mod
mha(x)=a⋅xmodm (scalar
product of aa and
xx,
product modulo mm)
static dictionary SS of
length nn with keys
k_1, ..., k_nk1,...,kn
H_mHm:
cc-universal
family of hash functions to \{0, ... m-1\}{0,...m−1}
C(h)C(h): number of
collisions in SS for
hh for every
pair (x,y)(x,y)
expected number of collisions: E[C(h)] \leq \frac{cn(n-1)}{m}E[C(h)]≤mcn(n−1)
for at least half of the functions, C(n)
\leq 2cn(n-1)/mC(n)≤2cn(n−1)/m applies
if m \geq cn(n-1)+1m≥cn(n−1)+1, then at least half of the
functions hh in H_mHm
are injective (no collisions)
strategy: double hashing with O(n)O(n) space complexity
step 1: hash key using a well-chosen hash function in a table of size O(n)O(n) (i.e. m = \alpha nm=αn), where
each collision is packed into a bucket
set \alphaα
to \sqrt 2 \cdot c2⋅c,
then m = \lceil \sqrt2 \cdot c \cdot
n\rceilm=⌈2⋅c⋅n⌉
choose hh
with few collisions from H_{\lceil \sqrt2
\cdot c \cdot n\rceil}H⌈2⋅c⋅n⌉
for h(k) \in \{0, ..., \lceil \sqrt2cn\rceil -
1\}h(k)∈{0,...,⌈2cn⌉−1}
choose hh
until C(h) \leq \sqrt2 \cdot nC(h)≤2⋅n
formally: C(h) = |\{(x,y) \; | \; h(x) = h(y), x
\neq y \}| \leq \sqrt2nC(h)=∣{(x,y)∣h(x)=h(y),x=y}∣≤2n
note: every tuple pair is counted twice! (x,y)(x,y),
then (y,x)(y,x)
for each hash ll,
a bucket B_lBl
is created, so that each key mapped to ll
gets inserted into B_lBl
each bucket has b_l = |B_l|bl=∣Bl∣ keys
each bucket has size m_l = c
\cdot b_l (b_l -1) + 1 \in O(b_l^2)ml=c⋅bl(bl−1)+1∈O(bl2)
sum of all bucket sizes effectively in O(n)O(n)
due to low number of collisions
(!) good function, when \alpha \mod x
\implies x > \sqrt2 \cdot nαmodx⟹x>2⋅n for
any \alphaα
step 2: choose fitting h_lhl
for bucket B_lBl
from cc-universal
family H_{m_l}Hml
with h_l(k) \in \{0, ..., m_l
-1\}hl(k)∈{0,...,ml−1}
choose h_lhl
until no collisions
(!) good function, when \alpha \mod x
\implies x \geq b_l(b_l-1) + 1αmodx⟹x≥bl(bl−1)+1 for any \alphaα
with current bucket size b_lbl
when using arrays, the hash value of a key xx is s_l + h_l(x)sl+hl(x) with l = h(x)l=h(x), where hh is a perfect hash
function, and the worst-case runtime complexity for a lookup is O(1)O(1)
open hash function, allowing for collision-causing entries to be inserted at a free
neighbouring space
idea: store element in next free space, scanning from left to right and
wrapping around
the original hash value of a key is its ideal position
// insert into next available spot if ideal spot taken
void insert(Object e) {
i = h(key(e));
while (T[i] != null && T[i] != e)
i = (i + 1) % m;
T[i] = e;
}
// find object using linear search
Object find(Key k) {
i = h(k);
while (T[i] != null && key(T[i]) != k)
i = (i+1) % m;
return T[i];
}
// insert into next available spot if ideal spot takenvoidinsert(Object e) {
i = h(key(e));
while (T[i] != null && T[i] != e)
i = (i + 1) % m;
T[i] = e;
}
// find object using linear search
Object find(Key k) {
i = h(k);
while (T[i] != null && key(T[i]) != k)
i = (i+1) % m;
return T[i];
}
pros:
no extra space complexity
cache-efficient, since we only look at neighbouring entries in the same array
deletion (move everything that is not on its ideal position
back one space until blank position reached, leave elements in ideal positions
where they are!):
in-place, unstable, time complexity always \Theta(n^2)Θ(n2), space complexity O(1)O(1)
idea: choose smallest element from remainder of array and swap
places with element at start of iteration
void selectionSort(Object[] a, int n) {
for (int i = 0; i < n; i++) {
int k = i;
// find smallest element from unsorted sublist
for (int j = i + 1; j < n; j++)
if (a[j] < a[k])
k = j;
// swap with leftmost unsorted element
swap(a, i, k);
}
}
voidselectionSort(Object[] a, int n) {
for (inti=0; i < n; i++) {
intk= i;
// find smallest element from unsorted sublistfor (intj= i + 1; j < n; j++)
if (a[j] < a[k])
k = j;
// swap with leftmost unsorted element
swap(a, i, k);
}
}
idea: take next element from array and insert into correct
position by iterating backwards
void insertionSort(Object[] a, int n) {
for (int i = 1; i < n; i++)
// iterate backwards and insert at correct position
for (int j = i − 1; j >= 0; j−−)
if (a[j] > a[j + 1])
swap(a, j, j + 1);
else
break;
}
voidinsertionSort(Object[] a, int n) {
for (inti=1; i < n; i++)
// iterate backwards and insert at correct positionfor (intj= i − 1; j >= 0; j−−)
if (a[j] > a[j + 1])
swap(a, j, j + 1);
elsebreak;
}
example of a single iteration:
array: [5,10,19,1,14,3]
current element: 1
[5,10,19,1,14,3] (correct position? no \to→ swap 1 and 19)
[5,10,1,19,14,3] (correct position? no \to→ swap 1 and 10)
[5,1,10,19,14,3] (correct position? no \to→ swap 1 and 10)
idea: choose pivot element, then split array into
elements smaller than pivot and greater or equal to pivot
for each iteration, place pivot right at the end in the beginning for simplicity’s sake
let itemFromLeft be the first element starting from the
left of the array that is larger than the pivot and itemFromRight the first element starting from the right of
the array that is smaller than the pivot
once both have been found, swap places
if the index of itemFromLeft (ii) is greater
than that of itemFromRight (jj),
stop and swap pivot with itemFromLeft's index
continue recursively for each array (lower or greater than pivot, leave pivot unchanged
in final array)
speedup: when there are only two or less elements in an array, sort in one
go without pivot element
void quickSort(int[] a, int l, int r) {
if (l < r) {
int p = a[r]; // choose rightmost element as pivot
int i = l - 1; // left index
int j = r; // right index
do {
// move left index
do {
i++;
} while (a[i] < p);
// move right index
do {
j--;
} while (j >= l && a[j] > p);
// swap elements if possible
if (i < j)
swap(a, i, j);
} while (i < j);
// at end of iteration, move pivot into correct position
swap (a, i, r);
// do quicksort for lower and greater subarrays
quickSort(a, l, i - 1);
quickSort(a, i + 1, r);
}
}
voidquickSort(int[] a, int l, int r) {
if (l < r) {
intp= a[r]; // choose rightmost element as pivotinti= l - 1; // left indexintj= r; // right indexdo {
// move left indexdo {
i++;
} while (a[i] < p);
// move right indexdo {
j--;
} while (j >= l && a[j] > p);
// swap elements if possibleif (i < j)
swap(a, i, j);
} while (i < j);
// at end of iteration, move pivot into correct position
swap (a, i, r);
// do quicksort for lower and greater subarrays
quickSort(a, l, i - 1);
quickSort(a, i + 1, r);
}
}
example using rightmost element as pivot:
current array: [10, 5, 19, 1, 14, 3]
pivot: 3
swapped 10 (first greater than 3 from left) and 1 (first smaller than 3 from
right): [1, 5, 19, 10, 14, 3]
runtime always O(k \cdot n)O(k⋅n) with number of keys
nn and key
length kk,
space complexity O(n + k)O(n+k)
idea: create and distribute elements into buckets according to their radix, then
merge buckets and continue with new radix
for decimal numbers: from rightmost digit to leftmost digit, create buckets for
each present digit (0-9), distribute numbers into corresponding buckets, merge buckets and
repeat for next digit of number
for words: from rightmost letter to leftmost letter, create buckets for each
present letter (A-Z), distribute words into corresponding buckets, merge buckets and repeat
for next letter of word
idea: find kk-th smallest
element in array of nn elements
(numbering starts at 1)
similar to QuickSort, but we only look at one partition of the array
if kk is
smaller than the index of the pivot element (also starting at 1), continue with
left array and same kk
if kk is
greater than the index of the pivot element, continue with right array and k = k - |a| -
|b|k=k−∣a∣−∣b∣, where |a|∣a∣ is the length of the
left partition and |b|∣b∣ is the length of the
middle partition (containing elements equal to pivot)
else, element found
example - finding 7th smallest element in array (5)
s = [3,1,4,1,5,9,2,6,5,3,5,8,9], k = 7 \to→
[1,1][2][3,4,5,9,6,5,3,5,8,9]
s = [3,4,5,9,6,5,3,5,8,9], k = 4 \to→[3,4,5,5,3,5][6][9,8,9]
s = [3,4,5,5,3,5], k = 4 \to→
[3,4,3][5,5,5][] \to→found: 5
divide-and-conquer algorithms: algorithms that recursively divide the
problem into smaller subproblems, that are then solved (conquered) and merged back
together
runtime analysis of recursive functions is done using recurrence relations
recurrence relations define one or more base cases and a function
to determine the rest
e.g. Fibonacci numbers F(x) = \begin{dcases}1 & \text{if n = 0}\\ 1 &
\text{if n = 1} \\ F(n-2) + F(n-1) & \text{if n > 1}\end{dcases}F(x)=⎩⎨⎧11F(n−2)+F(n−1)if n = 0if n = 1if n > 1
to solve recurrence relation, we need to get rid of the function’s recursiveness and find a
closed form
e.g. closed form of F(x) = \frac{1}{\sqrt 5}\left(\left(\frac{1 + \sqrt
5}{2}\right)^n - \left(\frac{1 - \sqrt 5}{2}\right)^n\right)F(x)=51((21+5)n−(21−5)n)
method 1: iterative insertion
write first few steps by hand and try to deduce closed formula
e.g. T(n) = \begin{dcases}a
& \text{if n = 0} \\ T(n-1) + n & \text{if n > 0}
\end{dcases}T(n)={aT(n−1)+nif n = 0if n > 0
a full binary tree with nn
nodes has height \lfloor \log_2(n) \rfloor + 1⌊log2(n)⌋+1
complete binary tree: the first t-1t−1 levels make up a
complete binary tree, there exists a node ee on level
tt such that
there are no more nodes to the right of it
can be stored using arrays, where a node with index ii has children at
indices 2i + 12i+1 and 2i + 22i+2 and parent node at \lfloor \frac{i-1}{2}
\rfloor⌊2i−1⌋
deleteMin(): replace root with last element in heap and sift down
until heap invariant fulfilled, \mathcal{O}(1)O(1) + runtime of siftDown(v)
// pseudocode
Element deleteMin(Heap<Element> H) {
Element min = root of H;
replace root of H with last element of H;
siftDown(H, root of H);
return min;
}
// pseudocode
Element deleteMin(Heap<Element> H) {
Elementmin= root of H;
replace root of H with last element of H;
siftDown(H, root of H);
return min;
}
siftDown(v): move node down according to min-heap invariant, \mathcal{O}(\log n)O(logn)
// pseudocode
siftDown(Heap<Element> H, Node v) {
// cannot sift down if node is leaf
if (isLeaf(v)) return;
Node m;
// choose direction
if (key(v.left) < key(v.right)){
m = v.left;
}
else {
m = v.right;
}
// restore heap invariant or quit
if (key(m) < key(v)) {
swap content of m and v;
siftDown(H, m);
}
}
// pseudocode
siftDown(Heap<Element> H, Node v) {
// cannot sift down if node is leafif (isLeaf(v)) return;
Node m;
// choose directionif (key(v.left) < key(v.right)){
m = v.left;
}
else {
m = v.right;
}
// restore heap invariant or quitif (key(m) < key(v)) {
swap content of m and v;
siftDown(H, m);
}
}
insert(e): insert element at end of heap then sift up into place,
\mathcal{O}(1)O(1) + runtime of siftUp()
// pseudocode
insert(Heap<Element> H, Element e) {
Node v = insert e at end of H;
siftUp(H, v);
}
// pseudocode
insert(Heap<Element> H, Element e) {
Nodev= insert e at end of H;
siftUp(H, v);
}
siftUp(v): move node up according to min-heap invariant, \mathcal{O}(\log n)O(logn)
// pseudocode
siftUp(Heap<Element> H, Node v) {
while (v is not root && key(v.parent) > key(v)) {
swap content of v and v.parent;
v = v.parent;
}
}
// pseudocode
siftUp(Heap<Element> H, Node v) {
while (v is not root && key(v.parent) > key(v)) {
swap content of v and v.parent;
v = v.parent;
}
}
build(e1...en):
insert nn elements
unsorted into heap
do siftDown() for each node vv on
layer tt bottom-up
in reverse order (right to left)
in other words: the first \lfloor n / 2
\rfloor⌊n/2⌋ elements of
the actual array, handled in reverse order (e.g. for [15,20,9,1,11,8,4,13,17], one would do siftDown() for 1,9,20,15 in that order)
decreaseKey(v,k): \mathcal{O}(\log n)O(logn)
decreaseKey(Heap<Element> H, Node v, int k) {
if (k > key(v)) error();
key(v) = k;
siftUp(H, v);
}
decreaseKey(Heap<Element> H, Node v, int k) {
if (k > key(v)) error();
key(v) = k;
siftUp(H, v);
}
increaseKey(v,k): \mathcal{O}(\log n)O(logn)
increaseKey(Heap<Element> H, Node v, int k) {
if (k < key(v)) error();
key(v) = k;
siftDown(H, v);
}
increaseKey(Heap<Element> H, Node v, int k) {
if (k < key(v)) error();
key(v) = k;
siftDown(H, v);
}
delete(v): replace vv with last
node v'v′
in heap then do siftUp(v') or siftDown(v')
Binary Heap example using Max-Heap
insertion: adding 15 into heap by inserting it at the end, then sifting up until heap
invariant (here max-heap, i.e. \text{key(parent) > key(child)}key(parent) > key(child))
is restored
for visualization: let X be the spot where 15 will be inserted at first
place 15 there and check, if heap invariant is maintained \to→ since heap invariant
is violated, sift 15 up and check again
since the heap invariant is violated once more, sift up once again \to→ since the node is now
at the root, we have successfully inserted the node into the heap
deletion: using the same max-heap as before
let 11 be the node we want to remove (equiv. deleteMax())
replace 11 with last node in heap, 4
sift down, then heap invariant is restored
Binomial Trees
a binomial tree of rank rr has a root
node with children of rank r-1r−1, r-2r−2, … , 0 in that order[2]
maximum depth rr
depth l \in \{0, ...
,r\}l∈{0,...,r} has r \choose l(lr)
nodes (\frac{r!}{l!(r-l)!}l!(r−l)!r!)
in total 2^r2r
nodes
maximum degree rr in
root
merging: root node with bigger key becomes new child of root with smaller key[3]
removing root: new binomial trees of ranks r-1r−1 down to 00 appear
set of binomial trees where each tree fulfills the min-heap invariant, there are
no two trees with the same rank and a min-pointer points to
the root with the smallest key
a binomial heap with nn nodes contains
at most 1 + \lfloor \log_2(n)
\rfloor1+⌊log2(n)⌋ binomial trees
the binary representation of nn tells us
exactly the rank of the trees in our heap
z.B. n = 11_{10} = 1011_b = 1 * 2^3 + 1 * 2^1 + 1 *
2^0 \ton=1110=1011b=1∗23+1∗21+1∗20→ there are
trees of ranks 3,1,0
merging: equivalent to binary addition, \mathcal{O}(\log n)O(logn) with n = \max\{n_1,n_2\}n=max{n1,n2}[4]
operations:
min(): return root with minimal key (located at
min-pointer)
\mathcal{O}(1)O(1)
merge(): equivalent to binary addition
\mathcal{O}(\log n)O(logn)
insert(e): merge() with
binomial tree of rank 0, containing only e
\mathcal{O}(\log n)O(logn)
deleteMin(): remove min-root and merge() the children with the rest of the heap
\mathcal{O}(\log n)O(logn)
decreaseKey(v,k): set key(v) = k, then siftUp() in
binomial tree of v and adjust min-pointer if needed
\mathcal{O}(\log n)O(logn)
remove(v): first decreaseKey(v, -inf), then deleteMin()
\mathcal{O}(\log n)O(logn)
Binary Search Tree
binary tree with…
search tree invariant: left child smaller than parent, right child larger
than parent
key invariant: each key is unique
degree invariant: a node can only have at most 2 children
locate(e): begin at root ww of tree,
O(\log n)O(logn)
if \text{key}(v) \geq
kkey(v)≥k, go
to left child, else go to right child
return minimal node for which its key is greater or equal ee
insert(e): O(\log n)O(logn)
do locate(key(e)) until e'e′
is reached
if \text{key}(e') >
\text{key}(e)key(e′)>key(e), insert ee before
e'e′
in list, and create new search tree node with \text{key}(e)key(e) as splitter key to
fulfill search tree invariant
else, throw error
remove(k): O(\log n)O(logn)
do locate(k) until ee is reached
if \text{key}(e) =
kkey(e)=k
delete ee
from list
delete parent key vv
from tree
if not already deleted, replace node with next smaller node in tree
else, throw error
cba with making original graphics here, just look in the slides or google it, the examples are
good enough
if node does not have a left child, move right child into
its place
if node does not have a right child, move left child into
its place
if node has left and right child, replace with node with next
smaller key
balancing afterwards: same as before
searching works the same as in any standard binary search tree
Summary: AVL-Tree Rotations
if height differences for parent and child have the same sign,
perform single rotation
if positive, perform left rotation
if negative, perform right rotation
if height differences for parent and child have different signs,
perform double rotation
if +2 / -1, perform R-L–rotation
if -2 / +1, perform L-R-rotation
Source: https://www.geeksforgeeks.org/insertion-in-an-avl-tree/
T1, T2, T3 and T4 are subtrees.
S - single, D - double
S: RIGHT ROTATE
z y
/ \ / \
y T4 Right Rotate (z) x z
/ \ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2
D: LEFT-RIGHT ROTATE
z z x
/ \ / \ / \
y T4 Left Rotate (y) x T4 Right Rotate(z) y z
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
T1 x y T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2
S: LEFT ROTATE
z y
/ \ / \
T1 y Left Rotate(z) z x
/ \ - - - - - - - -> / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T4
D: RIGHT-LEFT ROTATE
z z x
/ \ / \ / \
T1 y Right Rotate (y) T1 x Left Rotate(z) z y
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4
Source: https://www.geeksforgeeks.org/insertion-in-an-avl-tree/
T1, T2, T3 and T4 are subtrees.
S - single, D - double
S: RIGHT ROTATE
z y
/ \ / \
y T4 Right Rotate (z) x z
/ \ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2
D: LEFT-RIGHT ROTATE
z z x
/ \ / \ / \
y T4 Left Rotate (y) x T4 Right Rotate(z) y z
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
T1 x y T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2
S: LEFT ROTATE
z y
/ \ / \
T1 y Left Rotate(z) z x
/ \ - - - - - - - -> / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T4
D: RIGHT-LEFT ROTATE
z z x
/ \ / \ / \
T1 y Right Rotate (y) T1 x Left Rotate(z) z y
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4
(a,b)-Trees
variable definitions:
ww:
root
nn leaves
d(v)d(v): number of children
(ext. degree) of a node vv
t(v)t(v): depth of a node
vv
a search treeGG is called an (a,b)(a,b)-tree for a \geq 2a≥2 and b \geq 2a-1b≥2a−1 (alt. a \leq \frac{b+1}{2}a≤2b+1) if
following invariants are fulfilled:
form invariant: all leaves are at the same depth
degree invariant: for all internal nodes except for the root, a \leq d(v) \leq
ba≤d(v)≤b
in other words, each node (except for the root) has at least aa and
at most bb
children
for the root node: 2 \leq d(w) \leq
b2≤d(w)≤b
(except if it’s a leaf)
depth d \leq 1 + \lfloor \log_a
\frac{n+1}{2}\rfloord≤1+⌊loga2n+1⌋ if n > 1n>1
all operations\Theta(\log n)Θ(logn)
locate(k) works the same as in any search tree
insert(e):
locate e'e′
using locate(key(e))
if \text{key}(e) <
\text{key}(e')key(e)<key(e′), insert ee before
e'e′,
otherwise throw error
insert \text{key}(e)key(e) and handle in vv
into tree
case 1: if d(v) \leq
bd(v)≤b,
finish
case 2: if d(v) >
bd(v)>b,
splitvv
in two and move splitter key (usually key at index \lfloor b / 2 \rfloor⌊b/2⌋ or
median) up
case 2.5: if degree of parent node is now bigger,
continue until eventually \deg \leq
bdeg≤b or
root has been split
remove(e):
let vv be
the node of ee
case 1: vv
contains ee
(lowest depth)
directly deleteee
and vv
if vv
now has less than aa
children, steal or merge
case 2: vv
does not contain ee
(not on lowest depth)
let e'e′
be the element directly before ee,
included in vv
delete e'e′
from vv
and ee
from list
replace remaining ee
in tree with e'e′
(i.e. replace key with value which contained pointer to ee)
if vv
now has less than aa
children, steal or merge
steal if neighbouring node v'v′
of vvhas more than aa children,
start with left neighbour
v'v′
left of vv:
rightmost key in v'v′
goes up, replaced key goes down into vv
v'v′
right of vv:
leftmost key in v'v′
goes up, replaced key goes down into vv
merge if neighbouring node v'v′
of vvdoes not have more than aa children
merge vv
with neighbouring node, preferably left node, by bringing down
father element
father node and adjacent nodes may need to be adjusted with steal / merge too
afterwards, since we’re taking a node away from it
if root is empty, remove it
for the same reason as before, if you want examples, look in the slides and go along with
those
for all edges (v,w)(v,w), finishNum[v] > finishNum[w] (higher finish number
points to lower finish number)
Type of Edge
dfsNum[v] < dfsNum[w]
finishNum[v] > finishNum[w]
Root Edge
yes
yes
Forwards Edge
yes
yes
Backwards Edge
no
no
Rest
no
yes
Connectivity
a graph is connected if every pair of vertices in the graph is
connected\equiv≡ there is a
path between every pair of vertices
a graph with just one vertex is connected
an edgeless graph with two or more vertices is disconnected
a directed graph is called weakly connected if replacing all of
its directed edges with undirected edges produces a connected (undirected) graph
it is unilaterally connected if it contains a directed path from uu to vvor a directed path from vv to
uu for every pair
of vertices u,
vu,v
it is strongly connected, or simply strong, if it contains a
directed path from uu to vvand a directed path from vv to
uu for every pair
of vertices u,
vu,v
a connected component is a maximal connected subgraph of an undirected
graph
each vertex belongs to exactly one connected component, as does each edge
a graph is connected if and only if it has exactly one connected component
the strong components are the maximal strongly connected subgraphs of a
directed graph
Shortest Paths (SSSP)
case 1: edge costs 1 \to→BFS
case 2: DAG, variable edge costs \to→Topological
Sorting
case 3: variable graph, positive edge costs \to→Dijkstra
case 4: variable graph, variable edge costs \to→Bellman-Ford
DAG - Topological Sorting
L ← Empty list that will contain the sorted elements
S ← FIFO-Queue of all nodes with no incoming edge
while S is not empty do
remove a node n from S
add n to L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
L ← Empty list that will contain the sorted elements
S ← FIFO-Queue of all nodes with no incoming edge
while S is not empty do
remove a node n from S
add n to L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
fundamental idea: there are at most|V| - 1∣V∣−1 edges in one of our paths
(because if there were |V|∣V∣ or more, there would be a
cycle)
algorithm:
initialize distance to source to 0 and all other nodes to infinity
for all edges: if the distance to the destination can be shortened by taking the
edge, the distance is updated to the new lower value
if dist[v] > dist[u] +
weight((u,v))dist[v]>dist[u]+weight((u,v)), then dist[v] = dist[u] +
weight((u,v))dist[v]=dist[u]+weight((u,v))
repeat last step |V|-1∣V∣−1 times
if in the last iteration, distances are still being updated, then finally
update these distances to - \infty−∞, indicating
that there is a negative weight cycle
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u, v) do
dist[u][v] ← w(u, v)
for each vertex v do
dist[v][v] ← 0
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
if dist[i][j] > dist[i][k] + dist[k][j]
dist[i][j] ← dist[i][k] + dist[k][j]
end if
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u, v) do
dist[u][v] ← w(u, v)
for each vertex v do
dist[v][v] ← 0
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
if dist[i][j] > dist[i][k] + dist[k][j]
dist[i][j] ← dist[i][k] + dist[k][j]
end if