Продолжаем цикл статей про деревья. Основной целью этого цикла является практика и подготовка к собеседованиям а не промышленные решения (о них я расскажу в следующих частях). В этой части мы еще раз воспользуемся рекурсией для решения одной популярной задачи.
Задача - проверить является ли дерево ли бинарным деревом поиска?
Для начала определимся что такое бинарное дерево поиска:
- У дерева не более двух наследников (оно бинарное)
- В левом подграфе значения всех узлов меньше, чем значение самого узла
- В право подграфе значения всех узлов больше, чем значение самого узла
Такое дерево называется Бинарным Деревом Поиска (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
Визуализируя описанно мы получаем вот такую штуку:
под MIN, MAX подразумевается Integer.MIN, Integer.MAX - сделано чтобы уместить широкую картинку
Какие выводы мы можем сделать:
- Рекурсия должна учитывать как минимум 2 значения приходящие "сверху" те левую и правую границы
- Передаваемая влево минимальное значение является минимальным пришедшим сверху
- Передаваемое влево максимальное значение является максимальным пришедшим сверху
- Передаваемое влево максимальное - текущее
- Передаваемое вправо минимальное - текущее
Давайте перепишем наш код согласно этой логике:
Код мог бы быть меньше но я написал его именно так с целью упрощения чтения и понимания.
Рассмотрим все пункты которые я отметил:
- A - мы проверяем условие что значение каждого узла лежит в рамках передаваемых min/max значений
- B - минимальное значение передаваемое левому наследнику копируется "сверх"
- C - минимальное значиение передаваемое правому - текущее значение
- D - максимальное значение передаваемое левому - текущее
- F - максимлаьное передаваемое правому копируется "сверху"
Выводы
- Задача успешно решается рекурсией
- Задача явно не так очевидна и первое решение скорее всего займет больше 30 минут и поэтому не подходит для собеседований (хотя это моё личное мнение)
Это не единственный подход к решению этой задачи но сейчас мы практикуем именно простые рекурсии. Подобную задачу вы скорее всего встретите при собеседованиях в FAANG или подобные большие компании. Такое решение скорее всего будет зачтено интервьювером. Также я советую посмотреть видео формат этой статьи
Всем кому интересно узнать про промышленную разработку приглашаю в мой котоджавовский телеграм канал.