Difference between revisions of "Binary Search Tree Assignment"

From CSE425S Wiki
Jump to navigation Jump to search
Line 45: Line 45:
  
 
==insert==
 
==insert==
{{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
Line 73: Line 72:
 
[https://en.wikipedia.org/wiki/Binary_search_tree#Deletion Wikipedia BST Deletion]
 
[https://en.wikipedia.org/wiki/Binary_search_tree#Deletion Wikipedia BST Deletion]
  
{{CurriedFunction}}
 
 
  fun remove (equal_less_greater_function:'a -> order) (t:'a tree) : 'a tree =
 
  fun remove (equal_less_greater_function:'a -> order) (t:'a tree) : 'a tree =
 
     raise NotYetImplemented
 
     raise NotYetImplemented
Line 80: Line 78:
 
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]
  
{{CurriedFunction}}
 
 
  fun find (equal_less_greater_function : 'a -> order) (t:'a tree) : 'a option =  
 
  fun find (equal_less_greater_function : 'a -> order) (t:'a tree) : 'a option =  
 
     raise NotYetImplemented
 
     raise NotYetImplemented
Line 95: Line 92:
 
  fun fold_rnl f init t =  
 
  fun fold_rnl f init t =  
 
     fold_order_hof RNL f init t
 
     fold_order_hof RNL f init t
 
=Applications=
 
{{SMLToImplement|apps_using_binary_tree|max_height<br/>sum_int_tree|binary_tree}}
 
 
Be sure to use <code>BinaryTree.LEAF</code> and <code>BinaryTree.BRANCH</code>.
 
 
Alternatively, use <code>open BinaryTree</code> to pollute your namespace so that you can use <code>BRANCH</code> and <code>LEAF</code>.
 
 
==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=
 
=Testing=
{{SMLUnitTest|binary_tree_and_apps|binary_tree}}
+
{{SMLUnitTest|binary_search_tree|binary_search_tree}}
  
 
=Pledge, Acknowledgments, Citations=
 
=Pledge, Acknowledgments, Citations=
{{Pledge|studio-binary-tree}}
+
{{Pledge|studio-binary-search-tree}}

Revision as of 08:46, 15 October 2020

We will implement a binary search tree data structure as well as a few Higher Order Function Hall of Fame inductees.

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

LNR would produce: ABCDEFGHI
RNL would produce: IHGFEDCBA

In-order LNR

Reverse in-order RNL

 datatype traversal_order = LNR | RNL

Code to Implement

file: src/main/sml/binary_tree/binary_tree.sml Smlnj-logo.png
functions: insert
remove
find
...
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_tree : ('k compare_function * ('a,'k) to_key_function) -> ('a,'k) tree
    val create_empty_simple_tree : ('a compare_function) -> ('a,'a) 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 to_string : ('a -> string) -> (('a,'k) tree) -> string
end

insert

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:

AVL-tree-delete.svg

Building a helper function will likely be helpful.

Wikipedia BST Deletion

fun remove (equal_less_greater_function:'a -> order) (t:'a tree) : 'a tree =
    raise NotYetImplemented

find

reference: List.find

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

Testing

file: unit_test_binary_search_tree.sml
source folder: src/test/sml/binary_search_tree

Pledge, Acknowledgments, Citations

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

More info about the Honor Pledge