tree - listas - Compruebe si el árbol n-aria está equilibrado en Common Lisp

manual lisp

Question

Intento escribir el código para verificar si un árbol n-aria está balanceado o no en clisp. El árbol se da así:

(A (B (E (I))(F))(C (G))(D)) 

que se vería así:

      A
   /  |  /
  B   C   D
 //   |   
E  F  G   
|
I

Que sería desequilibrado.

Estaba pensando en resolverlo usando algo como:

• el nivel máximo de todas las hojas de una carta: el nivel mínimo de todas las hojas no debe ser mayor que 1.

• Pensé en aplicar esta regla para A, B, C primero. Si la diferencia no es mayor que 1, entonces compruebe E, F, G hasta que haya verificado todas las letras posibles y el árbol esté equilibrado o tenga una diferencia mayor que 1, lo que significa que está desequilibrado.

Este es el código para el nivel min / max:

(defun nrlvlmax (tail) 
(cond 
    ( (null tail) 0)
    ( (listp (car tail)) (max ( + 1 (nrlvl (car tail))) (nrlvl (cdr tail))))
    ( t (nrlvl (cdr tail)))
)

)

No sé cómo analizar la lista y aplicar mi regla. No debería usar funciones map / lamba, solo como conceptos básicos. Cómo analizar la lista dada?

Answer 1

Aquí hay una posible solución que no usa funciones de orden superior.

La idea es calcular el nivel máximo de un árbol y su nivel mínimo, y verificar su diferencia.

Para calcular el nivel máximo (o mínimo) de un árbol utilizamos dos funciones mutuamente recursivas: la primera calcula el nivel máximo (mínimo) de árbol, la segunda calcula el máximo (mínimo) de todos sus hijos.

Por supuesto, si un árbol tiene hijos, entonces su nivel es 1 más el nivel máximo (mínimo) de sus hijos.

La función para los niños tiene dos parámetros, el primero es el resto de los niños a considerar, el segundo es el valor actual del máximo (mínimo).

(defun maxlevel(tree)
  (cond ((null tree) 0)
        ((null (cdr tree)) 1)
        (t (1+ (max-for-children (cddr tree) (maxlevel (cadr tree)))))))

(defun max-for-children(children current-max)
  (if (null children)
      current-max
      (max-for-children (cdr children) (max current-max (maxlevel (car children))))))

(defun minlevel(tree)
  (cond ((null tree) 0)
        ((null (cdr tree)) 1)
        (t (1+ (min-for-children (cddr tree) (minlevel (cadr tree)))))))

(defun min-for-children(children current-min)
  (if (null children)
      current-min
      (min-for-children (cdr children) (min current-min (minlevel (car children))))))

(defun balanced(tree)
  (= (maxlevel tree) (minlevel tree)))

Esto es para árboles perfectamente equilibrados. Si permite árboles con una diferencia de como máximo uno entre los niveles del árbol, entonces sustituya la última función por:

(defun balanced(tree)
  (<= (abs (- (maxlevel tree) (minlevel tree))) 1))

Answer 2

Mi solución anterior no es eficiente por dos razones:

1. el árbol es visitado dos veces,
2. el algoritmo no se detiene tan pronto como encuentra una ruta desde la raíz a una hoja que viola la condición de equilibrio.

Entonces, aquí hay una solución más eficiente, que visita el árbol solo una vez y se detiene tan pronto como encuentra un camino demasiado corto o demasiado largo.

Las ideas básicas son:

1. todo el trabajo se realiza mediante una función interna min-max que devuelve un par de valores: profundidad mínima y profundidad máxima de subárboles enraizados en el argumento actual de la función, esto permite visitar el árbol solo una vez;

2. en cada llamada recursiva, la función recibe el nivel actual, el nivel mínimo actual y el nivel máximo actual, para que pueda verificar lo antes posible si el árbol está desequilibrado y la visita debe detenerse inmediatamente. Para el primer hijo de un nodo, el máximo y el mínimo actuales se establecen en nil (y por esta razón, definí dos funciones auxiliares que calculan el mínimo o el máximo, incluso si el segundo argumento es nil ).

Tenga en cuenta que la función principal devuelve nil , si el árbol está desequilibrado, o la profundidad mínima del árbol.

(defun mymin(x y)
  (if y (min x y) x))

(defun mymax(x y)
  (if y (max x y) x))

(defun balanced(tree)
  (labels ((min-max(tree current-level current-min current-max)
             (when (and current-min (> (1- current-level) current-min))
                (return-from balanced nil))                  ; this path is too long
             (if (null (cdr tree))                           ; if it is a leaf node
                 (if (and current-max (< (1+ current-level) current-max))
                     (return-from balanced nil)              ; this path is too short
                     (values current-level current-level))   ; return normally
                 (loop for child in (cdr tree)               ; find min-max for each child
                    do (multiple-value-bind (min1 max1)
                           (min-max child (1+ current-level) current-min current-max)
                         (setf current-min (mymin min1 current-min)
                               current-max (mymax max1 current-max)))
                    finally (return (values current-min current-max))))))
    (values (min-max tree 0 nil nil))))

Finalmente, tenga en cuenta que la función utiliza un bucle. Se podría producir una versión recursiva, pero esto solo complicaría la solución y la volvería antinatural.