Поговорим про бинарные деревья

Что такое бинарное дерево? Бинарное дерево - это структура данных, суть которой - состояние иерархии узлов, где каждый узел имеет либо ноль, либо не больше двух дочерних узлов. Изначальный узел называется корнем.

Вот простая реализация на C#.

public class BinaryTreeNode<T>
{
    private T _value;
    private BinaryTreeNode<T>? _left;
    private BinaryTreeNode<T>? _right;

    public BinaryTreeNode(T value, BinaryTreeNode<T>? left = null, BinaryTreeNode<T>? right = null)
    {
         _value = value;
         _left = left;
         _right = right;
    }

    //Вот тут какая-то логика
}

В визуальном отображении такая структура как раз и напоминает перевёрнутое дерево.

        Root
       /    \
      A      B
     / \      \
    C   D      E

В чём преимущество бинарных деревьев? В алгоритме обхода.

Предположим, у нас есть некоторые числа: 11, 5, 17, 3, 7, 13, 19, 2, 23.
Предположим, мы вставили их в массив.

У нас есть операции: вставка в середину, добавление, удаление, поиск.
Сложность операций:
- Вставка в середину - O(n), так как нам нужно пересобрать массив.
- Добавление - если размер массива 10, а мы вставляем 11 элемент, то нам придётся собрать массив заново. В итоге O(n). Если добавлением мы перезаписываем 10 элемент, то O(1).
- С удалением с конца тоже самое, что и с добавлением. С середины - тоже самое, что со вставкой.
- Поиск - O(n), если мы не получаем по индексу. Тогда будет O(1).

А теперь предположим тоже самое с бинарным деревом.
Алгоритм сортировки:

Начинаем в корне (верхнем узле).
Сравниваем новое число X с числом V в текущем узле.
Если X < V - идём влево.
Если X > V - идём вправо.
Если X = V - тут уже зависит от вашего желания, что с этим делать. Давайте предположим, что у нас только уникальные значения.

Теперь на числах.
Вставляем 11 - дерево пустое -> 11 становится корнем.
Вставляем 5. Cравниваем с 11.
5 < 11 -> идём влево, место пустое -> вставляем 5 как левый ребёнок 11.
Вставляем 17.
17 > 11 -> идём вправо -> вставляем как правый ребёнок 11.
Вставляем 7.
7 < 11 -> влево к 5;
Дальше 7 > 5 -> вправо от 5 - вставляем там.

Суть: меньше - налево, больше - направо. Это простое локальное правило гарантирует, что любая левая ветка хранит только меньшие значения, а правая - только бОльшие.

Получается вот такой рисунок.

         11
        /  \
       5    17
      / \   / \
     3   7 13  19 
    /           \
   2             23

Примерно такая картина по операциям у нас получается.
h - это высота дерева.

Поиск:
O(h) -> в худшем случае O(n), если у нас дерево состоит только из одной ветки и мы идём только по ней.

Вставка:
O(h) -> в худшем случае O(n).

Удаление:
O(h) -> в худшем случае O(n).

Однако, если у нас хорошо распределённое дерево, как правило O(n) должно происходить редко, так как мы постоянно отсекаем какие-то его стороны. В этом случае также O(h) можно упростить до O(log n).
Таким образом, если дерево хорошо сбалансировано, у него более оптимизированное количество операций.

Однако, как правило такая оптимизация не всегда нужна, так как оперировать тем же List гораздо более удобно и понятно для разработчика. Думать о таких вещах нужно при огромном количестве объектов и при явной проблеме перформанса.

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

🚀 Пост Guru Unity: @Minerope

Update, FixedUpdate, LateUpdate - В чём разница и где что использовать?

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

Все эти методы являются частью жизненного цикла MonoBehaviour:

• Update вызывается каждый кадр игры.
• FixedUpdate вызывается определённый промежуток времени, который указан в настройках Юнити.
• LateUpdate вызывается после того, как все вызовы Update уже отработали. То есть, по сути, в конце кадрового цикла.

Однако, сухие определения - это конечно хорошо, но что с практикой? Когда нам может пригодиться одно, а когда другое?

Update нужен, когда у нас вызывается какая-нибудь логика, работа которой у нас должна выполняться каждый кадр.
Из тривиального - считывание нажатия игрока:

private void Update()
{
    if (Input.GetKeyDown(KeyCode.Space))
    {
        _isJumpRequested = true;
    }
}

В LateUpdate мы рассчитываем логику, которая нам нужна после того, как все кадры уже просчитались.
Например, для слежения камеры за игроком. Если сделать это в Update, то наша камера будет дёрганной. Им нужна итоговая точка объекта, чтобы они его не "догоняли" или не "перегоняли".

Классический пример с камерой:

private void LateUpdate()
{
    Vector3 desiredPosition = _target.position + _offset;
        
    Vector3 smoothedPosition = Vector3.Lerp(transform.position, desiredPosition, _smoothSpeed * Time.deltaTime);
    transform.position = smoothedPosition;

    transform.LookAt(_target);
}

Update приводит позиции к какому-то значению, а LateUpdate выполняется после того, как все Update отработали. Камера будет очень плавно идти за игроком и не будет меняться в рандомный момент кадра, как бы она это делала, если бы была в Update.

В FixedUpdate считывание ввода или слежение камеры добавлять не стоит, так как из-за того, что FixedUpdate работает какой-то определённый константный промежуток. Мы можем пропустить нажатие игрока, а поведение камеры будет выглядеть странно.

Но зачем тогда он вообще нужен?
Этот метод используется для просчётов физики, в которой нужно, чтобы всё работало одинаково, не завися от количества кадров.
FixedUpdate имеет фиксированный timestamp.
То есть, если у нас 60 фпс - Update вызывается 60 раз. Если у нас 20 фпс - 20 раз. Это слишком нестабильно для чётких расчётов.
Timestamp в 0.02 секунды может гарантировать нам, что метод вызовется ровно 50 раз в секунду. Это стабильность. Таким образом у нас физика будет постоянной и не зависеть от такого хаотичного параметра как кадры.

Пример:

private void FixedUpdate()
{
    IsGrounded = Physics2D.OverlapCircle(_groundChecker.position, _data.GroundCheckRadius, _data.GroundLayer);

    if (_isJumpRequested)
    {
        _rigidbody2D.linearVelocityY = _data.JumpForce;
        _isJumpRequested = false;
    }

    if (_isJumpCutRequested && _rigidbody2D.linearVelocityY > 0f)
    {
        _rigidbody2D.linearVelocityY *= _data.JumpCutMultiplier;
        _isJumpCutRequested = false;
    }
}

В следующей части мы поговорим про такую сущность как Time.deltaTime и почему она крайне необходима в контексте Update.

🚀 Пост Guru Unity: @Minerope

🚀 В январе перед нами стояли три ключевые задачи.

1. Миграция на Next.js
Мы перевели публичную часть проекта на Next.js, а дашборд оставили на React.js. Основные работы почти завершены — сейчас занимаемся тестированием и финальными правками.
В процессе столкнулись с рядом инфраструктурных вызовов: текущих ресурсов сервера оказалось недостаточно под новые проекты, поэтому пришлось масштабироваться. Впереди также большая работа по настройке SEO.

2. Сервис для лайвкодинга
Мы разрабатываем сервис лайвкодинга — аналог LeetCode с задачами российских компаний с реальных собеседований. У проекта большие планы:

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

Базовая версия сервиса уже готова и проходит тестирование. Совсем скоро — релиз.

3. Сервис уведомлений
Мы начали разработку сервиса уведомлений, который объединит всю нашу экосистему: платформу, Telegram-каналы и бота.

В Telegram будут публиковаться:

— новые собеседования,
— вопросы и задачи,
— статьи и подборки,
— анонсы,
— вакансии,
— статистика с HH.

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

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

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

P.S. Новогодние скидки продолжают действовать до запуска сервиса лайвкодинга. После релиза цены увеличатся в 2 раза — сейчас самое выгодное время подключиться и поддержать нас.

👉 Членство YeaHub

Впереди много интересного. Спасибо, что вы с нами.✊🏻🚀💪

Update vs FixedUpdate — где двигать объект? + Time.deltaTime

Продолжаем разбор Update.

Вопрос с подвохом: где вызывать такой код — в Update или FixedUpdate?

private void Update()
{
    transform.position += Vector3.forward * 10f;
}

Опытные разработчики уже чувствуют проблему

Если оставить код как есть и вызывать его в Update, скорость движения напрямую зависит от FPS:

• 30 FPS → объект едет медленно
• 120 FPS → объект летит быстрее

И FixedUpdate тоже не решение

Кажется логичным перенести код в FixedUpdate, но тут другая проблема: FixedUpdate вызывается реже, чем кадры
• между вызовами нет отрисовки
• визуально движение становится дёрганным

Решение — использовать Time.deltaTime

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

• Кадр 1 выполнился → прошло 0.008 секунд → Кадр 2 начался → Time.deltaTime = 0.008

Исправляем код:

private void Update()
{
    transform.position += Vector3.forward * 10f * Time.deltaTime;
}

Теперь:
• скорость одинакова при любом FPS
• движение плавное

🤔 Тогда зачем вообще FixedUpdate?

Логичный вопрос:
если есть Time.deltaTime, зачем нужен FixedUpdate?

Коротко:

• Update — визуал и логика
• FixedUpdate — физика

Почему так:

Update вызывается между физическими тиками, он не синхронизирован с физическим движком
FixedUpdate вызывается строго перед физическим шагом

Последовательность такая:

1. FixedUpdate у всех объектов
2. Unity считает физику
• коллизии
• силы
• OnCollisionEnter, OnTriggerEnter и т.д.

Если считать физику в Update (даже с Time.deltaTime), начинаются проблемы:

• туннелирование (объект «пролетает» сквозь коллайдеры)
• нестабильное и непредсказуемое поведение

Итог

Плавное движение, позиция, визуал → Update + Time.deltaTime
Физика, Rigidbody, силы, коллизии → FixedUpdate

🚀 Пост Guru Unity: @Minerope