Недавно купив «Cracking the Coding Interview» от Гейл Лаакманн МакДауэлл, я очень застрял на вопросе в главе 4, Деревья и графики. На самом деле, точнее будет сказать, что я очень застрял на решение. В разгар разочарования я никогда не уверен, переходить ли к другому вопросу или рисковать бесконечной регрессией, исследуя, что именно мешает мне интуитивно понять решение.
Вопрос 4.9, Последовательности BST, просит читателя распечатать все возможные списки, которые можно использовать для построения данного двоичного дерева поиска (BST).
Ответ здесь - список списков. Каждый внутренний список является допустимым порядком вставки для BST.
[ [10, 5, 20], [10, 20, 5] ]
BST в этом примере можно полностью восстановить, взяв любой из внутренних списков и пройдя по нему слева направо. Или, другими словами, каждый внутренний список является допустимым порядком вставки. Решение в Cracking the Coding Interview дает несколько идей.
Вывод 1: после вставки корневого узла положение его непосредственных дочерних узлов определяется их значением, а не порядком, в котором они вставлены. Неважно, вставлено ли 5 перед 20 или наоборот.
«У одного BST может быть несколько заказов на размещение».
Вывод 2: комбинируя порядки вставки поддеревьев, мы можем перейти к решению для узлов, расположенных дальше вверх по дереву. В следующем примере 5 является корнем определенного поддерева (назовите это «поддерево-5»). 20 является корнем другого поддерева (назовите это «поддерево-20»). Комбинированные порядки вставки для поддерева-5 и поддерева-20 помогают найти порядки вставки для поддерева-10.
В поддереве 5 есть два порядка размещения: [5, 2, 4] и [5, 4, 2]. Поддерево 20 имеет только один порядок вставки, [20, 30] , потому что есть только один способ создать поддерево с одним дочерним элементом. Обратите внимание, что корень поддерева включен в порядок вставки, поскольку он должен быть вставлен вместе со своими дочерними элементами, чтобы сформировать поддерево. Корневые значения выделены жирным шрифтом для визуальной подсказки.
# Insertion orders subtree5 = [[5, 2, 4], [5, 4, 2]] subtree20 = [[20, 30]]
Объединение порядков вставки поддерева 5 и поддерева 20 поможет найти порядки вставки поддерева 10. Но как можно объединить порядки вставки для поддерева 5 и поддерева 20? Прежде чем ответить на этот вопрос, давайте сделаем шаг назад и рассмотрим, что значит «комбинировать» в данном контексте. Сочетание означает, что мы хотим создать единый порядок размещения из порядков размещения двух поддеревьев. Например:
combine_insertion_orders([5, 2, 4], [20, 30])
Но мы не можем просто комбинировать списки как угодно. Здесь есть правила. Это должны быть действительные заказы на размещение для BST. Значения корневых узлов должны появляться перед дочерними значениями, иначе BST будет (пере) построен неправильно.
5должен стоять перед2и4во всех результирующих комбинациях20должен стоять перед30во всех результирующих комбинациях.
Давайте посмотрим, к чему мы стремимся, сразу перейдя к ответу. Полный список заказов на размещение:
[ [5, 2, 4, 20, 30], [5, 2, 20, 4, 30], [5, 2, 20, 30, 4], [5, 20, 2, 4, 30], [5, 20, 2, 30, 4], [5, 20, 30, 2, 4], [20, 5, 2, 4, 30], [20, 5, 2, 30, 4], [20, 5, 30, 2, 4], [20, 30, 5, 2, 4] ]
Каждый список представляет собой порядок вставки, который можно использовать для создания BST. Обратите внимание, что каждый список состоит из пяти элементов, потому что мы объединили списки длиной 3 и длиной 2. Прежде чем посмотреть, как мы формируем эти результаты, давайте посмотрим, почему. Возможно, вы заметили, что если мы префикс 10 ко всем порядкам вставки, мы получим все заказы на вставку для поддерева 10.
[ [10, 5, 2, 4, 20, 30], [10, 5, 2, 20, 4, 30], [10, 5, 2, 20, 30, 4], [10, 5, 20, 2, 4, 30], [10, 5, 20, 2, 30, 4], [10, 5, 20, 30, 2, 4], [10, 20, 5, 2, 4, 30], [10, 20, 5, 2, 30, 4], [10, 20, 5, 30, 2, 4], [10, 20, 30, 5, 2, 4] ]
Сначала я подумал, что это слишком просто. Конечно, мы должны создать какую-то перестановку, при которой 10 не всегда является первым членом? Но помните наши правила, корневой узел любого поддерева должен быть вставлен перед его дочерними элементами.
Это то, что я имел в виду ранее, когда сказал, что объединение порядков вставки для поддерева-5 и поддерева-20 поможет нам с поддеревом-10. Мы не просто получили заказы на размещение поддерева-10 на серебряном блюде, мы должны были работать над этим (ну, префикс 10 для каждой комбинации). В Cracking the Coding Interview объединение списков с сохранением их относительного порядка называется «переплетением». Мне нравится этот термин, и я тоже буду его использовать.
Итак, как мы можем сплести два списка вместе и сгенерировать действительные заказы на размещение для BST? Решение в Cracking the Coding Interview - ввести третий список под названием prefix. Думайте об этом как о списке помощников. Для простоты вернемся к нашему первому примеру с меньшим количеством узлов:
В этом примере у нас есть два поддерева, каждое с нулевыми узлами (т. Е. Два пустых поддерева). В поддереве 5 есть один допустимый порядок вставки, [5]. В поддереве 20 также есть один действующий порядок вставки, [20]. Помните, что из нашего предварительного просмотра результатов 10 будет добавлено в начало всех заказов на размещение, поэтому нам нужно объединить [5] и [20]:
subtree5 = [5] subtree20 = [20] prefix = []
Начнем со следующего кода, который объединяет все три списка в один:
prefix + subtree5 + subtree20
Общий подход будет заключаться в перемещении элементов в эти списки и из них и объединении всех списков только в том случае, если subtree5 или subtree20 пусто. Если мы переместимся 5 из subtree5 в prefix, мы получим нашу первую комбинацию:
# prefix + subtree5 + subtree20 [5] + [] + [20]
Поскольку subtree5 пусто, мы объединяем все списки, чтобы получить [5, 20] (потому что этот средний список пуст). Теперь вернитесь 5 в subtree5 и переместите 20 из subtree20 в prefix:
# prefix + subtree5 + subtree20 [20] + [5] + []
Теперь там subtree20 пусто, поэтому присоединяйтесь ко всем спискам, чтобы получить [20, 5]. Этот быстрый пример дал нам два порядка размещения, просто перемещая элементы в префикс и из него:
[5, 20] [20, 5]
Использование третьего prefix списка кажется чрезмерным, когда он используется для создания двух списков, каждый из которых содержит только один элемент. Давайте поднимемся на ступеньку выше и составим два списка по два элемента в каждом:
subtree5 = [2, 5] subtree20 = [20, 30] prefix = []
Прежде чем создавать эти списки, нам понадобится другое правило: мы всегда должны брать элементы слева от списка и возвращать элементы справа от списка. Может помочь представление о prefix как о стеке. Как и раньше, мы будем объединять списки, только если subtree5 или subtree20 пусто.
Поскольку 5 - крайний левый элемент в subtree5, начните с перемещения 5 в prefix:
# prefix + subtree5 + subtree20 [5] + [2] + [20, 30]
Что ж, у нас еще что-то есть в subtree5, поэтому мы пока не можем объединить. Давайте также переместим оставшийся элемент из subtree5 в prefix:
# prefix + subtree5 + subtree20 [5, 2] + [] + [20, 30]
Теперь в subtree5 ничего не осталось, мы можем объединить и получить наш первый заказ на размещение [5, 2, 20, 30]. Давай продолжим. Верните 2 в subtree5 и переместите 30 из subtree20 в prefix:
# prefix + subtree5 + subtree20 [5] + [2] + [20, 30] [5, 20] + [2] + [30]
Фу. Не знаю, как вы, но это сбивает с толку и почти невозможно уследить. Добавление двух дополнительных значений сделало тот же процесс намного труднее "увидеть". Здесь полезно взглянуть на происходящее с более высокого уровня. У нас есть три списка: prefix, subtree5 и subtree20. Когда либо subtree5, либо subtree20 пусто, мы присоединяемся ко всем трем и получаем вознаграждение в виде нового заказа на размещение.
Таблица ниже начинается с пустых списков prefix и result. subtree5 и subtree20 инициализируются значениями, соответствующими нашему примеру выше ([5, 2] и [20, 30] соответственно). Каждая новая строка представляет значение, перемещающееся в массив prefix или выходящее из него. Каждая новая строка представляет момент, когда списки объединяются, потому что либо subtree5, либо subtree20 пусты.
Если вы проследите за состоянием каждого списка вниз, вы сможете почувствовать, как элементы перемещаются между списками. Я думаю об этом так: subtree5 - это грубый список. Дайте ему шанс, и он переместит все свои предметы в prefix, не спрашивая. subtree20, с другой стороны, является вежливым списком и обычно перемещает только один элемент, прежде чем subtree5 спросит, хочет ли он вернуться. Строго говоря, это не так, но это неплохая аналогия.
Элементы перемещаются из subtree5 и subtree20, сначала крайний левый элемент. Элементы возвращаются из списка prefix, крайний правый первым.
Код Python для достижения этой цели приведен ниже:
def weave(prefix, subtree5, subtree20, results):
if not len(subtree5) or not len(subtree20):
# One of the lists is empty, so join!
results.append(prefix + subtree5 + subtree20)
return results
# Move leftmost item into prefix.
head_subtree5 = subtree5.pop(0)
prefix.append(head_subtree5)
weave(prefix, subtree5, subtree20, results)
# Return rightmost item to subtree5.
prefix.pop()
subtree5.insert(0, head_subtree5)
# Move leftmost item into prefix.
head_subtree20 = subtree20.pop(0)
prefix.append(head_subtree20)
weave(prefix, subtree5, subtree20, results)
# Return rightmost item to subtree20.
prefix.pop()
subtree20.insert(0, head_subtree20)
if __name__ == "__main__":
results = []
weave_([], [5, 2], [20, 30], results)
print(results)
Есть два рекурсивных вызова weave, первый рекурсивный вызов перемещает элементы из subtree5 в prefix перед рекурсией. Второй рекурсивный вызов перемещает элементы из subtree20 в prefix. Это интересный образец, и я считаю, что он дает реальную возможность поучиться в этом вопросе. Первый рекурсивный вызов для subtree5 всегда будет происходить между рекурсивными вызовами для subtree20.
Ниже приведена диаграмма, показывающая рекурсивные вызовы. Обратите внимание, что параметр results был удален для простоты (поэтому мы просто выбрасываем результаты). Результирующий порядок вставки печатается сразу под красным полем (если subtree5 пусто) или желтым полем (если subtree20 пусто). Функция weave была сокращена до w для уменьшения шума.
С этим выбранным решением то, что казалось вопросом о деревьях двоичного поиска, на самом деле больше связано с объединением списков при сохранении их относительного порядка.
first [2], second [20, 30], prefix [5]
first [], second [20, 30], prefix [5, 2]
DONE [5, 2, 20, 30]
first [2], second [30], prefix [5, 20]
first [], second [30], prefix [5, 20, 2]
DONE [5, 20, 2, 30]
first [2], second [], prefix [5, 20, 30]
DONE [5, 20, 30, 2]
first [5, 2], second [30], prefix [20]
first [2], second [30], prefix [20, 5]
first [], second [30], prefix [20, 5, 2]
DONE [20, 5, 2, 30]
first [2], second [], prefix [20, 5, 30]
DONE [20, 5, 30, 2]
first [5, 2], second [], prefix [20, 30]
DONE [20, 30, 5, 2]
Этот вопрос был сложным не из-за двоичного дерева поиска, а из-за двух рекурсивных вызовов и упорядоченности, которую они обеспечивают. Внимательно изучив это решение, я теперь использую упрощенную версию этого шаблона рекурсии:
def f_(x, y):
if len(x) < 1 or len(y) < 1:
return
results.append(x[0])
f_(x[1:], y)
results.append(y[0])
f_(x, y[1:])
if __name__ == "__main__":
f_([1, 2], [3, 4])
Если бы я пропустил этот вопрос и перешел к другому, я бы не рассмотрел этот конкретный шаблон рекурсии.
На этом пока все. Если вы хотите объяснить какие-либо вопросы по программированию, дайте мне знать в комментариях.
