Difference between revisions of "Binary Search Tree Assignment"
Line 113: | Line 113: | ||
in folder: <code>src/test/sml/run_binary_search_tree_testing</code> | in folder: <code>src/test/sml/run_binary_search_tree_testing</code> | ||
+ | |||
+ | <nowiki> fun to_graphviz_dot(value_to_string, t) = | ||
+ | let | ||
+ | fun node_to_dot(value) = | ||
+ | "\t" ^ value_to_string(value) ^ " [label= \"{ " ^ value_to_string(value) ^ " | { <child_left> | <child_right> } }\"]" | ||
+ | |||
+ | fun edge_to_dot(parent_value_opt, tag, value) = | ||
+ | case parent_value_opt of | ||
+ | NONE => "" | ||
+ | | SOME(parent_value) => "\t" ^ value_to_string(parent_value) ^ tag ^ " -> " ^ value_to_string(value) | ||
+ | |||
+ | fun nodes_to_dot(bst) = | ||
+ | raise Fail("NotYetImplemented") | ||
+ | |||
+ | fun edges_to_dot(bst, parent_value_opt, tag) = | ||
+ | raise Fail("NotYetImplemented") | ||
+ | |||
+ | |||
+ | (* TODO: bind root *) | ||
+ | val root = raise Fail("NotYetImplemented") | ||
+ | |||
+ | in | ||
+ | "digraph g {\n\n\tnode [\n\t\tshape = record\n\t]\n\n\tedge [\n\t\ttailclip=false,\n\t\tarrowhead=vee,\n\t\tarrowtail=dot,\n\t\tdir=both\n\t]\n\n" ^ nodes_to_dot(root) ^ edges_to_dot(root, NONE, "") ^ "\n}\n" | ||
+ | end | ||
+ | </nowiki> | ||
=Testing= | =Testing= |
Revision as of 09:04, 23 February 2022
We will implement a binary search tree data structure as well as Higher Order Function Hall of Fame inductees: find and fold.
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 (('k * 'k) -> 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
Code to Implement
file: | src/main/sml/binary_tree/binary_tree.sml | ![]() |
functions: | create_empty_tree insert remove find fold_order_hof to_string |
signature BINARY_SEARCH_TREE = sig type 'k compare_function = (('k * 'k) -> order) type ('a,'k) to_key_function = 'a -> 'k type ('a,'k) tree; val create_empty : ('k compare_function * ('a,'k) to_key_function) -> ('a,'k) tree val insert : (('a,'k) tree * 'a) -> (('a,'k) tree * 'a option) val remove : (('a,'k) tree * 'k) -> (('a,'k) tree * 'a option) val find : (('a,'k) tree * 'k) -> 'a option val fold_lnr : ((('a * 'b) -> 'b) * ('b) * (('a,'k) tree)) -> 'b val fold_rnl : ((('a * 'b) -> 'b) * ('b) * (('a,'k) tree)) -> 'b val debug_message : (('a -> string) * (('a,'k) tree)) -> string val to_graphviz_dot : (('a -> string) * (('a,'k) tree)) -> string end
type
(* TODO: replace unit with the datatype(s) and/or type synonym(s) you decide upon *) type ('a,'k) tree = unit
create_empty
fun create_empty(cmp : 'k compare_function, to_key : ('a,'k) to_key_function) : ('a,'k) tree = raise NotYetImplemented
insert
fun insert(t:('a,'k) tree, item:'a) : (('a,'k) tree * 'a option) = raise NotYetImplemented
NOTE: if the key for the specified item matches a key already in the tree, the previous item is replaced.
insert
returns a pair containing the new tree and the (optional) replaced value.
remove
fun remove(t:('a,'k) tree, item_key:'k) : (('a,'k) tree * 'a option) = raise NotYetImplemented
remove
the item whose key matches item_key
, if it is found.
returns a pair of the modified tree and the (optional) removed item.
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.
both 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.
find
reference: List.find
fun find(t:('a,'k) tree, item_key:'k) : 'a option = raise NotYetImplemented
fold
reference: List.foldl foldr
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
Debugging
file: debug_binary_search_tree.sml
in folder: src/test/sml/run_binary_search_tree_testing
fun to_graphviz_dot(value_to_string, t) = let fun node_to_dot(value) = "\t" ^ value_to_string(value) ^ " [label= \"{ " ^ value_to_string(value) ^ " | { <child_left> | <child_right> } }\"]" fun edge_to_dot(parent_value_opt, tag, value) = case parent_value_opt of NONE => "" | SOME(parent_value) => "\t" ^ value_to_string(parent_value) ^ tag ^ " -> " ^ value_to_string(value) fun nodes_to_dot(bst) = raise Fail("NotYetImplemented") fun edges_to_dot(bst, parent_value_opt, tag) = raise Fail("NotYetImplemented") (* TODO: bind root *) val root = raise Fail("NotYetImplemented") in "digraph g {\n\n\tnode [\n\t\tshape = record\n\t]\n\n\tedge [\n\t\ttailclip=false,\n\t\tarrowhead=vee,\n\t\tarrowtail=dot,\n\t\tdir=both\n\t]\n\n" ^ nodes_to_dot(root) ^ edges_to_dot(root, NONE, "") ^ "\n}\n" end
Testing
file: run_complete_unit_test_binary_search_tree.sml
in folder: src/test/sml/run_binary_search_tree_testing
Pledge, Acknowledgments, Citations
file: | studio-binary-search-tree-pledge-acknowledgments-citations.txt |
More info about the Honor Pledge