Binary Search Trees - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:18:05Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:18, 9 October 2019
Line 50:		Line 50:
	** right pointer		** right pointer

	These methods are covered in more detail below. Implementations are all here: https://charlesreid1.com~~:3000~~/cs/java/src/master/trees/search-trees/Weiss.java		These methods are covered in more detail below. Implementations are all here: https://git.charlesreid1.com/cs/java/src/master/trees/search-trees/Weiss.java

	===Contains===		===Contains===
Line 152:		Line 152:
	</pre>		</pre>

	Link on git.charlesreid1.com: https://charlesreid1.com~~:3000~~/cs/java/src/master/trees/search-trees/Weiss.java		Link on git.charlesreid1.com: https://git.charlesreid1.com/cs/java/src/master/trees/search-trees/Weiss.java

	===Insert===		===Insert===
Line 169:		Line 169:
	==Binary Search Tree Implementation==		==Binary Search Tree Implementation==

	Implementation following Weiss: https://charlesreid1.com~~:3000~~/cs/java/src/master/trees/search-trees		Implementation following Weiss: https://git.charlesreid1.com/cs/java/src/master/trees/search-trees

	See [[Java/Binary Search Tree]]		See [[Java/Binary Search Tree]]

Admin at 01:00, 4 July 2017

2017-07-04T01:00:12Z

← Older revision		Revision as of 01:00, 4 July 2017
Line 1:		Line 1:
			See also: [[Balanced Search Trees]]

	=Notes=		=Notes=

Admin: /* Implementation Notes */

2017-07-03T10:38:48Z

Implementation Notes

← Older revision		Revision as of 10:38, 3 July 2017
Line 296:		Line 296:

	Insertion and deletion both occur in O(h) time. (Worst case: height is n, so O(n).)		Insertion and deletion both occur in O(h) time. (Worst case: height is n, so O(n).)

			==Big O Analysis==

			Nearly every operation associated with a binary search tree is O(h), since so many operations are working from the top down or bottom up.

			Checking if a key is in a tree: O(h)

			Getting/setting a value from a key: O(h)

			Deleting a position or deleting a key: O(h)

			Finding a position from a key: O(h)

			First/last: O(h)

			Find min/find max: O(h)

			Before/afteR: O(h)

			Find lt, find le, find gt, find ge: O(h)

			Find range: O(s + h) (s is the number of items in the sequence)

			Iterator/reverse iterator: O(n)



			Note: n is the number of items stored in the map.


	=Implementation Notes=		=Implementation Notes=

Admin: /* Flags */

2017-07-03T10:30:40Z

Flags

← Older revision		Revision as of 10:30, 3 July 2017
Line 303:		Line 303:

	=Flags=		=Flags=

			{{SearchTreesFlag}}

	{{TreesFlag}}		{{TreesFlag}}

	[[Category:Trees]]		[[Category:Trees]]
	[[Category:Binary Trees]]		[[Category:Binary Trees]]
	[[Category:Data Structures]]		[[Category:Data Structures]]

Admin: /* Flags */

2017-07-03T10:18:42Z

Flags

← Older revision		Revision as of 10:18, 3 July 2017
Line 296:		Line 296:

	Insertion and deletion both occur in O(h) time. (Worst case: height is n, so O(n).)		Insertion and deletion both occur in O(h) time. (Worst case: height is n, so O(n).)

			=Implementation Notes=

			Notes from combing through Goodrich's implementation:
			* asdf

	=Flags=		=Flags=

Admin: /* Insertions and Deletions */

2017-07-03T10:13:25Z

Insertions and Deletions

@@ Line 278: / Line 278: @@
 * If insert key > nearest node key, add to node's right
 * If insert key < nearest node key, add to node's left
 =Flags=

Admin: /* Searches */

2017-07-03T08:59:41Z

Searches

@@ Line 266: / Line 266: @@
      return p
 </pre>
 =Flags=

Admin: /* Searches */

2017-07-03T08:25:41Z

Searches

← Older revision		Revision as of 08:25, 3 July 2017
Line 248:		Line 248:

	A very important property of binary trees is that their structure allows us to search the tree in the same manner as a binary search algorithm. The algorithm to perform a search for a node on a binary search tree can be structured almost precisely like the binary search algorithm for an array or a list.		A very important property of binary trees is that their structure allows us to search the tree in the same manner as a binary search algorithm. The algorithm to perform a search for a node on a binary search tree can be structured almost precisely like the binary search algorithm for an array or a list.

			Three cases:
			* If target key is equal to our key, return this node
			* If target key is less than our key, call a search on left subtree
			* If target key is greater than our key, call a search on right subtree

	Here is the tree search algorithm:		Here is the tree search algorithm:

Admin: /* Algorithmic Analysis */

2017-07-03T08:24:02Z

Algorithmic Analysis

← Older revision		Revision as of 08:24, 3 July 2017
Line 211:		Line 211:
	* 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.

			==Summary of Operations==

			===Navigation===

			first

			last

			before(p)

			after(p)

			Implementing first/last:
			* If we are looking for the first or last nodes, we want the left-most or right-most node in the tree.
			* So we simply implement a while loop: while there is still a node to the left, walk left.
			* This eventually yields us the minimum node in the tree.
			* However, keep it general.
			* We will want to implement this functionality in other algorithms: find the smallest node in this subtree.
			* Implement first and last as private method, first/last in the subtrees of a given node.

			Implementing before/after:
			* Let's look at the algorithm. The before and after algorithms are symmetric, but we'll do both.
			* Both algorithms examine 2 cases:
			* Case 1: right child is not null
			** Walk right once
			** Walk left until left == null
			** Return walk
			* Case 2: right child is null
			** Walk up once
			** Walk up until parent == null or walk == left(parent)
			** Return parent

			Case 1 steps right once, then left left left. This yields the next element in the sequence. Case 2 walks up until we switch direction or hit the top of the tree.

			===Searches===

			A very important property of binary trees is that their structure allows us to search the tree in the same manner as a binary search algorithm. The algorithm to perform a search for a node on a binary search tree can be structured almost precisely like the binary search algorithm for an array or a list.

			Here is the tree search algorithm:

			<pre>
			def tree_search(T,p,k):
			if k==p.key():
			return p
			else if k<p.key() and T.left(p) is not None:
			return tree_search(T, T.left(p), k)
			else if k>p.key() and T.right(p) is not None:
			return tree_search(T, T.right(p), k)
			return p
			</pre>

	=Flags=		=Flags=

Admin: /* Flags */

2017-07-03T07:55:42Z

Flags

← Older revision		Revision as of 07:55, 3 July 2017
Line 171:		Line 171:
	See [[Java/Binary Search Tree]]		See [[Java/Binary Search Tree]]



			=Algorithmic Analysis=

			Let's examine some of the big-O costs of operations on binary trees.

			==Operations==

			First, let's lay out some basic operations that a binary search tree will need to define. (See also: [[Search Trees]])

			The general categories of operations implemented:
			* Navigation (moving through the tree)
			* Find/Search (finding position corresponding to a particular key)
			* Get/Set/Delete (getting/setting/deleting a node with a particular key/value in the tree)

			Here's a more detailed list:

			Navigation methods:
			* First node - keep traversing left in the tree until we hit the left-most node. This will be the minimum key. (This uses find min subtree method below)
			* Last node - keep traversing right in the tree until we hit the right-most node. This will be the maximum key.
			* Before position - get the position of the node whose key immediately precedes this node's key
			* After position - get the position of the node whose key comes immediately after this node's key
			* In order traversal
			* Reverse order traversal

			Find:
			* Find key - find the node corresponding to key k in SUBTREE
			* Find min - find the node corresponding to the minimum value in SUBTREE
			* Find max - find the value corresponding to the max value in SUBTREE
			* Find tree min - returns first
			* Find tree max - returns first
			* Find greater than or equal to
			* Find less than or equal to
			* Find range

			Get/Set/Delete:
			* Get item - Search for a key, and rebalance the tree. If we find the key, return the value at that position
			* Set item - Take a key-value pair. Start with the empty case, adding as root; otherwise,
			* 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.