Binary Search Trees/ADT - Revision history

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

2019-10-09T03:18:15Z

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

← Older revision		Revision as of 03:18, 9 October 2019
Line 1:		Line 1:
	This page covers an abstract data type (or, a generic interface for a data container) for binary search trees. These are trees (directed acyclic graphs) that follow a particular convention or interface, and provide certain basic functions. See [[Trees/ADT]] or [[Binary Trees/ADT]] for other, related tree-based abstract data types.		This page covers an abstract data type (or, a generic interface for a data container) for binary search trees. These are trees (directed acyclic graphs) that follow a particular convention or interface, and provide certain basic functions. See [[Trees/ADT]] or [[Binary Trees/ADT]] for other, related tree-based abstract data types.

	See also BinarySearchTree class here: https://charlesreid1.com~~:3000~~/cs/java/src/master/trees/search-trees/Weiss.java		See also BinarySearchTree class here: https://git.charlesreid1.com/cs/java/src/master/trees/search-trees/Weiss.java

	or LinkedBinTree here: https://charlesreid1.com~~:3000~~/cs/java/src/master/trees/LinkedBinTree.java		or LinkedBinTree here: https://git.charlesreid1.com/cs/java/src/master/trees/LinkedBinTree.java

	==Trees==		==Trees==

2017-06-17T05:25:47Z

2017-06-17T05:24:50Z

← Older revision		Revision as of 05:24, 17 June 2017
Line 1:		Line 1:
	See [[Trees/ADT]] or [[Binary Trees/ADT]]		This page covers an abstract data type (or, a generic interface for a data container) for binary search trees. These are trees (directed acyclic graphs) that follow a particular convention or interface, and provide certain basic functions. See [[Trees/ADT]] or [[Binary Trees/ADT]] for other, related tree-based abstract data types.

			See also BinarySearchTree class here: https://charlesreid1.com:3000/cs/java/src/master/trees/search-trees/Weiss.java

			or LinkedBinTree here: https://charlesreid1.com:3000/cs/java/src/master/trees/LinkedBinTree.java

	==Trees==		==Trees==

2017-06-17T05:21:48Z

← Older revision		Revision as of 05:21, 17 June 2017
Line 1:		Line 1:
	See [[Trees/ADT]] or [[Binary Trees/ADT]]		See [[Trees/ADT]] or [[Binary Trees/ADT]]

			==Trees==

			Binary trees should follow the basic tree ADT and implement:
			* size
			* isempty

			Further:
			* iterable
			* depth
			* height

			Utility methods (confusing, b/c using Tree, but checking Node...)
			* isInternal
			* isExternal
			* isLeaf
			* isRoot
			* parent
			* children
			* numberOfChildren

			Trees:
			* allPositions
			* iterator

			Some of these can be left out, particularly in a trimmed-down binary tree.

			==Binary Trees==

			The binary tree implementation can replace the children functionality with a left and right. See [[Binary_Trees/ADT]], which we follow here.

			Node class provides two methods to access two children:
			* left/getLeft
			* right/getRight

			Additional:
			* sibling
			* parent

			Support iteration:
			* positions() should return all positions in tree
			* iter() should make it iterable

			==Trimming Down==

			To really trim things down, our binary search tree only implements a few methods, so we can focus on the actual search tree organization.

			The minimal methods for a binary search tree are:
			* insert
			* remove
			* contains/find

			Optionally:
			* findMin/findMax

			These are "easiest" to implement recursively (and usually, easiest to handle the empty case separately.)












			[[Category:Trees]]
			[[Category:ADT]]
			[[Category:Binary Trees]]

2017-06-17T05:09:52Z

Created page with "See Trees/ADT or Binary Trees/ADT"

New page

See [[Trees/ADT]] or [[Binary Trees/ADT]]