Удалить элемент из бинарного дерева поиска в F #
Я пытаюсь написать метод для удаления элемента из BST. Пока что это то, что у меня есть. Я не уверен, нахожусь ли я на правильном пути или есть лучший способ сделать это, используя сопоставление с образцом, чтобы соответствовать различным случаям удаления, то есть: нет детей, 1 ребенок, 2 ребенка.
type 'a bst = NL | BinTree of 'a * 'a bst * 'a bst;;
let rec smallest = function
| NL -> failwith "tree is empty"
| BinTree(m, lst, rst) -> if lst = NL then BinTree(m, lst, rst)
else smallest lst;;
let rec smallest2 = function
| NL -> failwith "tree is empty"
| BinTree(m, lst, rst) -> if lst = NL then m
else smallest2 lst;;
let rec rem2 = function
| NL -> NL
| BinTree(m, NL, NL) -> NL
| BinTree(m, NL, rst) -> rst
| BinTree(m, lst, NL) -> lst
| BinTree(m, lst, rst) -> BinTree(smallest2 rst, lst, rst);;
let rec rem x = function
|NL -> failwith "Node doesn't exit"
|BinTree(m, lst, rst) -> if m = x then rem2 (BinTree(m, lst, rst))
elif m < x then BinTree(m, lst, rem x rst)
else BinTree(m, rem x lst, rst);;
Случаи отсутствия дочерних элементов и одного дочернего элемента работают отлично, но когда удаляемый узел имеет 2 дочерних элемента, я не могу понять, как реализовать этот случай. Я хочу заменить значение этого узла наименьшим элементом в правом поддереве, а затем удалить наименьший элемент в правом поддереве.