Я написал неизменяемую версию, и она работает лучше, чем вышеупомянутая изменяемая. Я только внедрил вставку до сих пор. Я все еще пытаюсь выяснить, какие проблемы с производительностью.
type ILLRBT =
| Red of ILLRBT * int * ILLRBT
| Black of ILLRBT * int * ILLRBT
| Nil
let flip node =
let inline flip node =
match node with
| Red(l, v, r) -> Black(l, v, r)
| Black(l, v, r) -> Red(l, v, r)
| Nil -> Nil
match node with
| Red(l, v, r) -> Black(flip l, v, flip r)
| Black(l, v, r) -> Red(flip l, v, flip r)
| Nil -> Nil
let lRot = function
| Red(l, v, Red(l', v', r'))
| Red(l, v, Black(l', v', r')) -> Red(Red(l, v, l'), v', r')
| Black(l, v, Red(l', v', r'))
| Black(l, v, Black(l', v', r')) -> Black(Red(l, v, l'), v', r')
| _ -> Nil // could raise an error here
let rRot = function
| Red( Red(l', v', r'), v, r)
| Red(Black(l', v', r'), v, r) -> Red(l', v', Red(r', v, r))
| Black( Red(l', v', r'), v, r)
| Black(Black(l', v', r'), v, r) -> Black(l', v', Red(r', v, r))
| _ -> Nil // could raise an error here
let rec insert node value =
match node with
| Nil -> Red(Nil, value, Nil)
| n ->
n
|> function
| Red(Red(_), v, Red(_))
| Black(Red(_), v, Red(_)) as node -> flip node
| x -> x
|> function
| Red(l, v, r) when value < v -> Red(insert l value, v, r)
| Black(l, v, r) when value < v -> Black(insert l value, v, r)
| Red(l, v, r) when value > v -> Red(l, v, insert r value)
| Black(l, v, r) when value > v -> Black(l, v, insert r value)
| x -> x
|> function
| Red(l, v, Red(_))
| Black(l, v, Red(_)) as node -> lRot node
| x -> x
|> function
| Red(Red(Red(_),_,_), v, r)
| Black(Red(Red(_),_,_), v, r) as node -> rRot node
| x -> x
let rec iter node =
seq {
match node with
| Red(l, v, r)
| Black(l, v, r) ->
yield! iter l
yield v
yield! iter r
| Nil -> ()
}