Data structure cheat sheet - Revision history

Hoppinglife: /* Graphs */

2020-10-27T02:52:08Z

Graphs

← Older revision		Revision as of 02:52, 27 October 2020
Line 109:		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.		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 ===		=== 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 ==		== Dynamic Programming ==

Hoppinglife: /* Searching */

2020-10-26T19:19:05Z

Searching

← Older revision		Revision as of 19:19, 26 October 2020
Line 118:		Line 118:

	== Searching ==		== Searching ==

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

			=== Breath-first search ===

	== Mathematical Problems ==		== Mathematical Problems ==

Hoppinglife: /* Permutations and Combinations */

2020-10-26T16:33:16Z

Permutations and Combinations

@@ Line 131: / Line 131: @@
 * reverse the tail:
 <pre>672[1345]</pre>
 ==== Heap's algorithm ====

Hoppinglife: /* Binary Tree */

2020-10-26T00:40:50Z

Binary Tree

← Older revision		Revision as of 00:40, 26 October 2020
Line 40:		Line 40:
	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.		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 ~~are~~ 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.		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 ===		=== Heap ===

Hoppinglife: /* Traversal */

2020-10-26T00:32:31Z

Traversal

← Older revision		Revision as of 00:32, 26 October 2020
Line 38:		Line 38:
	==== Traversal ====		==== 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.		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 are 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.

	=== Heap ===		=== Heap ===

Hoppinglife: /* Traversal */

2020-10-26T00:28:07Z

Traversal

← Older revision		Revision as of 00:28, 26 October 2020
Line 37:		Line 37:

	==== Traversal ====		==== 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.

	=== Heap ===		=== Heap ===

Hoppinglife: /* Property */

2020-10-26T00:25:20Z

Property

← Older revision		Revision as of 00:25, 26 October 2020
Line 32:		Line 32:
	==== Property ====		==== Property ====
	* A full n-level binary tree have <math>2^n - 1</math> elements.		* A full n-level binary tree have <math>2^n - 1</math> elements.
	* A n-node binary tree have <math>\lceil log n \rceil </math> levels.		* A n-node binary tree have <math>\lceil log n \rceil + 1 </math> levels.

	==== Storage ====		==== Storage ====

Hoppinglife: /* Binary Tree */

2020-10-26T00:24:29Z

Binary Tree

← Older revision		Revision as of 00:24, 26 October 2020
Line 31:		Line 31:
	=== Binary Tree ===		=== Binary Tree ===
	==== Property ====		==== Property ====
			* A full n-level binary tree have <math>2^n - 1</math> elements.
			* A n-node binary tree have <math>\lceil log n \rceil </math> levels.
			==== Storage ====

	==== Traversal ====		==== Traversal ====

Hoppinglife: /* Generate next lexicographic permutation */

2020-10-26T00:16:10Z

Generate next lexicographic permutation

← Older revision		Revision as of 00:16, 26 October 2020
Line 109:		Line 109:

	* find the longest non-increasing suffix:		* find the longest non-increasing suffix:
	<pre>~~671~~[5432]</pre>		<pre>67[1]5432</pre>
	* find the last element that is larger than the previous one:		* find the last element that is larger than the previous one:
	<pre>6[7]1[5]~~432~~</pre>		<pre>67[1]543[2]</pre>
	* swap		* swap
	<pre>6[5]1[7]~~432~~</pre>		<pre>67[2]543[1]</pre>
	* reverse the tail:		* reverse the tail:
	<pre>6[~~5]1[2347~~]</pre>		<pre>672[1345]</pre>

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

Hoppinglife: /* Mathematical Problems */

2020-10-26T00:12:57Z

Mathematical Problems

← Older revision		Revision as of 00:12, 26 October 2020
Line 105:		Line 105:

	== Mathematical Problems ==		== Mathematical Problems ==
			=== Permutations and Combinations ===
	=== Generate next lexicographic permutation ===		==== Generate next lexicographic permutation ====

	* find the longest non-increasing suffix:		* find the longest non-increasing suffix:
Line 117:		Line 117:
	<pre>6[5]1[2347]</pre>		<pre>6[5]1[2347]</pre>

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