测试两个二叉树是否相等的最有效方法

Question

您将如何在Java中实现二叉树节点类和二叉树类以支持最有效(从运行时角度来看)相等检查方法(也必须实现):

    boolean equal(Node<T> root1, Node<T> root2) {}

要么

    boolean equal(Tree t1, Tree t2) {}

首先,我创建了Node类,如下所示:

    public class Node<T> {
        private Node<T> left;
        private Node<T> right;
        private T data;

        // standard getters and setters
    }

然后是equals方法,它将2个根节点作为参数并运行标准的递归比较:

    public boolean equals(Node<T> root1, Node<T> root2) {
        boolean rootEqual = false;
        boolean lEqual = false;
        boolean rEqual = false;    

        if (root1 != null && root2 != null) {
            rootEqual = root1.getData().equals(root2.getData());

            if (root1.getLeft()!=null && root2.getLeft() != null) {
                // compare the left
                lEqual = equals(root1.getLeft(), root2.getLeft());
            }
            else if (root1.getLeft() == null && root2.getLeft() == null) {
                lEqual = true;
            }
            if (root1.getRight() != null && root2.getRight() != null) {
                // compare the right
                rEqual = equals(root1.getRight(), root2.getRight());
            }
            else if (root1.getRight() == null && root2.getRight() == null) {
                rEqual = true;
            }

            return (rootEqual && lEqual && rEqual);
        }
        return false;
    } 

我的第二次尝试是使用数组和索引实现遍历树.然后可以使用两个数组上的按位运算(AND)进行比较 - 从2个数组中读取块并使用逻辑AND逐个屏蔽.我没有让我的代码工作,所以我不在这里发布(我很感激你实现的第二个想法以及你的改进).

有没有想过如何最有效地对二叉树进行相等测试？

编辑

这个问题假设结构平等.(不是语义上的平等)

但是,测试语义相等性的代码例如"如果它们的内容相同,我们应该考虑两棵树是否相同,即使它们的结构不相同？" 将按顺序迭代树,它应该是直截了当的.

Answer 1

好吧,有一件事你总是检查分支,即使你发现根是不平等的.如果您在false发现不平等时立即返回,您的代码将更简单(IMO)并且效率更高.

简化操作的另一个选择是允许您的equals方法接受null值并将两个空值比较为相等.这样您就可以避免在不同分支中进行所有这些无效检查.这不会使它更有效率,但它会更简单:

public boolean equals(Node<T> root1, Node<T> root2) {
    // Shortcut for reference equality; also handles equals(null, null)
    if (root1 == root2) {
        return true;
    }
    if (root1 == null || root2 == null) {
        return false;
    }
    return root1.getData().equals(root2.getData()) &&
           equals(root1.getLeft(), root2.getLeft()) &&
           equals(root1.getRight(), root2.getRight());
} 

请注意,如果root1.getData()返回,目前这将失败null.(对于添加节点的方式,这可能是也可能不存在.)

编辑:正如评论中所讨论的,您可以使用哈希码来快速"提前" - 但这会增加复杂性.

无论你需要让你的树木不变(这是一个整体的其他讨论)或者你需要在每个节点知道其母公司,这样当节点改变时(通过添加叶或改变值的EG),它需要更新其哈希码并要求其父级也进行更新.

Answer 2

出于好奇,如果两棵树的内容相同,你认为两棵树是否相同,即使它们的结构不相同？例如,这些是平等的吗？

  B         C        C      A
 / \       / \      / \      \
A   D     B   D    A   D      B
   /     /          \          \
  C     A            B          C
                                 \
                                  D

这些树以相同的顺序具有相同的内容,但由于结构不同,通过您的测试将不相等.

如果你想测试这个相等性,我个人只是使​​用按顺序遍历为树构建一个迭代器,并迭代遍历树,逐个元素地比较它们.

Answer 3

首先,我做了一些一般的假设.这些假设对大多数基于树的集合类都有效,但总是值得检查:

1. 您认为两个树是相等的,当且仅当它们在树结构和每个节点的数据值方面都相等时(由data.equals(...)定义)
2. 树节点允许使用null数据值(这可能是因为您明确允许null或因为您的数据结构仅在叶节点处存储非空值)
3. 您可以利用的数据值分布没有任何特殊的事实(例如,如果您知道唯一可能的数据值为null或字符串"foo",那么您不需要比较两个非null String值)
4. 树木通常具有适中的尺寸并且相当平衡.特别是,这可以确保树永远不会太深,以至于您冒着深度递归导致的StackOverflowExceptions风险.

假设这些假设是正确的,那么我建议的方法是:

• 首先执行根引用相等性检查.这样可以快速消除两个空值或传入相同树的情况,以便与自身进行比较.两者都是非常常见的情况,参考等式检查非常便宜.
• 接下来检查空值.非null显然不等于null,这使您可以提前纾困,并为以后的代码建立非空保证!一个非常聪明的编译器理论上也可以使用这个保证来优化掉空指针检查(不确定JVM当前是否这样做)
• 接下来检查数据引用相等和空值.这样可以避免在树枝下一直向下移动,即使在数据不一致的情况下,如果先将树枝放下,也会这样做.
• 接下来检查data.equals().您想再次在树枝之前检查数据相等性.检查空值后执行此操作,因为data.equals()可能更昂贵,并且您希望保证不会出现NullPointerException
• 作为最后一步递归检查分支的相等性.如果你先做左或右是没关系的,除非一方更不可能不平等,在这种情况下你应该先检查那一方.例如,如果大多数更改被附加到树的右侧分支,则可能是这种情况....
• 使比较成为静态方法.这是因为您希望以一种将null作为两个参数之一接受的方式递归地使用它(因此它不适用于实例方法,因为this它不能为null).此外,JVM非常擅长优化静态方法.

因此,我的实施将是这样的:

public static boolean treeEquals(Node a, Node b) {
    // check for reference equality and nulls
    if (a == b) return true; // note this picks up case of two nulls
    if (a == null) return false;
    if (b == null) return false;

    // check for data inequality
    if (a.data != b.data) {
        if ((a.data == null) || (b.data == null)) return false;
        if (!(a.data.equals(b.data))) return false;
    }

    // recursively check branches
    if (!treeEquals(a.left, b.left)) return false;
    if (!treeEquals(a.right, b.right)) return false;

    // we've eliminated all possibilities for non-equality, so trees must be equal
    return true;
}