Difference between revisions of "Binary Search Tree Assignment"
| Line 22: | Line 22: | ||
datatype traversal_order = LNR | RNL | datatype traversal_order = LNR | RNL | ||
| − | = | + | =Code to Implement= |
{{SMLToImplement|binary_tree|insert<br/>remove<br/>find<br/>...|binary_tree}} | {{SMLToImplement|binary_tree|insert<br/>remove<br/>find<br/>...|binary_tree}} | ||
datatype 'a tree = LEAF | BRANCH of 'a tree * 'a * 'a tree | datatype 'a tree = LEAF | BRANCH of 'a tree * 'a * 'a tree | ||
| − | + | ==insert== | |
| − | |||
{{CurriedFunction}} | {{CurriedFunction}} | ||
fun insert (compare_function:(('a * 'a) -> order)) (t:'a tree) (item:'a) : 'a tree = | fun insert (compare_function:(('a * 'a) -> order)) (t:'a tree) (item:'a) : 'a tree = | ||
raise NotYetImplemented | raise NotYetImplemented | ||
| − | + | ==remove== | |
Remove contains the most challenging aspect of this studio. When instructed to remove a node from a tree, there are several cases: | Remove contains the most challenging aspect of this studio. When instructed to remove a node from a tree, there are several cases: | ||
| − | + | ===not found=== | |
What will indicate that you reached the point where you know the node is not found in the tree?<br>note: this has a trivial solution. | What will indicate that you reached the point where you know the node is not found in the tree?<br>note: this has a trivial solution. | ||
| − | + | ===no child in the left tree=== | |
How will you detect this pattern?<br>note: this has a trivial solution. | How will you detect this pattern?<br>note: this has a trivial solution. | ||
| − | + | ===no child in the right tree=== | |
how will you detect this pattern?<br>note: this has a trivial solution. | how will you detect this pattern?<br>note: this has a trivial solution. | ||
| − | + | ===no children are present=== | |
If you need to remove a node and it has both children, now you have a legit problem. You must maintain a correct binary search tree. | If you need to remove a node and it has both children, now you have a legit problem. You must maintain a correct binary search tree. | ||
| Line 60: | Line 59: | ||
raise NotYetImplemented | raise NotYetImplemented | ||
| − | + | ==find== | |
reference: [http://sml-family.org/Basis/list.html#SIG:LIST.find:VAL List.find] | reference: [http://sml-family.org/Basis/list.html#SIG:LIST.find:VAL List.find] | ||
| Line 67: | Line 66: | ||
raise NotYetImplemented | raise NotYetImplemented | ||
| − | + | ==fold_order_hof== | |
reference: [http://sml-family.org/Basis/list.html#SIG:LIST.foldl:VAL List.foldl] | reference: [http://sml-family.org/Basis/list.html#SIG:LIST.foldl:VAL List.foldl] | ||
Revision as of 08:44, 15 October 2020
We will implement a binary search tree data structure as well as a few Higher Order Function Hall of Fame inductees.
Contents
Background
order
SML's General structure's order
datatype order = LESS | EQUAL | GREATER
Values of type order are used when comparing elements of a type that has a linear ordering.
Functions which take (('a * 'a) -> order) functions behave as Int.compare does:
- compare (i, j)
- returns LESS, EQUAL, or GREATER when i is less than, equal to, or greater than j, respectively.
list
We will implement some of the higher ordered functions list provides on our binary tree.
traversal order
RNL would produce: IHGFEDCBA
datatype traversal_order = LNR | RNL
Code to Implement
| file: | src/main/sml/binary_tree/binary_tree.sml |  |
| functions: | insert remove find ... |
datatype 'a tree = LEAF | BRANCH of 'a tree * 'a * 'a tree
insert
note: this function is curried.
fun insert (compare_function:(('a * 'a) -> order)) (t:'a tree) (item:'a) : 'a tree =
raise NotYetImplemented
remove
Remove contains the most challenging aspect of this studio. When instructed to remove a node from a tree, there are several cases:
not found
What will indicate that you reached the point where you know the node is not found in the tree?
note: this has a trivial solution.
no child in the left tree
How will you detect this pattern?
note: this has a trivial solution.
no child in the right tree
how will you detect this pattern?
note: this has a trivial solution.
no children are present
If you need to remove a node and it has both children, now you have a legit problem. You must maintain a correct binary search tree.
A common approach is to choose one of the following:
- remove the right most descendant in the left child, and promote it to be the node at the current level, or
- remove the left most descendant in right left child, and promote it to be the node at the current level
The image below shows finding the left most child in the right subtree for promotion:
Building a helper function will likely be helpful.
note: this function is curried.
fun remove (equal_less_greater_function:'a -> order) (t:'a tree) : 'a tree =
raise NotYetImplemented
find
reference: List.find
note: this function is curried.
fun find (equal_less_greater_function : 'a -> order) (t:'a tree) : 'a option =
raise NotYetImplemented
fold_order_hof
reference: List.foldl
note: this function is curried.
fun fold_order_hof (order:traversal_order) (f : 'a * 'b -> 'b) (init : 'b) (t : 'a tree) : 'b =
raise NotYetImplemented
fun fold_lnr f init t = fold_order_hof LNR f init t fun fold_rnl f init t = fold_order_hof RNL f init t
Applications
| file: | src/main/sml/binary_tree/apps_using_binary_tree.sml | |
| functions: | max_height sum_int_tree |
Be sure to use BinaryTree.LEAF and BinaryTree.BRANCH.
Alternatively, use open BinaryTree to pollute your namespace so that you can use BRANCH and LEAF.
max_height
fun max_height(t : 'a BinaryTree.tree) : int = raise NotYetImplemented
sum_int_tree
fun sum_int_tree(t : int BinaryTree.tree) : int = raise NotYetImplemented
Testing
| file: | unit_test_binary_tree_and_apps.sml | |
| source folder: | src/test/sml/binary_tree |
Pledge, Acknowledgments, Citations
| file: | studio-binary-tree-pledge-acknowledgments-citations.txt |
More info about the Honor Pledge
