Sha256: f55d3511090e45b895b4ec2660c15d20b4b59c1fd9cadf9e191dfe4586149fdc
Contents?: true
Size: 945 Bytes
Versions: 256
Compression:
Stored size: 945 Bytes
Contents
module BinarySearchTree
type Node = { left: Node option; value: int; right: Node option }
let left node = node.left
let right node = node.right
let value node = Some node.value
let singleton value = { left = None; right = None; value = value }
let rec insert newValue (tree: Node) =
let loop newValue =
function
| Some x -> Some <| insert newValue x
| None -> Some <| singleton newValue
match newValue with
| x when x <= tree.value ->
{ tree with left = loop newValue tree.left }
| _ ->
{ tree with right = loop newValue tree.right }
let toList tree =
let rec loop =
function
| Some node -> loop node.left @ [node.value] @ loop node.right
| None -> []
loop <| Some tree
let fromList =
function
| [] -> failwith "Cannot create tree from empty list."
| x::xs -> List.fold (fun acc elem -> insert elem acc) (singleton x) xs
Version data entries
256 entries across 256 versions & 1 rubygems