Search Trees - Revision history

Admin: /* Notes */

2017-07-03T07:57:48Z

Notes

← Older revision		Revision as of 07:57, 3 July 2017
Line 55:		Line 55:
	*** Add the key-value pair as a new node wherever our search ended		*** Add the key-value pair as a new node wherever our search ended
	* Delete item - Take a key. Start with the empty case - nothing. Search the subtree; if we find something, delete it. Otherwise, rebalance the search tree.		* Delete item - Take a key. Start with the empty case - nothing. Search the subtree; if we find something, delete it. Otherwise, rebalance the search tree.



	==Object Oriented Programming Concepts==		==Object Oriented Programming Concepts==

Admin: /* Flags */

2017-07-03T07:53:02Z

Flags

← Older revision		Revision as of 07:53, 3 July 2017
Line 57:		Line 57:



			==Object Oriented Programming Concepts==

			Notes on using object-oriented programming when assembling a binary search tree class.

	==Flags==		==Flags==

	{{SearchTreesFlag}}		{{SearchTreesFlag}}

Admin at 06:43, 3 July 2017

2017-07-03T06:43:10Z

@@ Line 16: / Line 16: @@
 * [[AVL Search Trees]] - these are balanced binary trees that enforce the constraint that the difference in heights of the left and right subtree is 0 or 1.
 * [[Splay Trees]] - Splay trees are interesting data structures that maintain the most recently accessed keys at the top of the tree, providing an advantage for applications where some keys are accessed more frequently. With a splay tree data structure, these will be accessed faster. You can use [[Amortization]] and the [[Amortization/Accounting Method]] to show that these structures have an amortized log(N) cost for operations.
 ==Flags==
 {{SearchTreesFlag}}

Admin: /* Notes */

2017-07-03T04:53:29Z

Notes

← Older revision		Revision as of 04:53, 3 July 2017
Line 12:		Line 12:

	Some examples of types of sorted trees:		Some examples of types of sorted trees:
	* [[Heaps]] - a tree in which values progress from smallest (at the root node) to largest (at the leaf nodes). The invariant in this case is that any tree position at height h has a key that is smaller than any tree position at height h+1.		* [[Heaps]] - a tree in which values progress from smallest (at the root node) to largest (at the leaf nodes). The invariant in this case is that any tree position at height h has a key that is smaller than any tree position at height h+1. Useful for implementing [[Priority Queues]].
	* [[Binary Search Trees]] - a search tree in which each node is limited to having at most 2 children. Insert and delete methods maintain sorted order. There is no limitation to the height of this tree, so in the worst case the height of the tree is equal to the number of nodes (completely expanded tree).		* [[Binary Search Trees]] - a search tree in which each node is limited to having at most 2 children. Insert and delete methods maintain sorted order. There is no limitation to the height of this tree, so in the worst case the height of the tree is equal to the number of nodes (completely expanded tree).
	* [[AVL Search Trees]] - these are balanced binary trees that enforce the constraint that the difference in heights of the left and right subtree is 0 or 1.		* [[AVL Search Trees]] - these are balanced binary trees that enforce the constraint that the difference in heights of the left and right subtree is 0 or 1.
	* [[Splay Trees]] - Splay trees are interesting data structures that maintain the most recently accessed keys at the top of the tree, providing an advantage for applications where some keys are accessed more frequently. With a splay tree data structure, these will be accessed faster. You can use [[Amortization]] and the [[Amortization/Accounting Method]] to show that these structures have an amortized log(N) cost for operations.		* [[Splay Trees]] - Splay trees are interesting data structures that maintain the most recently accessed keys at the top of the tree, providing an advantage for applications where some keys are accessed more frequently. With a splay tree data structure, these will be accessed faster. You can use [[Amortization]] and the [[Amortization/Accounting Method]] to show that these structures have an amortized log(N) cost for operations.




	==Flags==		==Flags==

	{{SearchTreesFlag}}		{{SearchTreesFlag}}

Admin at 04:52, 3 July 2017

2017-07-03T04:52:50Z

@@ Line 1: / Line 1: @@
 A search tree is a type of data structure that uses a tree to store sorted data. This is a basic idea with many variations, some listed below.
@@ Line 14: / Line 16: @@
 * [[AVL Search Trees]] - these are balanced binary trees that enforce the constraint that the difference in heights of the left and right subtree is 0 or 1.
 * [[Splay Trees]] - Splay trees are interesting data structures that maintain the most recently accessed keys at the top of the tree, providing an advantage for applications where some keys are accessed more frequently. With a splay tree data structure, these will be accessed faster. You can use [[Amortization]] and the [[Amortization/Accounting Method]] to show that these structures have an amortized log(N) cost for operations.

Admin at 04:52, 3 July 2017

2017-07-03T04:52:29Z

← Older revision		Revision as of 04:52, 3 July 2017
Line 10:		Line 10:

	Some examples of types of sorted trees:		Some examples of types of sorted trees:
	* [[~~Heap~~]] - a tree in which values progress from smallest (at the root node) to largest (at the leaf nodes). The invariant in this case is that any tree position at height h has a key that is smaller than any tree position at height h+1.		* [[Heaps]] - a tree in which values progress from smallest (at the root node) to largest (at the leaf nodes). The invariant in this case is that any tree position at height h has a key that is smaller than any tree position at height h+1.
	* [[Binary Search ~~Tree~~]] - a search tree in which each node is limited to having at most 2 children. Insert and delete methods maintain sorted order. There is no limitation to the height of this tree, so in the worst case the height of the tree is equal to the number of nodes (completely expanded tree).		* [[Binary Search Trees]] - a search tree in which each node is limited to having at most 2 children. Insert and delete methods maintain sorted order. There is no limitation to the height of this tree, so in the worst case the height of the tree is equal to the number of nodes (completely expanded tree).
	* [[AVL Search Trees]] - these are balanced binary trees that enforce the constraint that the difference in heights of the left and right subtree is 0 or 1.		* [[AVL Search Trees]] - these are balanced binary trees that enforce the constraint that the difference in heights of the left and right subtree is 0 or 1.
	* [[Splay Trees]] - Splay trees are interesting data structures that maintain the most recently accessed keys at the top of the tree, providing an advantage for applications where some keys are accessed more frequently. With a splay tree data structure, these will be accessed faster. You can use [[Amortization]] and the [[Amortization/Accounting Method]] to show that these structures have an amortized log(N) cost for operations.		* [[Splay Trees]] - Splay trees are interesting data structures that maintain the most recently accessed keys at the top of the tree, providing an advantage for applications where some keys are accessed more frequently. With a splay tree data structure, these will be accessed faster. You can use [[Amortization]] and the [[Amortization/Accounting Method]] to show that these structures have an amortized log(N) cost for operations.

Admin at 04:52, 3 July 2017

2017-07-03T04:52:00Z

← Older revision		Revision as of 04:52, 3 July 2017
Line 1:		Line 1:
	A search tree is a type of data structure that uses a tree to store sorted data.		A search tree is a type of data structure that uses a tree to store sorted data. This is a basic idea with many variations, some listed below.

	~~This~~ is a ~~basic idea~~ with ~~many variations~~. On this ~~wiki some~~ of ~~those variations~~ are ~~described~~ and ~~implemented~~, ~~others~~ are ~~just described~~.		In our notes on [[Trees]], we introduced trees generally as having arbitrary ordering and arbitrary numbers of children per node. Our definition of a tree was recursive:

			{{Quote\|
			"A tree data structure can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root."

			- Wikipedia, "Tree (data structure)" [https://en.wikipedia.org/wiki/Tree_(computer_science)]
			}}

			Some examples of types of sorted trees:
			* [[Heap]] - a tree in which values progress from smallest (at the root node) to largest (at the leaf nodes). The invariant in this case is that any tree position at height h has a key that is smaller than any tree position at height h+1.
			* [[Binary Search Tree]] - a search tree in which each node is limited to having at most 2 children. Insert and delete methods maintain sorted order. There is no limitation to the height of this tree, so in the worst case the height of the tree is equal to the number of nodes (completely expanded tree).
			* [[AVL Search Trees]] - these are balanced binary trees that enforce the constraint that the difference in heights of the left and right subtree is 0 or 1.
			* [[Splay Trees]] - Splay trees are interesting data structures that maintain the most recently accessed keys at the top of the tree, providing an advantage for applications where some keys are accessed more frequently. With a splay tree data structure, these will be accessed faster. You can use [[Amortization]] and the [[Amortization/Accounting Method]] to show that these structures have an amortized log(N) cost for operations.

Admin: Created page with "A search tree is a type of data structure that uses a tree to store sorted data. This is a basic idea with many variations. On this wiki some of those variations are describe..."

2017-07-03T04:11:15Z

Created page with "A search tree is a type of data structure that uses a tree to store sorted data. This is a basic idea with many variations. On this wiki some of those variations are describe..."

New page

A search tree is a type of data structure that uses a tree to store sorted data.

This is a basic idea with many variations. On this wiki some of those variations are described and implemented, others are just described.