二叉树同叶序问题的高效Prolog实现方案探究

问题定义 #

二叉树的**叶序（fringe）**是其从左到右的叶子节点序列。同叶序（same-fringe）问题[Hewitt & Patterson, 1970]指判断两棵二叉树是否拥有相同的叶序。例如以下示例中，前两棵树的叶序相同，后两棵则不同：

%         .         .         .
%        / \       / \       / \
%       .   3     1   .     1   .
%      / \           / \       / \
%     1   2         2   3    -2   3

example(1, fork(fork(leaf(1), leaf(2)), leaf(3))).
example(2, fork(leaf(1), fork(leaf(2), leaf(3)))).
example(3, fork(leaf(1), fork(leaf(-2), leaf(3)))).

现有方案分析 #

简单方案（sf_1） #

最直接的思路是分别将两棵树的叶子节点收集为列表，再通过列表合一判断是否相同：

/*
 * SIMPLE SOLUTION
 */

sf_1(T1, T2) :-
    walk(T1, [], Xs),
    walk(T2, [], Xs).

walk(leaf(X), A, [X|A]).
walk(fork(L, R), A0, Xs) :-
    walk(R, A0, A1),
    walk(L, A1, Xs).

该方案简洁直观，但存在明显缺陷：

• 若其中一棵树规模极大，生成完整叶子列表会占用大量内存，不切实际；
• 若两棵树的叶序在开头就存在差异，仍需完整生成第一棵树的叶子列表，效率极低。

按需对比方案（sf_2） #

为解决上述问题，可实现按需遍历叶子的方案，一旦发现首个差异立即终止对比，无需生成完整列表：

/*
 * SUPPOSEDLY BETTER SOLUTION
 */

sf_2(T1, T2) :-
    step([T1], [T2]).

step([], []).
step([T1|S1], [T2|S2]) :-
    next(T1, S1, X, R1),
    next(T2, S2, X, R2),
    step(R1, R2).

next(leaf(X), S, X, S).
next(fork(L, R), S0, X, S) :-
    next(L, [R|S0], X, S).

该方案在叶序不同时能快速终止，但实验显示，当叶序完全相同时，其效率略低于简单方案。

性能对比实验 #

在SWI-Prolog 9.0.4中实现自动实验谓词，对比两种方案的性能：

/*
 * EMPIRICAL COMPARISON
 */

comp(Case) :-
    format('fsize sf-1 sf-2\n'),
    forall( between(1, 10, I),
            (   N is 100000 * I,
                tree(1, N, A),
                (   Case = true         % trees with same fringes
                ->  tree(1, N, B)
                ;   M is random(N//10), % trees with different fringes
                    flip(A, M, B) ),
                time(10, sf_1(A, B), T1),
                time(10, sf_2(A, B), T2),
                format('~0e ~2f ~2f\n', [N, T1, T2]) ) ).

time(N, G, T) :-
    garbage_collect,
    S is cputime,
    forall(between(1, N, _), ignore(call(G))),
    T is (cputime - S) / N.

/*
 * RANDOM TREE GENERATION AND MODIFICATION
 */

tree(X1, Xn, leaf(X1)) :-
    X1 = Xn,
    !.
tree(X1, Xn, fork(L, R)) :-
    X1 < Xn,
    random(X1, Xn, Xi),
    Xj is Xi + 1,
    tree(X1, Xi, L),
    tree(Xj, Xn, R).


flip(leaf(X), Y, leaf(Z)) :-
    (  X = Y
    -> Z is -X
    ;  Z is  X ).
flip(fork(L0, R0), X, fork(L, R)) :-
    flip(L0, X, L),
    flip(R0, X, R).

叶序不同时的结果 #

此时按需对比方案（sf_2）明显快于简单方案：

?- comp(false).
fsize sf-1 sf-2
1e+05 0.01 0.00
2e+05 0.03 0.00
3e+05 0.05 0.00
4e+05 0.07 0.01
5e+05 0.09 0.01
6e+05 0.11 0.00
7e+05 0.12 0.01
8e+05 0.14 0.01
9e+05 0.17 0.00
1e+06 0.18 0.00
true.

叶序相同时的结果 #

此时按需对比方案（sf_2）略慢于简单方案：

?- comp(true).
fsize sf-1 sf-2
1e+05 0.02 0.03
2e+05 0.04 0.05
3e+05 0.06 0.08
4e+05 0.08 0.11
5e+05 0.10 0.12
6e+05 0.12 0.14
7e+05 0.12 0.16
8e+05 0.14 0.18
9e+05 0.17 0.19
1e+06 0.18 0.22
true.

混合优化方案 #

要实现叶序不同时快于简单方案，叶序相同时不慢于简单方案的目标，可通过合并按需对比的逻辑与尾递归优化的特性，实现一个混合方案：

/*
 * HYBRID OPTIMIZED SOLUTION
 */

sf_hybrid(T1, T2) :-
    walk_compare(T1, T2, [], []).

% 匹配叶子节点，继续处理栈中的剩余节点
walk_compare(leaf(X), leaf(X), S1, S2) :-
    step_rest(S1, S2).

% 遍历左子树，将右子树压入栈
walk_compare(fork(L1, R1), T2, S1, S2) :-
    walk_compare(L1, T2, [R1|S1], S2).
walk_compare(T1, fork(L2, R2), S1, S2) :-
    walk_compare(T1, L2, S1, [R2|S2]).

% 栈中还有节点，继续遍历
walk_compare(T1, leaf(X), [R1|S1], S2) :-
    walk_compare(R1, leaf(X), S1, S2).
walk_compare(leaf(X), T2, S1, [R2|S2]) :-
    walk_compare(leaf(X), R2, S1, S2).

% 处理栈中剩余的节点对
step_rest([], []).
step_rest([R1|S1], [R2|S2]) :-
    walk_compare(R1, R2, S1, S2).

方案优势 #

1. 按需终止：当两棵树的叶序在开头出现差异时，会立即终止对比，无需遍历完整树结构，效率与sf_2一致；
2. 尾递归优化：该方案的核心谓词walk_compare和step_rest均为尾递归，SWI-Prolog会自动优化栈开销，在叶序完全相同时，其效率接近sf_1；
3. 减少中间调用：将sf_2中step与next的分层调用合并为单一的walk_compare谓词，减少了谓词调用的额外开销，进一步提升性能。

验证逻辑 #

该方案通过维护两个栈保存待遍历的右子树，遍历过程中优先处理左子树，确保叶子节点按从左到右的顺序对比。一旦发现叶子节点不匹配，立即失败终止；若所有叶子节点匹配，最终栈会同时为空，返回成功。

内容的提问来源于stack exchange，提问作者slago