Data structure cheat sheet: Difference between revisions

(5 intermediate revisions by the same user not shown)

Line 37:

==== Traversal ====

General traversal of binary trees all takes <math>O(n)</math> time, except for the root node, exactly two times of the search routine was called for each node.

For Binary Search Trees, Min/Max is easy - just follow the left/right link. Getting successor/predecessor is tricker: the next element of x is either a) the minimum element of the right subtree, or b) the lowest ancestor of x whose left child is also the ancestor of x.

==== Insertion and Deletion ====

Insertion is relatively simple, just follows the search procedure until you find an empty node.

Deletion is more complicated: if the target <math>z</math> has two children, we find the successor of <math>z</math>, if it is the right child of <math>z</math>, it can be replaced by y, otherwise, we first replace y by its right child, then replace z using y.

=== Heap ===

Line 99:

Line 109:

Fundamentally, the representation of a graph is always equivalent to an adjacent matrix. The most usual methods are uncompressed matrix, adjacent list, and compressed matrix.

=== Traverse ===

=== ~~Properties~~ ===

* BFS is the simplest traverse one can conduct on a graph. Useful to do the basic shortest path discoveries.

=== ~~Algorithms~~ ===

* DFS is useful for establishing strongly connected components. It can also be used to classify edges in the graph (tree edge, back, forward, cross).

=== Topological sort and Strongly Connected Components ===

* As each vertex is finished, insert it into the front of a linked list.

* For directional graphs, its strongly connected graph can be computed in the following way: 1) do a DFS to establish topological order, 2) do the DFS on the transposed graph using the order in reverse order of its finishing time.

=== Minimum Spanning Trees ===

* Kruskal: add the lowest edge that connected different components. <math>O(E lg V)</math>

* Prim: find the light edge between the sites. <math>O(E lg V)</math>

=== Shortest Paths ===

* Bellman-Ford: relax each edge V times, O(VE).

* DAG can be done in O(V+E) time, by looking at it in topological order.

* Dijkstra: relax all the edges of the newly visited node. O(V^2)

== Dynamic Programming ==

Line 108:

Line 128:

== Searching ==

=== Depth-first search / backtracking ===

=== Breath-first search ===

== Mathematical Problems ==

Line 121:

Line 145:

* reverse the tail:

==== Generate the k-th permutation of N ====

The idea is to generate the permutation one element by one element:

we can determine the first element of the permutation by comparing k with N,

then repeat this procedure.

==== Generate permutations with the duplications ====

This can be done with a simple backtracking search.

==== Heap's algorithm ====

@@ Line 37: / Line 37: @@
 ==== Traversal ====
+General traversal of binary trees all takes <math>O(n)</math> time, except for the root node, exactly two times of the search routine was called for each node.
+For Binary Search Trees, Min/Max is easy - just follow the left/right link.  Getting successor/predecessor is tricker: the next element of x is either a) the minimum element of the right subtree, or b) the lowest ancestor of x whose left child is also the ancestor of x.
+==== Insertion and Deletion ====
+Insertion is relatively simple, just follows the search procedure until you find an empty node.
+Deletion is more complicated: if the target <math>z</math> has two children, we find the successor of <math>z</math>, if it is the right child of <math>z</math>, it can be replaced by y, otherwise, we first replace y by its right child, then replace z using y.
 === Heap ===
@@ Line 99: / Line 109: @@
 Fundamentally, the representation of a graph is always equivalent to an adjacent matrix. The most usual methods are uncompressed matrix, adjacent list, and compressed matrix.
 === Traverse ===
-=== Properties ===
+* BFS is the simplest traverse one can conduct on a graph. Useful to do the basic shortest path discoveries.
-=== Algorithms ===
+* DFS is useful for establishing strongly connected components. It can also be used to classify edges in the graph (tree edge, back, forward, cross).
+=== Topological sort and Strongly Connected Components ===
+* As each vertex is finished, insert it into the front of a linked list.
+* For directional graphs, its strongly connected graph can be computed in the following way: 1) do a DFS to establish topological order, 2) do the DFS on the transposed graph using the order in reverse order of its finishing time.
+=== Minimum Spanning Trees ===
+* Kruskal: add the lowest edge that connected different components. <math>O(E lg V)</math>
+* Prim: find the light edge between the sites. <math>O(E lg V)</math>
+=== Shortest Paths ===
+* Bellman-Ford: relax each edge V times, O(VE).
+* DAG can be done in O(V+E) time, by looking at it in topological order.
+* Dijkstra: relax all the edges of the newly visited node. O(V^2)
 == Dynamic Programming ==
@@ Line 108: / Line 128: @@
 == Searching ==
+=== Depth-first search / backtracking ===
+=== Breath-first search ===
 == Mathematical Problems ==
@@ Line 121: / Line 145: @@
 * reverse the tail:
 <pre>672[1345]</pre>
+==== Generate the k-th permutation of N ====
+The idea is to generate the permutation one element by one element:
+we can determine the first element of the permutation by comparing k with N,
+then repeat this procedure.
+==== Generate permutations with the duplications ====
+This can be done with a simple backtracking search.
 ==== Heap's algorithm ====

Data structure cheat sheet: Difference between revisions

Navigation menu

Search