Prolog是树平衡的

Question

如果T是一棵平衡的树，我需要实现一个谓词isBal的/1，以便isBal的（T）为真。

在这种情况下，二叉树由结构节点（左、右）定义，其中左和右可以是另一个节点或任何Prolog数据项。

我目前掌握的情况是:

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（_）表示空树，
• 节点（L， R）表示非空树。

我怀疑您的高度/2有一个错误，因为您似乎将空树的高度定义为1（而不是0）。

我可能会将二叉树表示如下：

> < li>nil —空树 < li>

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

平衡的确定

所以，从这个表示和定义开始工作

二叉树是平衡的，如果：

• 它的左子树是平衡的
• 它的右子树是平衡的
• 子树各自的高度相差不超过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!)