Вспоминаю себя, 2009/2010 год, заканчиваю радиотехнический техникум, по учебе ну чуть лучше троечника, чуть хуже хорошиста. Ищу на первых досках объявлений типо сландо или профильных сайтах по электронике типо hpc битые кпк, смартфоны, чтобы купить, поехать на митино или горбу из своего зажопинска за запчастями, починить и продать с наваром хоть каким то, заодно купив первую паяльную станцию и по скудным данным чиню все это. Попутно по знакомым хожу ставлю виндоусы, всякий софт или помогаю с несложным ремонтом ПК. Скоро диплом и надо искать работу, а на работу нигде не берут без опыта работы, везде предлагают поработать пару тройку месяцев бесплатно/за еду , а не нравится - пшёл вон, за забором вооон какая очередь готовых работать за еду.
А сейчас постоянно посты: бегаем умоляем зуммеров чтобы пришли и просто получали деньги, чтобы ну хотя бы просто приходили на работу, а мы охали и ахали, как же так, а вот мы в их годы, а вот они.
А я им завидую, с таким бы рынком как сейчас, да в моё время я бы очень неплохо развернулся.
Деревья являются одним из самых пугающих вещей в разработке. Еще хуже дело обстоит, когда программист встречает задачу, связанную с деревьями, во время собеседования. В этой статье я постараюсь минимизировать боль, связанную с этой темой.
Деревья бывают разные. Мы рассмотрим двоичное сбалансированное.
В данной статье мы рассмотрим наиболее популярные — двоичные сбалансированные (красно-черные) деревья.
Пример бинарного дерева. У каждого листка может быть не более двух наследников.
Основные понятия.
Рассматривая бинарные деревья нужно знать следующие понятия:
Node - он же узел. Это элемент дерева, содержащий какое-то значение, которое может быть любым, от примитива (например, числа) до объекта (например, пользователя).
Edge или ребро. Ссылка, соединяющая один узел с другим или указывающая на пустое значение (null).
Root Node. Верхний узел дерева, от которого начинается вся структура.
Leaf - Узел, не имеющий наследников, то есть находящийся в самом низу иерархии.
Высота дерева - Количество "уровней", от корня до самого нижнего узла.
Несбалансированные деревья могут выродиться в связный список.
Несбалансированные деревья — это деревья, у которых высота левой и правой веток может значительно отличаться. В худшем случае все узлы могут располагаться по одной стороне. В этом случае дерево деградирует до связного списка.
деградированное дерево вырожденное в связанный список.
Сбалансированные деревья.
Сбалансированные (например красно-черные) при каждом добавлении нового узла проверяют, является ли дерево "несбалансированным". Если условие истино то дерево делает "разворот" свои узлов.
Пример красно черного сбалансированного дерева. Именно такое используется в TreeMap
Сбалансированные деревья никогда не вырождаются в связанные списки. В J ava джаве деревья представлены коллекцие TreeMap и TreeSet (который инкапсулирует TreeMap внутри себя).
Как могут быть представлены деревья на уровне кода.
Если мы не используем готовые решения вроде TreeMap то простейшее дерево может быть представлено в виде следующего класса:
Простейший узел. По большому счету это единственный важный момент.
Итого что мы имеем:
String data это то значение которое хранит узел. Это может быть любым объектом - в нашем случае просто строка.
Node left - ссылка на левого наследника.
Node right - ссылка на правого.
Используя Node класс создадим дерево
Поочередно инициализируем наше дерево с 7 узлами
Изобразим полученное дерево:
Итерация по дереву - один из самых важных навыков для решения задач.
Большинство (если не все) задач, связанных с деревьями требуют итерации или обхода узлов. Чаще всего, умея обходить дерево, вы решаете львиную часть проблемы. В данной статье мы рассмотрим лишь 1 вариант итерации, я напишу отдельные статьи чтобы рассмотреть другие подходы.
Используем рекурсию для итерации и распечатки всех элементов.
Каждый раз когда вам прилетела задача по деревьям, помните - скорее всего в основании решения будет рекурсия (это не всегда так, но довольно часто). Те у вас будет функция которая будет вызывать сама себя. Для распечатки дерева напишем рекурсию которая обходит все элементы начиная с левого наследника:
Код вроде простой но не стоит его недооценивать. Давайте проговорим этапы:
Распечатываем значение узла
Идем к левому наследнику и повторяем действие (те опять распечатываем и идем влево)
после того мы обошли все левые и уткнулись в null мы "возвращаемся" на уровень который находится наверху от нижнего левого и идем в правый наследник
зайдя в правый распечатывем и идем влево повторяя шаги 2-3.
Все это звучит странно проще будет изобразить:
Это лишь первая статья но в ней мы ознакомились с основными понятиями. Также мы обошли дерево, используя рекурсию. Это один из самых популярных подходов в решениии подобных задач. В следующей части мы рассмотрим альтернативные варианты работы с деревьями.
В новой серии рубрики «Например» от Академии Eduson программист Илья Воронцов рассказывает о том, как в цифровых продуктах работает условный оператор. Разберитесь всего за 2 минуты ↴
Стартовать в IT лучше всего с каким-то универсальным инструментом. Например, с языком Python — он подойдёт и для аналитики, и для веб- и мобильной разработки, и даже для научной работы.
Сделайте первый шаг на бесплатном курсе от Eduson. Вы узнаете, почему этот язык востребован и как его можно освоить. Поймёте, какие задачи решают разработчики, насколько это подходит вам и даже напишите первые строки кода.
Ну а полностью его освоить можно на курсе «Python-разработчик». Так ещё и гарантировано найти работу — в договоре прописано, что вы получите желанный оффер или деньги за обучение вернут.
Я учавствую тренировках по алгоритмам от Яндекса. Вспоминая, как работает бабл сорт, я нашел несколько интересных фактов о сортировках:
- Пузырьковая сортировка работает медленно из-за черепах - небольших по размеру элементов, находящихся в конце массива. Алгоритм работает таким образом, что именно они долго "ползут" в начало.
- Для оценки временной сложности алгоритмов существует не только O большое. Если сортировка работает за O(n), то ее эффективность ≤ n (то есть, она работает за n, либо быстрее). Если сложность о(n) (о малое), эффективность < n (сортировка точно работает быстрее n). Ω (омега большое), ≥ n ω (омега малое), > n θ (тетта), = n
- В 2022 году модель AlphaDev улучшила алгоритм сортировки коротких последователей на 70%. Поиск алгоритма осуществлялся в виде пошаговой игры, а сама AlphaDev основана на AlpaZero - модели для игры в шахматы.
Первая библиотека на node.js для программирования телеграм-ботов, с которой я познакомился node-telegram-bot-api (ntba). Мне ее подсказал chatGPT. Я не интересовался альтернативами и не вдавался в подробности, а просто начал пользоваться ей. Со временем я к ней привык и уже писал всех своих ботов на ntba. Какие были минусы? На тот момент никаких, ведь мне было не с чем сравнить. Но потом я встретился с grammy, о да. Это была прекрасная дива по сравнению со старенькой ntba в лохмотьях. Ее прекрасный внешний вид и большааая документация сразу привлекли мое внимание. Я решил попробовать написать бота на ней и создал бота модератора для небольшого канала.
Написание этого бота заняло чуть больше времени, ведь нужно было сверяться с документацией (хотя они почти одинаковые). Но теперь я точно знаю что всегда буду писать именно на гремми.
Также скоро запишу отдельный большой пост по программированию ботов