Balanced Search Trees - Revision history

Admin at 00:21, 4 July 2017

2017-07-04T00:21:48Z

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

			==Define the goal==

	On the [[Binary Search Trees]] page we covered the use of a binary tree to store items in a sorted order. In the analysis of binary search trees, adding and removing from a search tree is O(h), where h is the height of the tree. In the worst case, the tree can have all nodes in the left or right subtree, and each node have one child, such that the height is n, and addition/removal is O(n).		On the [[Binary Search Trees]] page we covered the use of a binary tree to store items in a sorted order. In the analysis of binary search trees, adding and removing from a search tree is O(h), where h is the height of the tree. In the worst case, the tree can have all nodes in the left or right subtree, and each node have one child, such that the height is n, and addition/removal is O(n).

	Our goal is to design a binary search tree such that we can '''guarantee''' O(log N) insertion and deletion.		Our goal is to design a binary search tree such that we can '''guarantee''' O(log N) insertion and deletion.

			==Recap of other data structures==

	Let's just recap some other data structures before we do so:		Let's just recap some other data structures before we do so:
Line 13:		Line 17:
	* Hash tables: O(1) insertion and deletion, but not in sorted order		* Hash tables: O(1) insertion and deletion, but not in sorted order
	* Sorted hash tables: now we are starting to get closer to a key-value tree, or a structure that maintains key-value pairs in sorted order		* Sorted hash tables: now we are starting to get closer to a key-value tree, or a structure that maintains key-value pairs in sorted order

			==Recap of Binary Search Trees==

			{{Main\|Binary Search Trees}}

	Reviewing what we know about binary search trees:		Reviewing what we know about binary search trees:
Line 18:		Line 26:
	* A proper binary tree is a binary tree in which each node has 0 or 2 children.		* A proper binary tree is a binary tree in which each node has 0 or 2 children.
	* A full binary tree is a binary tree in which each level of the tree is completely full.		* A full binary tree is a binary tree in which each level of the tree is completely full.
	* Properties of binary trees~~, and full binary trees~~
			Properties of binary trees:
	* Height is between log(n+1)-1 and n-1		* Height is between log(n+1)-1 and n-1
	* Number of external nodes = number of internal nodes + 1		* Number of external nodes = number of internal nodes + 1
	* Performance:
	** O(1) left/right, sibling/child, number of children, parent
	** O(c) to get children(p), where c is number of children
	** O(d + 1) depth of position p (where d is depth of position p)
	** O(N) height
	** O(1) add root, add left, add right, replace, delete
	** O(N) tree traversal (in order, pre-order, post-order) (breadth-first, depth-first)

			Performance:
			* O(1) left/right, sibling/child, number of children, parent
			* O(c) to get children(p), where c is number of children
			* O(d + 1) depth of position p (where d is depth of position p)
			* O(1) add root, add left, add right, replace, delete
			* O(N) tree traversal (in order, pre-order, post-order) (breadth-first, depth-first)

			Note that binary search trees are not, by default, balanced, so when we say an operation costs O(h), where h is height of binary tree, h can potentially be as large as n or as small as log(n).

			==Modifying the binary search tree==

			To modify the binary search tree data structure to achieve guaranteed log N performance, we need a way to ensure the height of the tree is limited to a reasonable value. The way we do this is by defining a set of rebalancing operations that will not change the order of the items in the tree but that will change the relative heights of subtrees of nodes, allowing nodes to be shifted between left and right subtrees.



	{{SearchTreesFlag}}		{{SearchTreesFlag}}

Admin at 20:14, 3 July 2017

2017-07-03T20:14:33Z

← Older revision		Revision as of 20:14, 3 July 2017
Line 23:		Line 23:
	* Performance:		* Performance:
	** O(1) left/right, sibling/child, number of children, parent		** O(1) left/right, sibling/child, number of children, parent
			** O(c) to get children(p), where c is number of children
	** O(d + 1) depth of position p (where d is depth of position p)		** O(d + 1) depth of position p (where d is depth of position p)
	** O(N) height		** O(N) height
	** O(1) add root, add left, add right, replace, delete		** O(1) add root, add left, add right, replace, delete
			** O(N) tree traversal (in order, pre-order, post-order) (breadth-first, depth-first)

Admin at 20:11, 3 July 2017

2017-07-03T20:11:28Z

← Older revision		Revision as of 20:11, 3 July 2017
Line 11:		Line 11:
	* Stacks/queues: provide O(1) insert/remove, but no random access		* Stacks/queues: provide O(1) insert/remove, but no random access
	* Priority queues: while these maintain data in a sorted order, like queues, they provide no random access		* Priority queues: while these maintain data in a sorted order, like queues, they provide no random access
			* Hash tables: O(1) insertion and deletion, but not in sorted order
			* Sorted hash tables: now we are starting to get closer to a key-value tree, or a structure that maintains key-value pairs in sorted order

			Reviewing what we know about binary search trees:
			* Binary trees are trees with the property that each node has at most two children. (Left precedes right.)
			* A proper binary tree is a binary tree in which each node has 0 or 2 children.
			* A full binary tree is a binary tree in which each level of the tree is completely full.
			* Properties of binary trees, and full binary trees
			* Height is between log(n+1)-1 and n-1
			* Number of external nodes = number of internal nodes + 1
			* Performance:
			** O(1) left/right, sibling/child, number of children, parent
			** O(d + 1) depth of position p (where d is depth of position p)
			** O(N) height
			** O(1) add root, add left, add right, replace, delete

Admin at 19:46, 3 July 2017

2017-07-03T19:46:12Z

← Older revision		Revision as of 19:46, 3 July 2017
Line 1:		Line 1:
	See also: [[Trees]] and [[Binary Search Trees]]		See also: [[Trees]] and [[Binary Search Trees]]

	In the analysis of binary search trees, ~~we see that~~ adding and removing from a search tree is O(h), where h is the height of the tree. In the worst case, the tree can have all nodes in the left or right subtree, and each node have one child, such that the height is n, and addition/removal is O(n).		On the [[Binary Search Trees]] page we covered the use of a binary tree to store items in a sorted order. In the analysis of binary search trees, adding and removing from a search tree is O(h), where h is the height of the tree. In the worst case, the tree can have all nodes in the left or right subtree, and each node have one child, such that the height is n, and addition/removal is O(n).

	Our goal is to design a ~~data structure where~~ we can guarantee O(log N) insertion and deletion.		Our goal is to design a binary search tree such that we can '''guarantee''' O(log N) insertion and deletion.

	Let's just recap some other data structures before we do so:		Let's just recap some other data structures before we do so:
	* Unsorted array: this is definitely out, since this is O(N) insertion and O(N) deletion		* Unsorted array: this is definitely out, since this is O(N) insertion and O(N) deletion
	* Sorted array: we can find the insertion index of our new node in O(log N) time, but if we're inserting to the front of the array, it costs O(N) to move all the elements back		* Sorted array: we can find the insertion index of our new node in O(log N) time, but if we're inserting to the front of the array, it costs O(N) to move all the elements back
	* Linked list: we can perform an O(1) insertion, but to ~~get to where we are inserting can take~~ O(N) time.		* Linked list: we can perform an O(1) insertion, but actually getting to the insertion index takes O(N) time
			* Stacks/queues: provide O(1) insert/remove, but no random access
			* Priority queues: while these maintain data in a sorted order, like queues, they provide no random access



	{{~~SearchTreeFlag~~}}
			{{SearchTreesFlag}}

Admin: Created page with "See also: Trees and Binary Search Trees In the analysis of binary search trees, we see that adding and removing from a search tree is O(h), where h is the height of t..."

2017-07-03T19:38:30Z

Created page with "See also: Trees and Binary Search Trees In the analysis of binary search trees, we see that adding and removing from a search tree is O(h), where h is the height of t..."

New page

See also: [[Trees]] and [[Binary Search Trees]]

In the analysis of binary search trees, we see that adding and removing from a search tree is O(h), where h is the height of the tree. In the worst case, the tree can have all nodes in the left or right subtree, and each node have one child, such that the height is n, and addition/removal is O(n).

Our goal is to design a data structure where we can *guarantee* O(log N) insertion and deletion.

Let's just recap some other data structures before we do so:
* Unsorted array: this is definitely out, since this is O(N) insertion and O(N) deletion
* Sorted array: we can find the insertion index of our new node in O(log N) time, but if we're inserting to the front of the array, it costs O(N) to move all the elements back
* Linked list: we can perform an O(1) insertion, but to get to where we are inserting can take O(N) time.

{{SearchTreeFlag}}