types - programar - Eliminar un elemento de un árbol de búsqueda binario en F#

arboles binarios ejemplos

Question

Estoy intentando escribir un método para eliminar un elemento de una BST. Hasta ahora, esto es lo que tengo. No estoy seguro de si estoy en el camino correcto o si hay una mejor manera de hacerlo mediante el uso de la coincidencia de patrones para que coincida con los diferentes casos de eliminación, es decir: sin hijos, 1 niño, 2 niños.

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

Los casos de no hijos y un solo hijo funcionan perfectamente, pero cuando el nodo que se va a eliminar tiene 2 hijos, no puedo encontrar la manera de implementar este caso. Quiero reemplazar el valor de ese nodo con el elemento más pequeño en su subárbol derecho, y luego eliminar el elemento más pequeño en su subárbol derecho.

Answer 1

No estoy seguro de entender la lógica que su función de remove está tratando de implementar. La forma habitual de hacerlo es escribir una función recursiva que:

• si x es más pequeño que la corriente, elimine x del subárbol izquierdo recursivamente
• si x es más grande que la actual, elimine x del subárbol de derechos recursivamente
• si x es igual a la corriente, suelte el nodo actual y combine los dos árboles

La forma de codificar esto en F # es escribir una función recursiva usando la coincidencia de patrones, bastante similar a las funciones que escribió:

let rec remove x = function
  | NL -> NL
  | BinTree(m, lst, rst) when x = m -> merge lst rst
  | BinTree(m, lst, rst) when x < m -> BinTree(m, remove x lst, rst)
  | BinTree(m, lst, rst) (* x > m *) -> BinTree(m, lst, remove x rst)

[ EDITAR ¡ Lo siguiente no va a funcionar realmente!] Esto está casi completo, pero necesita agregar la función de merge . La lógica para la función de combinación es la siguiente:

• Si ambos árboles están vacíos, devuelve el árbol vacío
• Si la izquierda es Bin(n, llst, lrst) y la derecha es la rst , devuelve un árbol que contiene n con llst a la izquierda y (recursivamente) fusionados lrst y rst a la derecha (porque los elementos en ambos son mayores que n )
• De manera similar, si el derecho es Bin y el izquierdo es cualquier otra cosa.

Esto no producirá un árbol binario equilibrado , pero es un buen comienzo.

EDITAR : Creo que quizás la opción más fácil es escribir dos funciones: una para eliminar la más grande y otra para eliminar el elemento más pequeño del árbol (luego, al fusionarlas, puedes llamar a una de estas dos). Esto podría ser más fácil que escribir una función de eliminación completamente general.

A continuación, se elimina el elemento más grande y lo devuelve, junto con un nuevo árbol (sin el elemento más grande):

let rec remLargest = function
  | NL -> failwith "Tree was empty!"
  | BinTree(m, l, NL) -> m, l
  | BinTree(m, l, r) -> 
      let res, newR = remLargest r
      res, BinTree(m, l, newR)

Answer 2

He seguido los pasos que Tomás describe en su publicación y se me ocurrió esta solución:

// BST - binary search tree
type BST<''a when ''a: comparison> = | Leaf
                                   | Node of BST<''a> * ''a * BST<''a>

let rec rmMaxBST = function
    | Leaf              -> failwith "Tree was empty"
    | Node(tL, x, Leaf) -> x, tL
    | Node(tL, x, tR  ) -> let m, newTR = rmMaxBST tR
                           m, Node(tL, x, newTR)

let rec rmMinBST = function
    | Leaf              -> failwith "Tree was empty"
    | Node(Leaf, x, tR) -> x, tR
    | Node(tL,   x, tR) -> let m, newTL = rmMinBST tL
                           m, Node(newTL, x, tR)

let mergeBST t1 t2 =
    match t1, t2 with
    | (Leaf, Leaf)      -> Leaf
    | (t1,   Leaf)      -> let x, t = rmMaxBST t1
                           Node(t, x, Leaf)               
    | (t1,   t2  )      -> let x, t = rmMinBST t2
                           Node(t1, x, t)              

let rec delBST x = function
    | Leaf                       -> Leaf
    | Node(tL, a, tR) when x < a -> Node(delBST x tL, a,          tR)
    | Node(tL, a, tR) when a < x -> Node(         tL, a, delBST x tR)
    | Node(tL, _, tR)            -> mergeBST tL tR

Intenté esto en REPL:

> delBST 3 Leaf;;

val it : BST<int> = Leaf

> delBST 3 (Node(Leaf, 4, Leaf));;

val it : BST<int> = Node (Leaf,4,Leaf)

> delBST 3 (Node(Leaf, 3, Leaf));;

val it : BST<int> = Leaf

> delBST 3 (Node(Node(Leaf, 1, Leaf), 3, Node(Leaf, 5,Leaf)));;

val it : BST<int> = Node (Node (Leaf,1,Leaf),5,Leaf)

> delBST 1 (Node(Node(Leaf, 1, Leaf), 3, Node(Leaf, 5,Leaf)));;

val it : BST<int> = Node (Leaf,3,Node (Leaf,5,Leaf))

> delBST 5 (Node(Node(Leaf, 1, Leaf), 3, Node(Leaf, 5,Leaf)));;

val it : BST<int> = Node (Node (Leaf,1,Leaf),3,Leaf)