Почему обход порядка и предварительного порядка полезен для создания алгоритма, определяющего, является ли T2 поддеревом T1

Я смотрю книгу интервью и вопрос:

У вас есть два очень больших двоичных дерева: T1 с миллионами узлов и T2 с сотнями узлов. Создайте алгоритм, чтобы решить, является ли T2 поддеревом T1.

Авторы упоминают это как возможное решение:

Обратите внимание, что проблема здесь указывает, что T1 имеет миллионы узлов - это означает, что мы должны быть осторожны с тем, сколько места мы используем. Скажем, например, T1 имеет 10 миллионов узлов - это означает, что одних данных составляет около 40 mb. Мы могли бы создать строку, представляющую обходы по порядку и по предварительному заказу. Если предварительный обход T2 является подстрокой предварительного обхода T1, а неупорядоченный обход T2 является подстрокой обхода T1, тогда T2 является подстрокой T1.

Я не совсем уверен, почему, если это правда:

  • T2-preorder-traversal-string является подстрокой T1-preorder-traversal-string
  • T2-inorder-traversal-string является подстрокой T1-inorder-traversal-string

Это T2 должно быть подстрокой (хотя я предполагаю, что автор имеет в виду поддерево) T1. Могу я получить объяснение этой логике?

EDIT: пользователь BartoszMarcinkowski поднимает хороший вопрос. Предположим, что у обоих деревьев нет повторяющихся узлов.


algorithm binary-tree tree-traversal
person But I'm Not A Wrapper Class    schedule 20.01.2014    source источник
comment
Предполагая, что вы получили этот вопрос из интервью Cracking the Coding, автор действительно упоминает, что деревья могут иметь повторяющиеся узлы, и даже показывает пример этого. Она решила, что также распечатала нулевые значения для выходных узлов.   -  person Cheng    schedule 28.09.2014

Ответы (3)


arrow_upward
4
arrow_downward

Я думаю, это неправда. Учитывать:

T2:

  2
 / \
1   3

inorder 123 preorder 213

и

T1:

      0
     / \
    3   3
   / \ 
  1   1
 / \ 
0   2


inorder 0123103 preorder 0310213

123 - подстрока 0123103, 213 - подстрока 0310213, но T2 не является поддеревом T1.

person Bartosz Marcinkowski    schedule 20.01.2014
comment
Я почти уверен, что одно из ограничений - отсутствие повторяющихся узлов. - person Daniel Imms; 20.01.2014
comment
Тогда это было бы совершенно очевидно :) - person Bartosz Marcinkowski; 20.01.2014
comment
Я бы тоже ожидал этого предположения, но +1 как хороший контрпример. - person Łukasz Kidziński; 20.01.2014

arrow_upward
2
arrow_downward

Вот контрпример этому методу.

Рассмотрим дерево T1:

  B
 / \
A   D
   / \
  C   E
       \
        F

И поддерево T2:

  D
 / \
C   E

Соответствующие обходы:

  • T1 предварительный заказ: BADCEF
  • T2 предварительный заказ: DCE
  • T1 в порядке: ABCDEF
  • T2 в порядке: CDE

В то время как DCE находится в BADCEF, а CDE находится в ABCDEF, T2 на самом деле не является поддеревом T1. Авторское определение поддерева должно быть другим или это просто ошибка.

Связанный вопрос: Определите, является ли двоичное дерево поддеревом другого двоичного дерева, используя строки предварительного и упорядоченного порядка

person Daniel Imms    schedule 20.01.2014
comment
Но почему нас не волнует пост-заказ? Кроме того, ваш BADCEF пример счетчика не имеет смысла ... может я чего-то не вижу - person But I'm Not A Wrapper Class; 21.01.2014
comment
Каково ваше определение поддерева? - person gen; 11.11.2016

arrow_upward
1
arrow_downward

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

Теперь обратите внимание, что preorder-traversal-string и inorder-traversal-string однозначно идентифицируют двоичное дерево.

Обрывок доказательства:

Пусть T будет деревом.

  • Первый объект в preorder-traversal-string(T) - это корень.
  • Найдите его в inorder-traversal-string(T) - все слева от этого элемента является вашим левым поддеревом L, давайте назовем эту подстроку inorder-traversal-string(L). Все, что справа, - это ваше правое поддерево R.

Теперь давайте сосредоточимся на левом поддереве L.

  • Очевидно, что все поддеревья разделены (они не смешиваются) в обеих строках. Они представлены как последовательные объекты. Проблема только в том, что мы априори не знаем, где preorder-traversal-string(L) заканчивается на preorder-traversal-string(T).
  • Обратите внимание, что строки inorder-traversal-string(L) и preorder-traversal-string(L) имеют одинаковую длину. Это дает место, где можно резать.
  • Теперь у вас есть поддерево, описанное как подстроки inorder-traversal-string(L) и preorder-traversal-string(L), поэтому вы можете повторять процедуру до конца.

Следуя этим шагам (неэффективным, но это только для доказательства) для всех поддеревьев, вы построите дерево однозначно.

Таким образом, все поддеревья T1 однозначно описываются соответствующими inorder-traversal-string и preorder-traversal-string.

person Łukasz Kidziński    schedule 20.01.2014