Advertisement
DasT1k

Tree delete elem func

Oct 29th, 2017
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
F# 0.80 KB | None | 0 0
  1. let rec findInOrderPredecessor (tree : Tree<'a>) =
  2.  match tree with
  3.  | Empty -> Empty
  4.  | Branch (_, _, Empty) -> tree
  5.  | Branch (_, _, right) -> findInOrderPredecessor right
  6.  
  7. let rec delete value (tree : Tree<'a>) =
  8.   match tree with
  9.   | Empty -> Empty
  10.   | Branch (value', left, right) when value < value' ->
  11.     let left' = delete value left
  12.    Branch (value', left', right)
  13.  | Branch (value', left, right) when value > value' ->
  14.    let right' = delete value right
  15.     Branch (value', left, right')
  16.   | Branch (_, Empty, Empty) ->
  17.     Empty
  18.   | Branch (_, left, Empty) ->
  19.     left
  20.   | Branch (_, Empty, right) ->
  21.     right
  22.   | Branch (_, left, right) ->
  23.     let (Branch(value', _, _)) = findInOrderPredecessor left
  24.    let left' = delete value' left
  25.    Branch (value', left', right)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement