mimokrokodilchik

Рекурсия далека от идеала.

Рекурсия чаще всего используется только во время собеседований (а этот цикл статей именно направлен на подгтовку к собеседования). В промышленной разработке её чаще избегают изза потенциальных следующих потенциальных проблем:

• Криво написанная рекурсия может выполняться бесконечно (в "лучшем" случае это приведет к ошибке переполнения стэка). В худшем программа повиснет (особенно если программа однопоточная).

• Изначально чаще всего под стэк выделяется не более 1мб памяти а это значит что рекурсивная функция сможет вызвать саму себя где то от 10 до 20 тысяч раз. (размер можно легко увеличить с помощью параметра -Xss но стоит помнить что у JDK есть ограничения по верхней границе - обычно до 1 ГБ)

• Рекурсия сложна для понимания, особенно новичкам.

• Высокое потребление памяти - каждый раз спуская на уровень ниже мы позволяем сборщику мусора удалить ссылки используемые на верхних уровнях - и это не ошибка тк все объекты используемы выше текущего уровня будут использованы когда мы вернемся "снизу"

Очеред (или Стэк) - популярный подход в решении задач на деревья.

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

• Добавляем корневой элемент в очередь

• Проходим по всем элементам очереди и ранее добавленные узлы

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

Обходим дерево в ширину.

Распечатаем все значения дерева сверху вниз, распечатывая значения на каждом уровне слева направо, как гирлянду.

Что такое очередь и как ей пользоваться?

Для начала познакомимся с интерфейсом очереди (Queue) в Java. Очередь представляет собой FIFO (first in, first out - первый зашёл, первый вышел) структуру. В нашем случае потребуется два метода:

• add - добавить в очередь

• poll - вытащить первого из очереди (элемент который бы добавлен раньше других)

Как именно мы будем выполнять обход дерева?

Обходить дерево мы будем следующим способом:

• Добавим в очередь корневой элемент

• "Вытащим" добавленный элемент и положим в очередь его наследников

• Повторим 1-2 шаги пока в очереди ничего не останется

Изобразим эти действя по шагам:

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

Теперь напишем код описанной выше логике

И так как запомнить данный подход если он попадется на собеседовании? Я бы рекомендовал держать в памяти две вещи:

• условие while (!queue.isEmpty())

• queue.poll() - вытаскивание элемента

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

Задача - проверить является ли дерево ли бинарным деревом поиска?

Для начала определимся что такое бинарное дерево поиска:

• У дерева не более двух наследников (оно бинарное)

• В левом подграфе значения всех узлов меньше, чем значение самого узла

• В право подграфе значения всех узлов больше, чем значение самого узла

Такое дерево называется Бинарным Деревом Поиска (Binary Search Tree). Но не стоит путать его с балансированым бинарным деревом. Про сбалансированные бинарные деревья мы поговорим в следующих частях.

Посмотрим на примеры бинарных деревьев поиска:

В примерах ниже если вы возьмете любой узел и проверите значения его левого подграфа то все эти значения будут меньше чем сам узел. Аналогично справа все значения будут больше:

Теперь обратим внимание на деревья нарушающие требуемую логику:

В дереве слева есть следующие недостатки:

• Значение 13 хоть и больше 10 но должно быть меньше 12

• Значение 21 хоть больше 12 но должно быть меньше 19

В дереве справа

• 14 больше 11 но должно быть меньше 12

Давайте попробуем написать простейшее решение данной задачи:

Из требований складывается впечатление что мы должны:

• Обойти все узлы и применить к ним единообразную логику (те написать функцию которая вызывает саму себя)

• Проверить что левый наследник меньше текущего значения узла

• Проверить что правый наследник больше текущего значения узла

Напишем решение для данного невалидного дерева:

И так код:

Чтобы код был более читаем я изобразил это графически:

• node - это текущий узел где мы "находимся"

• node.value это текущее значение узла, на картинке ниже значение текущего узла 18

• node.left это ссылка на левого наследника.

К сожалению такое решение не является верным.

Данная рекурсия берет в учет лишь 3 переменных - значение текущего, левого и правого узлов. Поэтому ниже будет считаться правильным хотя узел 13 слева хоть и больше своего предка (10) но никак не учитывает что он должен быть меньше 12.

Решение задачи не так очевидно на первый взгляд.

Первая попытка никак не учитывает значения дальних предков (те узлов выше родительского). Поэтому наша рекурсия должна будет передавать какую то информацию "сверху". Но какую информацию?

Рассмотрим следующий граф:

Проанализируем какие есть ограничения на значения узлов:

• Узел 12 может быть любым числом на него не ограничений, разве что если мы полагаем что каждый узел является целочисленным (integer) типом то он ограничен между Integer.MIN и Integer.MAX

• Узел 10 (слева) должен быть меньше 12 но также он может быть больше чем Intger.MIN

• Узел 11 - имеет все ограничения примение к 10 И он имеет новое ограничение - он должен быть больше 10.

• Узел 7 имеет ограничения которые есть у узла 10 плюс и также он должен быть меньше 10.

• Узел 6 имеет ограничения которые есть у узла 7 плюс он должен быть меньше 7

Визуализируя описанно мы получаем вот такую штуку:

Какие выводы мы можем сделать:

• Рекурсия должна учитывать как минимум 2 значения приходящие "сверху" те левую и правую границы

• Передаваемая влево минимальное значение является минимальным пришедшим сверху

• Передаваемое влево максимальное значение является максимальным пришедшим сверху

• Передаваемое влево максимальное - текущее

• Передаваемое вправо минимальное - текущее

Давайте перепишем наш код согласно этой логике:

Рассмотрим все пункты которые я отметил:

• A - мы проверяем условие что значение каждого узла лежит в рамках передаваемых min/max значений

• B - минимальное значение передаваемое левому наследнику копируется "сверх"

• C - минимальное значиение передаваемое правому - текущее значение

• D - максимальное значение передаваемое левому - текущее

• F - максимлаьное передаваемое правому копируется "сверху"

Выводы

• Задача успешно решается рекурсией

• Задача явно не так очевидна и первое решение скорее всего займет больше 30 минут и поэтому не подходит для собеседований (хотя это моё личное мнение)

Это не единственный подход к решению этой задачи но сейчас мы практикуем именно простые рекурсии. Подобную задачу вы скорее всего встретите при собеседованиях в FAANG или подобные большие компании. Такое решение скорее всего будет зачтено интервьювером.

Всем кому интересно узнать про промышленную разработку приглашаю в мой котоджавовский телеграм канал.