Проверьте, сбалансировано ли n-арное дерево в Common Lisp

Question

Я пытаюсь написать код, чтобы проверить, сбалансировано ли n-арное дерево или нет. Дерево задается следующим образом:

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

, который будет выглядеть так:

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

Какой бы несбалансированным.

Я думал о ее решении использовать что-то вроде:

• максимальный уровень всех листьев письма - уровень мин всех листьев не должно быть больше, чем 1.

• я думал о применении этого правила для A, B, C в первую очередь. Если разница не больше 1, тогда проверьте E, F, G, пока я не проверил все возможные буквы, а дерево не сбалансировано, или я получил разницу больше 1, что означает, что она неуравновешена.

Это код мин/макс уровня:

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

)

Я не знаю, как разобрать список и применить мое правило. Я не должен использовать функции map/lamba, только как основы. Как разобрать данный список?

Answer 1

Это возможное решение, которое не использует функции более высокого порядка.

Идея состоит в том, чтобы вычислить максимальный уровень дерева и его минимальный уровень и проверить их разницу.

Для вычисления максимального (или минимального) уровня дерева мы используем две взаимно-рекурсивные функции: первый вычисляет уровень максимального (minimun) дерева, второй вычисляет максимум (minimun) всех его дочерних элементов.

Конечно, если у дерева есть дети, то его уровень равен 1 плюс максимальный (минимальный) уровень его детей.

Функция для детей имеет два параметра, первый из которых - остальные дети для рассмотрения, второй - текущее значение максимума (минимум).

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

Это идеальное сбалансированное дерево. Если вы позволяете дерева с разницей не более одного между уровнями дерева, а затем заменить последнюю функцию с:

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

Answer 2

Моего previous solution не является эффективным по двум причинам:

1. дерева посещаются дважды,
2. алгоритм не останавливается, как только он находит путь от корня до листа, который нарушает условие балансировки.

Итак, вот более эффективное решение, которое посещает дерево только один раз и останавливается, как только он находит путь слишком короткий или слишком длинный.

Основные идеи:

1. вся работа выполняется с помощью внутренней функции min-max, которая возвращает несколько значений: Minimun глубину и максимальную глубину поддерева укорененных в текущем аргументе функции, это позволяет посещать дерево только один раз;

2. при каждом рекурсивном вызове функция получает текущий уровень, текущий минимальный уровень и текущий максимальный уровень, чтобы он мог как можно скорее проверить, если дерево неуравновешенно, и посещение должно быть немедленно остановлено. Для первого дочернего узла узла максимальный и минимальный ток установлены на nil (и по этой причине я определил две вспомогательные функции, которые вычисляют минимум или максимум, даже если второй аргумент равен nil).

Обратите внимание, что главная функция возвращает либо nil, если дерево несбалансированное, или Minimun глубины дерева.

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

Наконец, обратите внимание, что функция использует петлю. Рекурсивная версия может быть выпущена, но это только усложнит решение и сделает его неестественным.