Binary Search Tree Assignment

We will implement a binary search tree data structure as well as Higher Order Function Hall of Fame inductees: find and fold.

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

• In-order LNR

• Reverse in-order RNL

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.

standard approach

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 the right 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.

Wikipedia BST Deletion

alternate approach?

Can you come up with a different approach that produces a clean solution while still providing O(lg(N)) expected performance?

find

reference: List.find

fun find(t:('a,'k) tree, item_key:'k) : 'a option = 
    raise NotYetImplemented

fold

reference: List.foldl foldr

LNR would produce: ABCDEFGHI
RNL would produce: IHGFEDCBA

	(*
	 * depth-first, in-order traversal
	 * https://en.wikipedia.org/wiki/Tree_traversal#In-order_(LNR)
	 *)
	fun fold_lnr(f, init, t) = 
			raise Fail("NotYetImplemented")

	(*
	 * depth-first, reverse in-order traversal
	 * https://en.wikipedia.org/wiki/Tree_traversal#Reverse_in-order_(RNL)
	 *)
	fun fold_rnl(f, init, t) = 
			raise Fail("NotYetImplemented")

Debugging

debug_binary_search_tree

file: debug_binary_search_tree.sml

in folder: src/test/sml/run_binary_search_tree_testing

BinarySearchTree to_graphviz_dot

	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

graphviz dot vs code

search for "graphviz dot" in vs code extensions marketplace

Testing

Complete

source folder:	src/test/sml/binary_search_tree
how to run with CM.make verbosity off:	sml -Ccm.verbose=false run_binary_search_tree_testing.sml
how to run with CM.make verbosity on:	sml run_binary_search_tree_testing.sml

note: ensure that you have removed all printing to receive credit for any assignment.

SML Error Messages

Without Remove

sml -Ccm.verbose=false run_binary_search_tree_testing.sml --remove=false

sml run_binary_search_tree_testing.sml --remove=false

Pledge, Acknowledgments, Citations

file:

studio-binary-search-tree-pledge-acknowledgments-citations.txt

More info about the Honor Pledge