Sha256: 2a26f025c43a48732de035bbfa634072f473332df3cb2d7ec2f9ae10a0f5f997
Contents?: true
Size: 957 Bytes
Versions: 73
Compression:
Stored size: 957 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 data node = node.value
let private singleton value = { left = None; right = None; value = value }
let rec private 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 sortedData tree =
let rec loop =
function
| Some node -> loop node.left @ [node.value] @ loop node.right
| None -> []
loop <| Some tree
let create =
function
| [] -> failwith "Cannot create tree from empty list."
| x::xs -> List.fold (fun acc elem -> insert elem acc) (singleton x) xs
Version data entries
73 entries across 73 versions & 1 rubygems