Java + Программист

Инвертируем дерево

Целью является инвертировать дерево. Те для каждого узла нужно поменять местами его левый и правый наследники. Логику надо также применять к наследникам наследников.

Давайте проговорим какие этапы нужно продумать:

• Проитерироватсья по всем узлам рекурсией те нам понадобится функция которая будет вызывать саму себя.

• Нижние пустые null узлы нужно будет проигнорировать

• Для всех остальных узлов нужно выполнить смену ссылок для правого и левого наследников

Решение:

Думаю вам тоже задача показалось довольно простой но при этом она является одной из самых частых во время собеседований. В следующей статье мы рассмотрим более сложные случаи. Всем кому интересно - добро пожаловать в мою группу.

Довольно очевидно что самый длинный узел в данном дереве - M и он является пятым по счету если головной является первым.

Как решать данную задачу используя рекурсию.

Если сильно упрощать то нам нужно сделать 2 действия:

• Обойти все узлы

• Каким то образом "сохранять" состояния каждый раз когда мы обходим узлы

Но как же сохранять состояния о той глубине на которой мы побывали? Тут есть как минимум два варианта:

• Использовать возвращемое значение самой рекурсивной функции и "возвращать" её на уровень выше.

• Иметь какой то объект в котором мы будем сохранять состояния находясь внутри рекурсии

Воспользуемся первым подходом. Сосредоточимся на следующих аспектах:

• Рекурсивная функция должна передавать значение сама себе "наверх"

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

Логика передаваемого "наверх" значения.

• Самые нижние уровни (те что указывают на null) должны возвращать 0 тк они не включены в расчет глубины данного подграфа

• Нижний уровень который с листьями имеет лишь null предков должен вернуть 1 тк он является первым уровнем

• Узел выше чем 1й (те не лист) должен выбирать максимальный уровень из двух его наследников и добавлять 1 тк находится на уровень выше из наибольшего из них.

После данных рассуждений у нас вырисовывается вот такая картина:

К чему привели наши рассуждения?

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

И так первая версия кода:

Самый важная часть кода - итеративный вызов левого и правого поддерева и последующий расчет максимального значения среди них. И конечно же добавление 1 наибольшему из них чтобы учесть и текущую высоту.

Этот код можно было бы улучшить удалив случай когда мы находимся в самом низу - дело в том что если условие истино то возвращаемое значение maxDepth + 1 будет также равно 1.

Спасибо за внимание, всем кому интересна промышленная разработка приглашаю в мой канал.

Давайте рассмотрим уже знакомое дерево:

Прямой обход дерева (Префиксный) - NLR

В прошло части мы уже итерировались по дереву рекурсивно. В нем мы сначала печатали значение узла (Node) затем посещаем левое поддерево (Left) и лишь потом правое поддерево (Right). Такой подход называется прямым или еще префиксным - NLR.

Центрированный обход дерева (Инфиксный) LNR

Теперь сделаем одно минимальное изменение - сначала мы пойдем в левое поддерево (Left) затем распечатаем значение узла (Node) и потом пойдем в правое поддерево (Right) - этот обход называют Инфиксным (от лат. in внутри fixus закрепленный) или центрированным - LNR. Понятие инфиксный прошло из математики. Если очень упрощать значит что N находится между L и R.

И так вроде рекурсия выполнила ровно такой же обход, но теперь процесс распечатки значения узла мы стали делать после того как уходим "влево". Теперь если задуматься то первая печать произойдет лишь когда мы дойдем до нижнего левого узла. Давайте изобразим как будет выглядеть "обход" а порядок печати значений узлов:

Обратный или Постфиксный обход. LRN

Думаю уже понятно что данный подход подразумевает печать значения узла (Node) после посещения левого (Left) поддерева и правого (Right) поддерева - LRN

Порядок распечатки изображен ниже:

Минимальные изменения - большие последствия.

Изза минимальных изменений (меняя лишь порядок одной строчки) мы получили разные обходы дерева. Это позволит нам решать разные задачи в будущем.

Следующий этап.

В следующей статье мы рассмотрим какие задачи мы можем решать используя описанные подходы. Одна из главных целей цикла статей - помочь преодолеть страх задач про деревья во время собеседований. Думаю стоит повторить еще раз - как только вам прилетела задача на деревья во время собеса начинайте с того что напишите функцию обхода. Большинство алгоритмических задач решается именно через рекурсию (но не только через неё).

Кому интересна промышленная разработка и Java приглашаю в мою группу. Спасибо за внимание.

Основные понятия.

Рассматривая бинарные деревья нужно знать следующие понятия:

• Node - он же узел. Это элемент дерева, содержащий какое-то значение, которое может быть любым, от примитива (например, числа) до объекта (например, пользователя).

• Edge или ребро. Ссылка, соединяющая один узел с другим или указывающая на пустое значение (null).

• Root Node. Верхний узел дерева, от которого начинается вся структура.

• Leaf - Узел, не имеющий наследников, то есть находящийся в самом низу иерархии.

• Высота дерева - Количество "уровней", от корня до самого нижнего узла.

Несбалансированные деревья могут выродиться в связный список.

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

Сбалансированные деревья.

Сбалансированные (например красно-черные) при каждом добавлении нового узла проверяют, является ли дерево "несбалансированным". Если условие истино то дерево делает "разворот" свои узлов.

Сбалансированные деревья никогда не вырождаются в связанные списки. В J ava джаве деревья представлены коллекцие TreeMap и TreeSet (который инкапсулирует TreeMap внутри себя).

Как могут быть представлены деревья на уровне кода.

Если мы не используем готовые решения вроде TreeMap то простейшее дерево может быть представлено в виде следующего класса:

Итого что мы имеем:

• String data это то значение которое хранит узел. Это может быть любым объектом - в нашем случае просто строка.

• Node left - ссылка на левого наследника.

• Node right - ссылка на правого.

Используя Node класс создадим дерево

Поочередно инициализируем наше дерево с 7 узлами

Изобразим полученное дерево:

Итерация по дереву - один из самых важных навыков для решения задач.

Большинство (если не все) задач, связанных с деревьями требуют итерации или обхода узлов. Чаще всего, умея обходить дерево, вы решаете львиную часть проблемы. В данной статье мы рассмотрим лишь 1 вариант итерации, я напишу отдельные статьи чтобы рассмотреть другие подходы.

Используем рекурсию для итерации и распечатки всех элементов.

Каждый раз когда вам прилетела задача по деревьям, помните - скорее всего в основании решения будет рекурсия (это не всегда так, но довольно часто). Те у вас будет функция которая будет вызывать сама себя. Для распечатки дерева напишем рекурсию которая обходит все элементы начиная с левого наследника:

Код вроде простой но не стоит его недооценивать. Давайте проговорим этапы:

1. Распечатываем значение узла

2. Идем к левому наследнику и повторяем действие (те опять распечатываем и идем влево)

3. после того мы обошли все левые и уткнулись в null мы "возвращаемся" на уровень который находится наверху от нижнего левого и идем в правый наследник

4. зайдя в правый распечатывем и идем влево повторяя шаги 2-3.

Все это звучит странно проще будет изобразить:

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

Кому интересна разработка приглашаю в мой телеграм канал

Реактивнища это не изобретение Спринга.

Первое что нужно знать — реактивщина и реактивный подход не являются изобретением Спринга. Наоборот спринг как обычно поглотил очередную технологию, в данном случае Project Reactor

Реактивный дух времени.

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

Синхронный блокирующий подход:

Предположим что на мнужно выполнить 3 задачи. В старом синхронном подходе мы получим код который будет запущенным одним потоком поочередно и блокирующе.

Реактивный подход

Теперь перепишем ту же задачу используя реактивщину, встроенную в JDK еще с Java 9:

Различия. Небольшая большая разница.

Как можно было понять что сам подход к написанию кода от «естественного» процедурного, где каждый этап движется сверху вниз теряется в реактивщине (хотя и в функциональности он тоже теряется). Реактивный код выглядит скорее как декларативный набор реакций на события и поэтому менее прозрачен и читаем. К сожалению, такой стиль написания кода усложняет процессы разработки, тестирования и поддержки кода.

Но почему реактивщина стала с каждым днем становится все более популярней?

Причин довольно много, но я упомяну лишь два наиболее важных (по моему мнению):

1. Эффективное использование ресурсов (это утверждение истинно только если вы используете неблокирующий код).

2. Отзывчивость системы (Responsive)

Реактивный + неблокирующий подходы = нефть, золото, греча и, конечно же, акции эппл.

Если проанализировать среднестатистический цикл жизни потока то можно заметить что большую часть времени (иногда по 99% времени)

находится либо:

1. В состоянии ожидании доступа к локу те в состоянии ожидании монитора BLOCKED или WAITING

2. В "логическом ожидании" какого то ресурса как то ответа базы, сервиса или просто базы.

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

Решением является совместное использования реактивщины и неблокировщины. Первая организует процесс в котором пул потоков ожидает задачи под выполнение а неблокирующий подход не заставляет ждать потока в рамках одной из задач.

Отзывчивость системы. (Responsiveness)

Один из весомых плюсов реактивщины - возможность получения данных по мере их появления. А как следствие любые решения поверх реактивщины отзывчивы для пользователя и не висят тысячами лет пока все данные не подгрузятся.

Давайте уже, что нибудь попишем.

Как я уже упомянул есть несколько реактивных решений, но в рамках статьи мы напишем Спринговые классические решения.

Перед тем как начать. Если выше на путь реактивнищы - пути обратно нет. Все слои внутри приложений надо стараться писать именно в этом стиле. И конечно не забывать про неблокируйщий подход. Если следовать блокирующему то потоки будут стопорится именно у такой блокируюей воронки.

Что это значит на практике?

А на практике это значит что старые библиотеки вроде rest template (общение по http), jdbc template (связь с базой) должны быть выпилены и заменены не реактивные и неблокирующие:

1. Rest Template -> WebClient

2. JdbcTemplate -> DatabaseClient (R2DBC)

3. FileSystemResource (чтение файлов) -> ReadableResource

4. И так далее для соответствующий библиотек.

Пишем классический Фронт Бэк База на Спринге.

Пример ниже не является самым сложным, но скорее показательным. Напишем простую локику:

1. К нам приходит http запрос

2. Мы перенаправляем запрос в базу

3. Как база дает первый ответ мы кидаем данные на фронт

4. Данные на фронте парсятся по мере появления (а не лишь когда все будут доступны)

Если говорить упрощенно то весь код по сути будет сводится к тому что мы будем прокладывать трубы в виде Flux или Mono объектов.

Стоит помнить что вся реактивная магия Спринга возможно лишь когда при его старте используется WebFlux'овый фреймворк. Старый вариант запуска Спринга с каким нибудь томкатом под капотом не сработает. Поэтому зависимости ниже обязательны:

Начнем с базы, используем

Пробросим Flux используя DatabaseClient:

Теперь полученный Flux выставим на сторону фронта:

Наверно вы заметили что возвращаемый тип не application/json. Да тип x-ndjson. Если использовать стандартный application/json то данные которые будут улетать на фронт будут неполный и конвертировать их в целые объекты будет головной болью. Это недостаток потокового подхода (хотя по сути это 1 http запрос, просто растянутый). x-ndjson формат позволяет кидать на фронт кидать объекты

Читаем на фронте. Код неидеален, скорее служит в качестве простого примера.

Код выше делает следующее:

1. Делает http запрос

2. Ожидает ответа

3. Как только ответ прилетает начинает читать его по частям и писать в конcоль

Приведенный пример является довольно простым, возможности WebFlux гораздо богаче и позволяют манипулировать данными в асинхронном, реактивном подходе. Но код становится сложнее для написания, чтения и поддержки.

Еще раз про эффективный расход процессорных ресурсов.

Я еще раз хочу упомянуть что реактивные, неблокирующие решение написанные прямыми руками позволяют выжать максимум из предоставленных ресурсов. Особенно это актуально во времена микросервисов. Все чаще на проектах под небольшой микросервис могут выделить не более чем 1/0.5/0.1 CPU и я в общем поддерживаю такой подход.

Виртуальные потоки VS Реактивщина.

Эта тема заслуживает отдельного поста. И он будет следующим если эта статья зайдет. Дайте знать в комментах если интересно.

Спасибо за внимание, больше бесплатных статей и стримов в моей группе про джаву и смежные технологии.