Самый эффективный способ проверить два бинарных дерева на равенство

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. Мне не удалось заставить мой код работать, поэтому я не публикую его здесь (я был бы признателен за реализацию второй идеи, а также за ваши улучшения).

Есть мысли, как наиболее эффективно провести тест на равенство для бинарных деревьев?

EDIT

Вопрос предполагает структурное равенство. (Не семантическое равенство)

Однако код, который проверяет семантическое равенство, например «Должны ли мы считать два дерева равными, если их содержимое идентично, даже если их структура не одинакова?» Будет просто перебирать дерево по порядку, и это должно быть просто.

Answer 1

Ну, во-первых, вы всегда проверяете ветви, даже если замечаете, что корни неравны.Ваш код был бы более простым (IMO) и более эффективным, если бы вы только что вернули false, как только заметили неравенство.

Другой способ упростить задачу - разрешить вашему 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.(Это может или не может быть возможно с тем, как вы добавляете узлы.)

РЕДАКТИРОВАТЬ: Как обсуждалось в комментариях, вы могли бы использовать хэш-коды, чтобы сделать очень быстро "рано" - но это добавитсложность.

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

Answer 2

Из любопытства, считаете ли вы, что два дерева равны, если их содержимое одинаково, даже если их структура не одинакова?Например, равны ли они?

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

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

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

Answer 3

Прежде всего я делаю несколько общих предположений.Это предположения, которые действительны для большинства классов коллекций на основе дерева, но всегда стоит проверить:

1. Вы считаете, что два дерева равны тогда и только тогда, когда они равны оба с точки зрения дерева структура и в терминах значения данных в каждом узле (как определено data.equals (...))
2. допустимы нулевые значения данных в узлах дерева (это может бытьлибо из-за того, что вы допускаете пустое значение явно, либо из-за того, что ваша структура данных хранит ненулевые значения только в конечных узлах)
3. Нет каких-либо особых необычных фактов, которые вы знаете о распределении значений данных, которыми вы можете воспользоваться (например, если вы знали, что единственными возможными значениями данных являются null или String "foo", вам не нужно сравнивать два ненулевых значения String)
4. Деревья обычно имеют средний размери достаточно хорошо сбалансирован.В частности, это гарантирует, что деревья никогда не будут настолько глубокими, что вы рискуете получить StackOverflowExceptions, вызванный глубокой рекурсией.

Если предположить, что эти предположения верны, то я бы предложил следующий подход:

• Сначала выполните проверку на равенство корневых ссылок.это быстро исключает случай передачи двух нулей или одного и того же дерева для сравнения с самим собой.Оба являются очень распространенными случаями, и проверка на равенство ссылок чрезвычайно дешева.
• Далее проверьте нули.Значение, отличное от нуля, очевидно, не равно нулю, что позволяет вам выручить досрочно плюс , это устанавливает ненулевую гарантию для последующего кода!Очень умный компилятор также может теоретически использовать эту гарантию для оптимизации проверок нулевого указателя позже (не уверен, что 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;
}

Answer 4

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

Это будет работать только в том случае, если дерево статично (т.е. не изменяется со временем).Кроме того, он будет считать деревья равными, только если индексы вершин одинаковы в двух деревьях.

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

РЕДАКТИРОВАТЬ: на самом деле ваша реализация может быть улучшена, если вы будете следовать советам в ответе Джона Скита (по крайней мере, вернуть false, как только вы узнаете, что деревья не равны)

Answer 5

Приведенный выше код вернул бы true для двух неравных деревьев с одинаковыми корневыми значениями.Я не думаю, что это то, что вы хотите.Не должно ли это быть:

если (! A == b) вернуть false;

Таким образом, метод будет выполнять остальные проверки.

(Can 'сюда по какой-то причине зайти.)