Sanchime.Learn/DataStructures/Trees/RedBlack.fs

30 lines
1.0 KiB
Forth
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

namespace Sanchime.DataStructures.Trees
module RedBlack =
type Color = Red | Black
type RedBlackTree<'T> =
| Node of Color * Left: 'T RedBlackTree * Value: 'T * Right:'T RedBlackTree
| Leaf
let balance = function
| Black, Node (Red, Node (Red, a, x, b), y, c), z, d
| Black, Node (Red, a, x, Node (Red, b, y, c)), z, d
| Black, a, x, Node (Red, Node (Red, b, y, c), z, d)
| Black, a, x, Node (Red, b, y, Node (Red, c, z, d)) ->
Node (Red, Node (Black, a, x, b), y, Node (Black, c, z, d))
| a, b, c, d -> Node (a, b, c, d)
let insert x s =
let rec loop = function
| Leaf -> Node (Red, Leaf, x, Leaf)
| Node (color, a, y, b) as s ->
if x < y then balance (color, loop a, y, b)
elif y < x then balance (color, a, y, loop b)
else s
match loop s with
| Node (_, y, a, b) -> Node (Black, y, a, b)
| Leaf -> failwith "红黑树插入失败返回Leaf节点"