Ich versuche, eine Methode zum Löschen eines Elements aus einer BST zu schreiben. Soweit habe ich das. Ich bin mir nicht sicher, ob ich auf dem richtigen Weg bin oder ob es einen besseren Weg gibt, dies zu tun, indem ich den Mustervergleich verwende, um die verschiedenen Löschfälle abzugleichen, dh: keine Kinder, 1 Kind, 2 Kinder.

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);;

Die Fälle ohne Kinder und ein einzelnes Kind funktionieren einwandfrei, aber wenn der zu löschende Knoten 2 Kinder hat, kann ich nicht herausfinden, wie dieser Fall implementiert werden soll. Ich möchte den Wert dieses Knotens durch das kleinste Element in seinem rechten Teilbaum ersetzen und dann das kleinste Element in seinem rechten Teilbaum entfernen.