Binary Search Trees/ADT: Difference between revisions

Revision as of 05:21, 17 June 2017

Binary trees should follow the basic tree ADT and implement:

Further:

Utility methods (confusing, b/c using Tree, but checking Node...)

Trees:

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

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:

Additional:

Support iteration:

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:

Optionally:

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

@@ Line 1: / Line 1: @@
 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]]