Идентичные BST's

Question

Два дерева называются одинаковыми, если они содержат один и тот же набор элементов, но могут иметь разные структуры. , например. 4,3,5 и 5,4,3

Как проверить, идентичны ли эти два дерева?

Один из подходов, о котором я могу думать, - использовать хэширование. Для каждого элемента в первом дереве соответствующий счет увеличивается. Для каждого элемента во втором дереве счетчик уменьшается. В конце, хэш пуст, мы уверены, что деревья идентичны. Сложность времени: O (N) Сложность объекта: O (N)

Но этот подход не использует, является ли дерево BST или простым BINARY TREE.

Подход 2: Проведите обход обоих деревьев в массиве. Мы имеем два массива со отсортированными данными. Ли линейный поиск, чтобы проверить, идентичны ли массивы, нет. Сложность времени: O (N) Сложная сложность: O (N)

Но, я хотел знать, что существует ли какое-либо лучшее решение?

Answer 1

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

Как оптимизация для последнего, вы не могли бы просто использовать указатель на текущий элемент в каждом дереве, а не делать копии всех данных? Алгоритм обхода дерева по порядку (по крайней мере, с естественным порядком) не требует создания каких-либо копий данных. Таким образом, ваша космическая сложность будет равна O (1).

Answer 2

Проблема с хэшированием - если у вас есть два дерева поиска двоичных данных, {2, 1, 3} и {0, 0, 6}, они могут иметь одинаковый общий хэш-код, и у вас все еще есть разные элементы.

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

Answer 3

Это отвечает на вопрос, как изначально сформулированный, то есть после идентификация деревьев в смысле одной и той же структуры и элементов.

Сравнение последовательности (или любой другой) последовательности не будет работать: разные деревья имеют одинаковый обход. Например, деревья

^[source]

имеют то же самое в порядка обхода a,b,c,d,e. Вы можете использовать two (different) traversals и проверить, одинаковы ли они соответственно.

Классическое решение, однако, является рекурсивный алгоритм:

equal Leaf(x)  Leaf(y)  => x == y 
| equal Node(x,l1,r1) Node(y,l2,r2) => x == y && equal(l1,l2) && equal(r1,r2) 
| equal _    _    => false; 

Он выполняет обход дерева на обоих одновременно деревьев и занимает много времени Q (п), п максимум соответствующего числа узлов.

---

Что касается обновленного вопроса, то проверка обходных порядков для элементарного равенства достаточно. Обратите внимание, что по определению обход BST-порядка в порядке сортированного списка сохраненных элементов, поэтому этот подход является правильным. В рекурсивной форме, это алгоритм:

inorder Leaf(x)  = [x] 
| inorder Node(x,l,r) = (inorder l) ++ [x] ++ (inorder r); 

    equal []  []  = true 
| equal x1::r1 x2::r2 = x1 == x2 && (equal r1 r2) 
| equal _  _  = false; 

    sameElems t1 t2 = let 
         e1 = inorder t1 
         e2 = inorder t2 
        in 
         equal e1 e2 
        end; 

Если список конкатенация может быть сделана во время O (1), это работает во время Q (п) и пространство Q (п); итерационные решения, безусловно, такие же хорошие, и, вероятно, лучшие константы.

Если вы хотите выполнить эту проверку в o (n) времени, вы даже не можете смотреть на каждый элемент. В общем, оба дерева содержат попарно разные элементы, поэтому вы не можете использовать какие-либо диапазоны, поэтому для каждой общей проверки равенства элемента требуется время Ω (n) (предполагайте более быстрый алгоритм и постройте два дерева, для которых он не выполняется).

Пространство может быть выполнено лучше, чем O (n). Если вы реализуете в порядке cleverly ¹, вам потребуется только O (1) дополнительное пространство (указатель на текущие элементы, некоторые управляющие счетчики/флаги).

---

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