пролог дерево сбалансировано

Question

Мне нужно реализовать предикат , так что isBalanced(T) имеет значение true, если T - это сбалансированное дерево.

В этом случае двоичное дерево определяется узлом структуры (слева, справа), где слева и справа может быть либо другой узел, либо любой элемент данных Пролога.

То, что я до сих пор:

height(node(L,R), Size) :- 
    height(L, Left_Size), 
    height(R, Right_Size), 
    Size is Left_Size + Right_Size + 1 . 
height(l(_),1). 

isBalanced(l(_)). 
isBalanced(node(B1,B2)):- 
    height(B1,H1), 
    height(B2,H2), 
    abs(H1-H2) =< 1, 
    isBalanced(B1), 
    isBalanced(B2). 

Ожидаемый результат:

?- isBalanced(1). 
true. 
?- isBalanced(node(1,2)). 
true. 
?- isBalanced(node(1,node(1,node(1,2)))). 
false. 

Это не работает, любой совет будет весьма признателен!

Answer 1

Как вы работаете , представляя Ваше дерево? Она смотрит на меня, что

• l(_) представляет собой пустое дерево, и
• node(L,R) представляет собой непустое дерево.

И я подозреваю, что ваш height/2 имеет ошибку в том, что вы, кажется, определили высоту пустого дерева как 1 (а не 0).

я бы, вероятно, представляет собой бинарное дерево следующим образом:

• nil — пустое дерево

• tree(D,L,R) — непустое дерево, где

  • D: полезная нагрузка данных
  • L: левое поддеворье
  • R: правое поддерево

так, что один может представлять дерево

a 
/\ 
    b c 
//\ 
d e f 

в

tree(a , 
    tree(b , 
    tree(d , nil , nil) , 
    nil 
) , 
    tree(c , 
    tree(e , nil , nil) , 
    tree(f , nil , nil) 
) . 

и листовой узел (дерево, без поддеревьев) выглядит что-то вроде

tree(data , nil , nil) 

Определение баланса

Так, работая с этого представления, и из определения

A binary tree is balanced if:

• Its left sub-tree is balanced
• Its right sub-tree is balanced
• The respective heights of the sub-trees differ by no more than 1

Мы можем легко написать описательный решение проблемы:

is_balanced(nil  ) . % the empty tree is balanced 
is_balanced(tree(_,L,R)) :- % a non-empty tree is balanced IF ... 
    is_balanced(L) ,   % - the left sub-tree is balanced 
    is_balanced(R) ,   % - the right sub-tree is balanced 
    tree_height(L,LH) ,   % - the height of the left sub-tree 
    tree_height(R,RH) ,   % - the height of the right sub-tree 
    abs(LH - RH) < 2   % - differ by no more than 1 
    .       % Right? 

Нам просто нужно вычислить высоту дерева.

Вычисление высоты

можно вычислить высоту такого дерева следующим образом:

tree_height(nil   , 0) . % the depth of an empty tree is zero. 
tree_height(tree(_,L,R) , H) :- % for a non-empty tree... 
    tree_height(L , LH) ,   % - we compute the height of the left subtree 
    tree_height(R , RH) ,   % - we compute the height of the right subtree 
    H is 1 + max(LH , RH)   % - the overall height is 1 more than the higher of the two values thus obtained. 
    .        % Right? 

Эффективность

Можно отметить, что

• , похоже, происходит много обходов деревьев, и
• is_balanced/2 имеет подозрительное сходство до tree_height/2.

Таким образом, можно было бы оптимизировать вещи путем смешивания глубину два и вычислительное на лету:

Отредактировано: Добавлено обертка сказуемое is_balanced/1:

is_balanced(T) :- is_balanced(T, _) . 

is_balanced(nil   , 0) . % the empty tree is balanced and has a height of zero. 
is_balanced(tree(_,L,R) , H) :- % a non-empty tree is balanced IF ... 
    is_balanced(L , LH) ,   % - its left subtree is balanced, and 
    is_balanced(R , RH) ,   % - its right subtree is balanced, and 
    abs(LH - RH) < 2 ,    % - their respective heights differ by no more than 1, and 
    H is 1 + max(LH , RH)   % - the current tree's height is 1 more than the larger of the heights of the two subtrees. 
    .        % Easy! (And elegant!)