Наиболее эффективный способ проверки двух бинарных деревьев для равенства

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

EDIT: Как обсуждалось в комментариях, вы можете использовать хэш-коды, чтобы сделать очень быстрое "раннее", но это добавит сложности.

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

• Сначала проверьте правильность равенства ссылок. это быстро устраняет случай либо двух нулей, либо того же дерева, которое передается для сравнения с самим собой. Оба являются очень распространенными случаями, и контрольная проверка равенства чрезвычайно дешевая.
• Проверить нули. Non-null, очевидно, не равно null, что позволяет вам быстро выручить, плюс он устанавливает ненулевую гарантию на последующий код! Очень умный компилятор мог также теоретически использовать эту гарантию, чтобы позже оптимизировать ненужные проверки указателей (не уверен, что JVM в настоящее время это делает)
• Проверить правильность ссылки на данные и нули. Это позволяет избежать нисходящего пути вниз по ветвям дерева, которые вы делали бы даже в случае неравных данных, если сначала вы спустились по ветвям дерева.
• Проверьте data.equals() next. Снова вы хотите проверить равенство данных перед ветвями дерева. Вы делаете это после проверки нулей, поскольку data.equals() потенциально более дорогой и вы хотите гарантировать, что вы не получите NullPointerException
• Проверяйте равенство ветвей рекурсивно как последний шаг. Неважно, если вы делаете левый или правый первый, если не существует большей вероятности того, что одна сторона будет неравной, и в этом случае вы должны сначала проверить эту сторону. Это может иметь место, если, например, большинство изменений было добавлено к правой ветке дерева....
• Сделать сравнение статическим методом. Это связано с тем, что вы хотите использовать его рекурсивно таким образом, чтобы принимать значения null как один из двух параметров (следовательно, он не подходит для метода экземпляра, поскольку this не может быть нулевым). Кроме того, 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;
}

Ответ 4

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

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

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

EDIT: на самом деле ваша реализация может быть улучшена, если вы будете следовать рекомендациям в ответе Джона Скита (по крайней мере, верните false, как только вы узнаете, что деревья не равны)

Ответ 5

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

if (! a == b) возвращает false;

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

(Невозможно войти отсюда по какой-то причине.)