2022-08-14 16:45:17 +08:00
|
|
|
|
namespace Sanchime.DataStructures.Trees
|
|
|
|
|
|
|
|
|
|
module RedBlack =
|
|
|
|
|
|
|
|
|
|
type Color = Red | Black
|
|
|
|
|
|
|
|
|
|
type RedBlackTree<'T> =
|
2022-08-14 17:23:47 +08:00
|
|
|
|
| Node of Color * Left: 'T RedBlackTree * Value: 'T * Right:'T RedBlackTree
|
2022-08-14 17:04:45 +08:00
|
|
|
|
| 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
|
|
|
|
|
|
2022-08-14 22:15:22 +08:00
|
|
|
|
match loop s with
|
|
|
|
|
| Node (_, y, a, b) -> Node (Black, y, a, b)
|
|
|
|
|
| Leaf -> failwith "红黑树插入失败,返回Leaf节点"
|
2022-08-14 17:04:45 +08:00
|
|
|
|
|