Question ocmal about a function called remove_max from a three


Hi I have about a function called remove_max from a three I did not understand the mechanism of the function specially when he declares a local variable d’ and x and

type ’ a arbre =
|Noeud of('a arbre*'a*'a arbre);;

let racine =Noeud(Noeud(Vide,5,Vide),6,Noeud(Vide,2,Vide));;


From the looks of it, this seems like a function that is meant to work for a Binary Search Tree.

I think it would be easier to understand if you think about the characteristics of a BST. What is “max” in the concept of a BST? For example, given a diagram/drawing of a BST with their values, would you be able to find its “max”? And what would happen if you try to remove it (what’s the resulting tree)?


i did not understand how the function itterate when it use let(d’,x)=remove_max d in (Noeud(g,y,d’),x)


Perhaps annotating it with comments would help making it clearer? (I’ll use English for this since I’m not familiar with French.):

(** Given a BST, this function returns a new BST with its max element removed,
    as well as the value of the removed node. *)
let rec remove_max = function

  (* First case: Empty BST. There are no "max" of an empty tree,
     so we'll fail here. *)
  | Empty -> failwith "remove-max"

  (* Second case: BST with current node having no right child.
     By definition of a BST, if we're at the rightmost node of a
     tree, it is the maximum value of our BST.

     In this case, we remove this node by returning it's left child
     as the new BST as well as the current node_value. The left
     child will be used in the next case. *)
  | Node (left, node_value, Empty) -> (left, node_value)

  (* Third case: BST with current node having right child. *)
  | Node (left, node_value, right) ->
    (* Okay, since this node has a right child, then by definition of BST
       it CAN'T be the max value, hence we will try to remove the max which,
       also by definition of BST, must be in its right child. That is why we
       call remove_max recursively with `right` as parameter.

       As stated in the annotation of this function, remove_max will return a
       new tree with its max node removed along with the removed value. *)
    let (new_right_tree, removed_max_value) = remove_max right in
    (* Lastly, we return, as a result, the current node with a new right child,
       passing along the removed max value. *)
    (Node (left, node_value, new_right_tree), removed_max_value)

(* To use this function, we can just call `remove_max` with `root`
   as parameter *)
remove_max root


thank you brother god bless you ^^