Data Structures - Revision history

Marc: /* ACSL Videos */

2020-06-10T06:43:46Z

ACSL Videos

← Older revision		Revision as of 23:43, 9 June 2020
Line 221:		Line 221:

	A general tutorial on internal path length of a binary search tree		A general tutorial on internal path length of a binary search tree

			\|-
			\| <youtube width="300" height="180">https://youtu.be/Olu_RbWnHb8</youtube>
			\| [https://youtu.be/Olu_RbWnHb8 ''ACSL Test Prep - Data Structures - Queues, Stacks, Binary Search Trees, and Heaps'' ('''Mrs. Gupta''')]

			A talked-over presentation discussing queues, stacks, binary search trees, and heaps as needed for the American Computer Science League and its tests.
	\|}		\|}

Marc: /* Problem 1 */

2019-02-11T00:55:07Z

Problem 1

← Older revision		Revision as of 17:55, 10 February 2019
Line 166:		Line 166:
	</syntaxhighlight>		</syntaxhighlight>

	'''Solution:''' The first POP stores 8 in Y. The POP stores 6 in X. Then, 8-6=2 is pushed onto the stack. Finally, the last POP removes the 2 and stores it in Z.		'''Solution:''' The first POP stores 8 in Y. The second POP stores 6 in X. Then, 6-8=-2 is pushed onto the stack. Finally, the last POP removes the -2 and stores it in Z.

	=== Problem 2 ===		=== Problem 2 ===

Williamhu: /* Sample Problems */ More syntaxhighlight error fixing

2019-01-10T01:46:08Z

Sample Problems: More syntaxhighlight error fixing

← Older revision		Revision as of 18:46, 9 January 2019
Line 156:		Line 156:
	Consider an initially empty stack. After the following operations are performed, what is the value of Z?		Consider an initially empty stack. After the following operations are performed, what is the value of Z?

	<syntaxhighlight>		<syntaxhighlight lang="text">
	PUSH(3)		PUSH(3)
	PUSH(6)		PUSH(6)

Williamhu: /* Priority Queues */ Same as before

2019-01-10T01:45:47Z

Priority Queues: Same as before

← Older revision		Revision as of 18:45, 9 January 2019
Line 137:		Line 137:
	The smallest value is always the root. To delete it (and one can only delete the smallest value), one replaces it with the bottom-most and right-most element, and then walks down the tree making exchanges with the smaller child in order to ensure that the tree is valid. The following pseudo-code formalizes this notion:		The smallest value is always the root. To delete it (and one can only delete the smallest value), one replaces it with the bottom-most and right-most element, and then walks down the tree making exchanges with the smaller child in order to ensure that the tree is valid. The following pseudo-code formalizes this notion:

	<syntaxhighlight>		<syntaxhighlight lang="text">
	b = bottom-most and right-most element		b = bottom-most and right-most element
	p = root of tree		p = root of tree

Williamhu: /* Trees */ Fixed syntax highlighting

2019-01-10T01:45:18Z

Trees: Fixed syntax highlighting

← Older revision		Revision as of 18:45, 9 January 2019
Line 70:		Line 70:
	To search for a node in a binary tree, the following algorithm (in pseudo-code) is used:		To search for a node in a binary tree, the following algorithm (in pseudo-code) is used:

	<syntaxhighlight>		<syntaxhighlight lang="text">
	p = root		p = root
	found = FALSE		found = FALSE
Line 86:		Line 86:
	Deleting from a binary search tree is a bit more complicated. The algorithm we’ll use is as follows:		Deleting from a binary search tree is a bit more complicated. The algorithm we’ll use is as follows:

	<syntaxhighlight>		<syntaxhighlight lang="text">
	p = node to delete		p = node to delete
	f = father of p		f = father of p

Williamhu: /* Stacks and Queues */ Another method for fixing syntaxhighlight

2019-01-09T23:12:13Z

Stacks and Queues: Another method for fixing syntaxhighlight

← Older revision		Revision as of 16:12, 9 January 2019
Line 15:		Line 15:
	Consider the following sequence of 14 operations:		Consider the following sequence of 14 operations:

	<~~syntaxhighlight~~>		<pre>
	PUSH("A")		PUSH("A")
	PUSH("M")		PUSH("M")
Line 30:		Line 30:
	PUSH("A")		PUSH("A")
	PUSH("N")		PUSH("N")
	</~~syntaxhighlight~~>		</pre>

	If these operations are applied to a stack, then the values of the pops are: E, R, I, M, A and NIL. After all of the operations, there are three items still on the stack: the N is at the top (it will be the next to be popped, if nothing else is pushed before the pop command), and C is at the bottom. If, instead of using a stack we used a queue, then the values popped would be: A, M, E, R, I and NIL. There would be three items still on the queue: N at the top and C on the bottom. Since items are removed from the bottom of a queue, C would be the next item to be popped regardless of any additional pushes.		If these operations are applied to a stack, then the values of the pops are: E, R, I, M, A and NIL. After all of the operations, there are three items still on the stack: the N is at the top (it will be the next to be popped, if nothing else is pushed before the pop command), and C is at the bottom. If, instead of using a stack we used a queue, then the values popped would be: A, M, E, R, I and NIL. There would be three items still on the queue: N at the top and C on the bottom. Since items are removed from the bottom of a queue, C would be the next item to be popped regardless of any additional pushes.
Line 38:		Line 38:
	ACSL Contests pre-2018 used a slightly different, and more liberal, syntax. Consider the following sequence on a stack:		ACSL Contests pre-2018 used a slightly different, and more liberal, syntax. Consider the following sequence on a stack:

	<~~syntaxhighlight~~>		<pre>
	PUSH(A)		PUSH(A)
	PUSH(B)		PUSH(B)
Line 44:		Line 44:
	POP(X)		POP(X)
	POP(Z)		POP(Z)
	</~~syntaxhighlight~~>		</pre>

	After the 5 operations, the stack would be left with A as the only element on the stack, the value of C in variable X, and the value of B in variable Z.		After the 5 operations, the stack would be left with A as the only element on the stack, the value of C in variable X, and the value of B in variable Z.

Marc Brown: /* Stacks and Queues */

2018-09-12T03:05:36Z

Stacks and Queues

← Older revision		Revision as of 20:05, 11 September 2018
Line 33:		Line 33:

	If these operations are applied to a stack, then the values of the pops are: E, R, I, M, A and NIL. After all of the operations, there are three items still on the stack: the N is at the top (it will be the next to be popped, if nothing else is pushed before the pop command), and C is at the bottom. If, instead of using a stack we used a queue, then the values popped would be: A, M, E, R, I and NIL. There would be three items still on the queue: N at the top and C on the bottom. Since items are removed from the bottom of a queue, C would be the next item to be popped regardless of any additional pushes.		If these operations are applied to a stack, then the values of the pops are: E, R, I, M, A and NIL. After all of the operations, there are three items still on the stack: the N is at the top (it will be the next to be popped, if nothing else is pushed before the pop command), and C is at the bottom. If, instead of using a stack we used a queue, then the values popped would be: A, M, E, R, I and NIL. There would be three items still on the queue: N at the top and C on the bottom. Since items are removed from the bottom of a queue, C would be the next item to be popped regardless of any additional pushes.

			=== Pre-2018 Syntax ===

			ACSL Contests pre-2018 used a slightly different, and more liberal, syntax. Consider the following sequence on a stack:

			<syntaxhighlight>
			PUSH(A)
			PUSH(B)
			PUSH(C)
			POP(X)
			POP(Z)
			</syntaxhighlight>

			After the 5 operations, the stack would be left with A as the only element on the stack, the value of C in variable X, and the value of B in variable Z.

			Were the above operations applied to a queue, the queue would be left with C; variable X would contain A; and variable Z would contain B.

	== Trees ==		== Trees ==

Marc Brown: /* Problem 1 */

2018-09-10T06:03:13Z

Problem 1

← Older revision		Revision as of 23:03, 9 September 2018
Line 138:		Line 138:
	=== Problem 1 ===		=== Problem 1 ===

	Consider an initially empty stack. ~~What~~ is the value of Z ~~when these operations are performed:~~		Consider an initially empty stack. After the following operations are performed, what is the value of Z?

	<syntaxhighlight>		<syntaxhighlight>
Line 150:		Line 150:
	</syntaxhighlight>		</syntaxhighlight>

	'''Solution:''' The first POP() stores 8 in Y. The POP() stores 6 in X. Then, 8-6=2 is pushed onto the stack. Finally, the last POP() removes the 2 and stores it in Z.		'''Solution:''' The first POP stores 8 in Y. The POP stores 6 in X. Then, 8-6=2 is pushed onto the stack. Finally, the last POP removes the 2 and stores it in Z.

	=== Problem 2 ===		=== Problem 2 ===

Marc Brown: /* Priority Queues */

2018-09-10T06:01:41Z

Priority Queues

← Older revision		Revision as of 23:01, 9 September 2018
Line 112:		Line 112:
	was building from the letters A, M, E, R, I, C, A, N (in that order); the heap at the right is after a C has been added.		was building from the letters A, M, E, R, I, C, A, N (in that order); the heap at the right is after a C has been added.

			<center>
	{\| class="wikitable"		{\| class="wikitable"
	\|[[File:heap-american.svg\|220px]]\|\|		\|[[File:heap-american.svg\|220px]]\|\|
	[[File:heap-american-insert-c.svg\|220px]]		[[File:heap-american-insert-c.svg\|220px]]
	\|}		\|}
			</center>

	The smallest value is always the root. To delete it (and one can only delete the smallest value), one replaces it with the bottom-most and right-most element, and then walks down the tree making exchanges with the smaller child in order to ensure that the tree is valid. The following pseudo-code formalizes this notion:		The smallest value is always the root. To delete it (and one can only delete the smallest value), one replaces it with the bottom-most and right-most element, and then walks down the tree making exchanges with the smaller child in order to ensure that the tree is valid. The following pseudo-code formalizes this notion:

Marc Brown: /* Trees */

2018-09-10T06:01:13Z

Trees

← Older revision		Revision as of 23:01, 9 September 2018
Line 42:		Line 42:
	The following tree is built from the keys A, M, E, R, I, C, A, N in that order:		The following tree is built from the keys A, M, E, R, I, C, A, N in that order:

			<center>
	[[File:bst-american.svg\|200px]]		[[File:bst-american.svg\|200px]]
			</center>

	The ''root'' of the resulting tree is the node containing the key A. Our ACSL convention places duplicate keys into the tree as if they were less than their equal key. (In some textbooks and software libraries, duplicate keys may be considered larger than their equal key.) The tree has a ''depth'' (sometimes called height) of 3 because the deepest node is 3 nodes below the root. The root node has a depth of 0. Nodes with no children are called leaf nodes; there are four of them in the tree: A, C, I and N. Our ACSL convention is that an ''external node'' is the name given to a place where a new node could be attached to the tree. (In some textbooks, an external node is synonymous with a leaf node.) In the final tree above, there are 9 external nodes; these are not drawn. The tree has an ''internal path length'' of 15 which is the sum of the depths of all nodes. It has an ''external path length'' of 31 which is the sum of the depths of all external nodes. To insert the N (the last key inserted), 3 ''comparisons'' were needed against the root A (>), the M (>), and the R (≤).		The ''root'' of the resulting tree is the node containing the key A. Our ACSL convention places duplicate keys into the tree as if they were less than their equal key. (In some textbooks and software libraries, duplicate keys may be considered larger than their equal key.) The tree has a ''depth'' (sometimes called height) of 3 because the deepest node is 3 nodes below the root. The root node has a depth of 0. Nodes with no children are called leaf nodes; there are four of them in the tree: A, C, I and N. Our ACSL convention is that an ''external node'' is the name given to a place where a new node could be attached to the tree. (In some textbooks, an external node is synonymous with a leaf node.) In the final tree above, there are 9 external nodes; these are not drawn. The tree has an ''internal path length'' of 15 which is the sum of the depths of all nodes. It has an ''external path length'' of 31 which is the sum of the depths of all external nodes. To insert the N (the last key inserted), 3 ''comparisons'' were needed against the root A (>), the M (>), and the R (≤).
Line 87:		Line 89:
	These diagrams illustrate the algorithm using the tree above. At the left, we delete I (0 children); in the middle, we delete the R (1 child); and at the right, we delete the M (2 children).		These diagrams illustrate the algorithm using the tree above. At the left, we delete I (0 children); in the middle, we delete the R (1 child); and at the right, we delete the M (2 children).

			<center>
	{\| class ="wikitable"		{\| class ="wikitable"
	\|[[File:bst-american-del-i.svg\|200px]]		\|[[File:bst-american-del-i.svg\|200px]]
Line 92:		Line 95:
	\|[[File:bst-american-del-m.svg\|200px]]		\|[[File:bst-american-del-m.svg\|200px]]
	\|}		\|}
			</center>

	There are also general trees that use the same terminology, but they have 0 or more ''subnodes'' which can be accessed with an array or linked list of pointers. ''Pre-order'' and ''post-order'' traversals are possible with these trees, but the other algorithms do not work in the same way. Applications of general trees include game theory, organizational charts, family trees, etc.		There are also general trees that use the same terminology, but they have 0 or more ''subnodes'' which can be accessed with an array or linked list of pointers. ''Pre-order'' and ''post-order'' traversals are possible with these trees, but the other algorithms do not work in the same way. Applications of general trees include game theory, organizational charts, family trees, etc.