Data Structures Final Review

Constant Time

Logarithmic Time

Logarithmic Time

Linear Time

Linear Time

Quadratic Time

Quadratic Time

Exponential Time

Exponential Time

A set of operations that should be available to a data structure.

Insert, Find, Modify, Delete

Push, Pop, Peek

Enqueue, Dequeue, Peek

Insert, Find, Delete

Insert, Find, Delete

Insert: * O(1), Find: O(N), Modify: O(N), Delete: O(N)

Insert: * O(1), Find: O(N), Modify: O(N), Delete: O(N)

Insert: O(1), Find: O(N), Modify: O(N), Delete: O(N)

Insert: O(1), Find: O(N), Modify: O(N), Delete: O(N)

Insert: O(N), Find: O(N), Modify: O(N), Delete: O(N)

Insert: O(N), Find: O(log N), Modify: O(log N), Delete: O(N)

Insert: O(N), Find: O(log N), Modify: O(log N), Delete: O(log N)

Insert: O(N), Find: O(N), Modify: O(N), Delete: O(N)

Insert: O(N), Find: O(N), Modify: O(N), Delete: O(N)

Push: * O(1), Pop: O(1), Peek: O(1)

Push: O(1), Pop: O(1), Peek: O(1)

Push: O(1), Pop: O(1), Peek: O(1)

Enqueue: * O(1), Dequeue: O(1), Peek: O(1)

Enqueue: * O(1), Dequeue: O(N), Peek: O(1)

Enqueue: * O(1), Dequeue: O(1), Peek: O(1)

Enqueue: O(1), Dequeue: O(N), Peek: O(N)

Enqueue: O(1), Dequeue: O(1), Peek: O(1)

Enqueue: O(1), Dequeue: O(1), Peek: O(1)

Insert: O(N), Find: O(N), Delete: O(N)

A set of vertices and edges that connect said vertices

Insert: O(N), Find: O(N), Delete: O(N)

Insert: O(N), Find: O(N), Delete: O(N)

Insert: O(1), Find: O(N), Delete: O(N)

Insert: O(1) + O(logN), Find: O(N), Delete: O(N), DeleteMin: O(1) + O(logN)

Insert: O(log N) + O(1), Find: O(log N), Delete: O(log N) + O(1)

Insert: O(N) & * O(log N), Find: O(N) & * O(log N), Delete: O(N) & * O(log N)

A formula for calculating recurrence relations

T(n) = a * T(n) + (n^k * log^p(n))

T(n) = Omega(n^(log_b(a)))

T(n) = Omega(n^(log_b(a)) * log^(p+1)(n))

T(n) = Omega(n^(log_b(a)) * log(log(n)))

T(n) = Omega(n^(log_b(a)))

T(n) = Omega(n^k * log^p(n))

T(n) = Omega(n^k)

A high level, language-independent description of a step-by-step process

A specific organization of data and family of algorithms for implementing an ADT

A data structure whose first element is the element with the lowest priority. Has operations insert, deleteMin, and is_empty.

A data structure whose elements have First-In First-Out insertion and removal. The first element inserted is the first element removed. Has operations enqueue, dequeue, and peek

A data structure whose elements have Last-In First-Out insertion and removal. The last element inserted is the first element removed. Has push, pop, and peek.

1. Place the element in the next available slot of the complete tree
2. Shift the element upward, swapping with parents, until each parent's priority is less than the priority of its children.

1. Swap the root of the heap with the last element of the heap
2. Delete the last element of the heap
3. Shift the root downward, swapping with children, until each child's priority is larger than the priority of its parents

A rearrangement function for a BST that keeps the average height at O(log N)

A BST whose nodes adhere to the AVL property, and implement the AVL balance condition.

The left and right subtrees of a node differ by -1, 0, or 1. They do not differ from a greater amount. If they do, the balance condition is activated

Swaps a parent for its left child, making the parent its right child. If the left child already has right children, it becomes the left children of the parent node instead.
Available to AVL Trees, Splay Trees

Swaps a parent for its right child, making the parent its left child. If the right child already has left children, it becomes the right children of the parent node instead.
Available to AVL Trees, Splay Trees

On a LL insertion, perform a right rotation on the imbalanced node.
On a RR insertion, perform a left rotation on the imbalanced node.
On a LR insertion, perform a left rotation between the problematic grandchild and child, and then perform a right rotation between the new child and the parent.
On a RL insertion, perform a right rotation between the problematic grandchild and child, and then perform a left rotation between the new child and the parent.

An operation in Splay Trees that move the most recently access nodes to the top, with the side effect of balancing the whole tree.

When a tree rebalances itself without using height information.

Perform two right rotations on the target node.

Perform two left rotations on the target node.

Perform a right rotation then a left rotation on the target node.

Perform a left rotation then a right rotation on the target node

Splay the maximum element of T1 to the root, then make T2 a right child of T1

Splay the specified node up to the root, and then cut the link from the root to the left child.

Splay the specified node up to the root, delete it, then join the resulting subtrees.

1) Every node has a color either red or black.

2) Root of tree is always black.

3) There are no two adjacent red nodes (A red node cannot have a red parent or red child).

4) Every path from a node (including root) to any of its descendant NULL node has the same number of black nodes.

A method for handling collisions in a hash table

A collision resolution strategy that resolves collisions y choosing a different location when the natural choice is full.

Find the index and keep incrementing by 1 until an open spot is found.
h(key) + i % T

Find the index and keep incrementing polynomially until an open spot is found.
h(key) + i^2 % T

Find the index using a first hashing function, and use a second hashing function to handle collisions.
(h(key) + i*g(key)) % T

A collision resolution strategy that places colliding elements into their own separate collections, usually a linked list.

The average amount of elements per bucket in a separate chaining hash table. Equal to N/TableSize.

Insert: O(log N), Find: O(log N), Delete: O(log N)

If any bottom nodes are a 4 node (has three elements), preemptively split it upwards.
Search for the location to place the node and then insert it.

A bottom-up search tree whose nodes can have 1, 2, or 3 elements, and can have n elements + 1 children.

If a node has 3 elements, upon insertion, the node must be split upwards. The middle node becomes the parent of a left 2-node and a right 2-node, both holding a single element. If there are no parents, a new parent is formed, otherwise it joins the already existing parent. Splits may cascade upwards, upon which this is repeated.

Start at the root, searching for the node to delete. Along the way own, turn 2-nodes into three nodes (except for the root).
If an adjacent sibling is a 3 or 4 nodes, redistribute items from the sibling and adopt the child.
If the adjacent sibling is a 2-node, redistribute items from the parent (which will always have at least 2 items, unless it's the root), then merge the nodes.
Once the node is found, move it downward to a leaf node, shifting nodes along the way, then delete it.

A graph in which the edges have no direction.

A graph in which the edges have a direction.

An edge that originates and ends at the same node

A path that originates and ends at the same node.

A sequence of edges that start at one node and ends at another node, connected via intermediary edges between nodes.

A graph such that there is a path going from any node to any other node

A graph that is not connected (there exist nodes with no paths between them)

A graph with no cycles.

A |V| X |V| matrix M, where if M[u][v] is true, then there is an edge from u to v.

A linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

A directed graph with no cycles.

A search in which children of a node are considered before siblings are considered.

A search in which siblings of a node are considered before children are considered.

An algorithm for finding the shortest paths from an origin node to every other node.
1. Pick the closest unknown vertex v
2. Add it to the known vertices
3. Update distances for nodes with edges from v

1. Label each vertex with its in-degree
2. Enqueue each vertex with a degree of 0
3. Dequeue the first vertex, add it to the ordering, and then decrease the in-degree of all the vertices they point to.
4. Repeat Steps 2-4 until all vertices are ordered.

An algorithm that makes the best choice at each step.

A subgraph of a graph that includes all the vertices of the graph while retaining the minimum amount of edges (or minimum cost in the case of a weighted graph).

A graph where each edge has an associated cost.

1. Pick a node and mark it known
2. Select the lowest edge that is connected to our already known nodes, and is connected to an unknown node.
3. Add the edge to our spanning tree, and mark both it and the vertex its connected to as known.
4. Repeat 2-4 until all vertices are known.

1. Pick the lowest cost edge that does not cause a cycle
2. Repeat until all vertices are connected.

A table describing the shortest path from any vertex to any other vertex.

k = iteration number
D_k = |V| x |V| Distance table in kth iteration
S_k = |V| x |V| Sequence table in kth iteration
d_ij = Distance between vertex i and j

1. Remove self loops and resolve multiedges by picking the lowest node.
2. Fill the S_0 table by filling each column with the column number
3. Fill the D_0 table by filling dij with the cost of the edge between i and j if it exists, and infinity if it doesn't exist. If i == j, mark it as nil.
4. For each cell C_ij in D_k, if in D_k-1 d_ij > d_ik + d_kj, then C_ij = d_ik + d_kj and S_ij = k. Otherwise, C_ij = d_ij and S_ij copies the value from the previous table.
5. Increment k by 1. Loop 4-5 until k > |V|

Look up D[a][b].

Seq = []
"Seq top" is the topmost value of the sequence stack
1. Push vertex a onto Seq
2. Push S[Seq top][b] onto Seq
3. Repeat 2 until S[Seq top][b] == b

Two arrays describing the distances and sequences from a single source node to every other node.

D = Distance array
P = Predecessor Array
k = Iteration count
1. Fill the distance array with 0 at the source node, and infinity at every other node
2. Fill the predecessor array with nil
3. For each edge u -> v, determine if v.d > u.d + w(u, v). If so, set v.d = u.d + w(u, v), and set v.p = u.
4. Increment k, and repeat until k = |V|

A collection of sets with the operations union and find.

Start with a forest. Each forest has a weight corresponding to the amount of nodes in their uptree.
This can be represented using a parent array and a weight array.
Union(a, b): Find the roots of a and b. If a.w < b.w, have a point to b. Otherwise, have b point to a. Update the weight of b to be |a| + |b|.
Find(a): Find the root of a. If path compression is on, shift a upwards to directly point to the root to be accessed earlier.

O(|V| + |E|)

O(|V|^2)

O(|E|)

O(|V|^2)

O(|V| + |E|)

O(|V|)

O(|E|)

O(|V| + |E|)

O((|V| + |E|) log |V|)

O(|V|)

O(|V||E|)

O(|E|)

O(|V||E|)

O(|V|^3)

O(|E| log |V|)

O(|E| log |V|)

O(|E| + log |V|)

O(log |N|)

O(|V|^3)