Dictionaries - Revision history

Admin: /* Dictionaries interface */

2017-06-21T04:38:40Z

Dictionaries interface

← Older revision		Revision as of 04:38, 21 June 2017
Line 26:		Line 26:

	Dictionaries implement the following operations:		Dictionaries implement the following operations:
	* search(d,k) - given a search key k, ~~preeturn~~ a pointer to the element in d corresponding to key value k (if one exists)		* search(d,k) - given a search key k, return a pointer to the element in d corresponding to key value k (if one exists)
	* insert(d,x) - given a data item, add it to the set of data		* insert(d,x) - given a data item, add it to the set of data
	* delete(d,x) - given a pointer to a given data item x in the dictionary d, remove it from d		* delete(d,x) - given a pointer to a given data item x in the dictionary d, remove it from d

Admin: /* Flags */

2017-06-21T03:42:25Z

Flags

← Older revision		Revision as of 03:42, 21 June 2017
Line 84:		Line 84:

	=Flags=		=Flags=

	~~{{DictionariesFlag}}~~

	[[Category:Dictionaries]]		[[Category:Dictionaries]]
			[[Category:Maps]]
			{{MapsFlag}}

Admin: /* Flags */

2017-06-21T03:38:13Z

Flags

← Older revision		Revision as of 03:38, 21 June 2017
Line 85:		Line 85:
	=Flags=		=Flags=

	{{~~DataStructuresFlag~~}}		{{DictionariesFlag}}

	[[Category:Dictionaries]]		[[Category:Dictionaries]]

Admin: /* Question 3-7 */

2017-06-05T06:26:24Z

Question 3-7

← Older revision		Revision as of 06:26, 5 June 2017
Line 67:		Line 67:
	'''Question 3-7) Suppose you have access to a balanced dictionary structure that supports insert, delete, min, max, successor, predecessor, all in O(log n) time. How would you modify the insert/delete operations so that they take O(log n) time,but min/max now takes O(1)?		'''Question 3-7) Suppose you have access to a balanced dictionary structure that supports insert, delete, min, max, successor, predecessor, all in O(log n) time. How would you modify the insert/delete operations so that they take O(log n) time,but min/max now takes O(1)?

	When inserting or deleting, check if we have a new minimum.		When inserting or deleting, check if we have a new minimum/maximum. Keeping track of minimum element or maximum element then costs O(1) to return.

	<pre>		<pre>

Admin: /* Skiena Chapter 3 questions */

2017-06-05T06:25:13Z

Skiena Chapter 3 questions

@@ Line 62: / Line 62: @@
 * Off-by-one array: the numbers passed in from 1 to n are represented in an array of length n, with the kth number represented by the k-1th cell.
 * hash table: key value is given, turns into unique integer, looked up in O(1) time
 =Flags=

Admin: /* Dictionaries and Binary Trees */

2017-06-05T06:21:10Z

Dictionaries and Binary Trees

← Older revision		Revision as of 06:21, 5 June 2017
Line 10:		Line 10:

	Dictionaries can be implemented as binary trees. Dictionaries are designed as by-value lookup, and a binary tree is a way of storing values in such a way that they are maintained in sorted order, and therefore easy to find in log(n) time.		Dictionaries can be implemented as binary trees. Dictionaries are designed as by-value lookup, and a binary tree is a way of storing values in such a way that they are maintained in sorted order, and therefore easy to find in log(n) time.

			See [[Advanced Data Structures]] for more about Skiena coverage of data structures; Skiena discusses the connection between Dictionary types and binary trees in great detail, and the questions below explore these concepts as well.

			See [[Binary Trees]], particularly [[Binary_Trees#Question_3-6]], for more.

	==Skiena Chapter 3 notes==		==Skiena Chapter 3 notes==

Admin: /* Dictionary data type - definition */

2017-06-05T06:19:55Z

Dictionary data type - definition

← Older revision		Revision as of 06:19, 5 June 2017
Line 6:		Line 6:

	These types of data sets naturally lend themselves to a structure that partitions data based on its sort value, as in a binary tree. This allows operations to happen faster, because the lookup key itself guides the process of finding the corresponding data in the data structure.		These types of data sets naturally lend themselves to a structure that partitions data based on its sort value, as in a binary tree. This allows operations to happen faster, because the lookup key itself guides the process of finding the corresponding data in the data structure.

			==Dictionaries and Binary Trees==

			Dictionaries can be implemented as binary trees. Dictionaries are designed as by-value lookup, and a binary tree is a way of storing values in such a way that they are maintained in sorted order, and therefore easy to find in log(n) time.

	==Skiena Chapter 3 notes==		==Skiena Chapter 3 notes==

Admin: /* Question 3-6 */

2017-06-05T06:19:01Z

Question 3-6

@@ Line 54: / Line 54: @@
 * Off-by-one array: the numbers passed in from 1 to n are represented in an array of length n, with the kth number represented by the k-1th cell.
 * hash table: key value is given, turns into unique integer, looked up in O(1) time
 =Flags=

Admin: /* Question 3-6 */

2017-06-05T06:17:29Z

Question 3-6

← Older revision		Revision as of 06:17, 5 June 2017
Line 57:		Line 57:
	===Question 3-6===		===Question 3-6===

	Question 3-6) Describe how to modify any balanced tree structure such that search, insert, delete, min, max each take the expected amount of time, O(log n), but sucessor and predecessor methods now take O(1) time each.		'''Question 3-6) Describe how to modify any balanced tree structure such that search, insert, delete, min, max each take the expected amount of time, O(log n), but sucessor and predecessor methods now take O(1) time each. What modifications are required, and to which methods?'''

	~~What modifications are required~~, ~~and~~ to ~~which methods?~~		The methods:
			* Predecessor(D,k) - returns the predecessor key (in order) to the given key k
			* Successor(D,k) - returns the successor key to the given key k

	~~Predecessor~~(~~D,k~~) ~~- returns the predecessor key (~~in ~~order) to the given key k~~		Question is, how to we implement neighbor lookup in O(1) time in a balanced tree?

	~~Successor(D~~,k) - ~~returns~~ the ~~successor key~~ to ~~the given key k~~		Two options:
			* Option one - add a previous and next node pointers. This increases the complexity of the bookkeeping, and of the add/insert/remove methods, which now have to traverse the tree to fix their links.
			* Option two - make a data tree that is twice as big, and only holds data in the bottom-most leaf nodes. This obviates the need for a next and previous pointer, because the tree is easy to navigate - up and over... at most log(n) operations to traverse tree.

	~~Question is, how to we implement neighbor lookup in O(1) time in a balanced tree?~~		Option one:

	~~We could store a previous pointer and a next pointer~~

	We would need to modify the add() and insert() method, the delete method, no need to modify search or min or max methods.		We would need to modify the add() and insert() method, the delete method, no need to modify search or min or max methods.

	We modify them to keep track of the previous node. Finding the previous node would be somewhat tricky logic. When we add a new node, find its next and previous nodes, and link them correctly.		We modify them to keep track of the previous node. Finding the previous node would be somewhat tricky logic. When we add a new node, find its next and previous nodes, and link them correctly.

			Option two:

	It would be algorithmically easier (but more expensive and more complicated implementation wise) to use a tree structure with only data in the leaf nodes. Finding/keeping track of next or previous node then doesn't require the extra two pointers and the extra logic of traversing a binary tree, it just requires twice the number of nodes (tree of size N has N/2 leaf nodes).		It would be algorithmically easier (but more expensive and more complicated implementation wise) to use a tree structure with only data in the leaf nodes. Finding/keeping track of next or previous node then doesn't require the extra two pointers and the extra logic of traversing a binary tree, it just requires twice the number of nodes (tree of size N has N/2 leaf nodes).

			This also requires implementation of the entire data structure again, and it is not so obvious how you keep a tree structure like that balanced and dynamically resized.

	=Flags=		=Flags=

Admin: /* Skiena Chapter 3 questions */

2017-06-05T06:13:51Z

Skiena Chapter 3 questions

@@ Line 42: / Line 42: @@
 ==Skiena Chapter 3 questions==
-====Question 3-4====
+===Question 3-4===
 '''Question 3-4) Design a dictionary structure in which search, insertion, and deletion can be handled in O(1) time.'''
@@ Line 54: / Line 54: @@
 * Off-by-one array: the numbers passed in from 1 to n are represented in an array of length n, with the kth number represented by the k-1th cell.
 * hash table: key value is given, turns into unique integer, looked up in O(1) time
 =Flags=