🌳 Основные деревья в Python | B+ дерево ( B+ tree )

Вы когда-нибудь задумывались, как базы данных мгновенно находят нужные записи среди огромного количества данных? Всё дело в эффективной структуре данных — B+ дереве.

🔖Основные особенности дерева:

🔵Все данные — в листьях. Внутренние узлы выступают лишь как «указатели» или «оглавление», что делает поиск по диапазону невероятно быстрым (например, «найти всех пользователей с 10 по 100»).

🔵Листья связаны в список. Это позволяет легко и быстро обходить все данные в отсортированном порядке.

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

🔜Где используется? Практически везде! Это основа индексов в MySQL, PostgreSQL, MongoDB и многих других СУБД. Именно B+-дерево позволяет им работать быстро и стабильно.

📚 Дополнительные материалы для прочтения:

Базовые знания habr.com

Реализация дерева GitHub

🧑‍💻@IT_Python_ZheglY | #python #деревья

⚖️ Что такое балансировка дерева?

Балансировка — это процесс поддержания дерева в «стройной» форме, чтобы не было очень длинных веток и очень коротких.

Зачем это нужно? Балансировка гарантирует, что высота дерева остаётся логарифмической по отношению к числу элементов, а значит, операции поиска, вставки и удаления будут выполняться за O(log n) — то есть, очень быстро.

🔖Основные виды балансировки:

1. Балансировка поворотами |AVL-деревья

🔵Следят за идеальным балансом
🔵После каждого изменения проверяют разницу высот веток
🔵Если разница > 1 — делают повороты для выравнивания
🔵Идеально для частого поиска
❗️ Много поворотов замедляет добавление/удаление

2. Балансировка разделкнием и слиянием | B-деревья и B+-деревья

🔵Хранят несколько ключей в одном узле
🔵При переполнении делятся пополам
🔵При опустошении объединяются с соседом
🔵Идеальны для работы с диском и базами данных
❗️ Сложнее в реализации

3. Красно-чёрные деревья

🔵 Не гонятся за идеальным балансом
🔵 Следят за цветом узлов (красный/чёрный) по простым правилам
🔵Быстрое добавление и удаление
❗️Поиск чуть медленнее, чем в AVL

📚 Дополнительные материалы для прочтения:

Информация по деревьям

Информация по балансировкам

🧑‍💻@IT_Python_ZheglY | #python #деревья

🔍 ОСНОВНЫЕ ОПЕРАЦИИ С ДАННЫМИ: ЧТЕНИЕ, ПОИСК, ВСТАВКА, УДАЛЕНИЕ

📖 ЧТЕНИЕ (Access) Доступ к данным по известному местоположению(индексу или ключу)

🔵Массивы: O(1) — мгновенный доступ по формуле "адрес = начало + индекс × размер"
🔵Связные списки: O(n) — требуется последовательный проход от начала
🔵Хэш-таблицы: O(1) — вычисление хэша и мгновенный доступ к ячейке
🔵Деревья: O(log n) — быстрый спуск по ветвям
🔜Применение: загрузка профилей, отображение товаров, чтение конфигураций

🔍 ПОИСК (Search) Нахождение элемента по значению(а не по позиции)

🔵Линейный поиск: O(n) — последовательная проверка всех элементов (долго)
🔵Бинарный поиск: O(log n) — работает только с отсортированными данными
🔵Хэш-таблицы: O(1) — идеально для поиска по ключу
🔵Деревья: O(log n) — эффективный поиск в сбалансированных структурах
🔜Применение: поиск пользователей, проверка авторизации, фильтрация данных

➕ ВСТАВКА (Insertion) Добавление новых элементов в структуру данных

🔵Массивы: O(n) — требует сдвига элементов (кроме вставки в конец)
🔵Связные списки: O(1) — быстрое изменение указателей
🔵Хэш-таблицы: O(1) — вычисление позиции по хэшу и запись
🔵Деревья: O(log n) — поиск места
и балансировка
🔜Применение: регистрация
пользователей, добавление заказов, логирование

❌ УДАЛЕНИЕ (Deletion) Удаление элементов из структуры данных

🔵Массивы: O(n) — требует сдвига всех последующих элементов
🔵Связные списки: O(1) — быстрое перенаправление указателей
🔵Хэш-таблицы: O(1) — пометка ячейки как удаленной
🔵Деревья: O(log n) — удаление узла с последующей балансировкой
🔜Применение: удаление аккаунтов, очистка кэша, отмена действий

📚 Дополнительные материалы для прочтения:

Основные структуры данных

🧑‍💻@IT_Python_ZheglY | #python
#программирование #алгоритмы #данные #структурыданных

🧠 Что такое энтропия Шеннона и как она измеряет хаос?

Представьте, что вы пытаетесь угадать, что скажет ваш друг. Если он всегда говорит «да» — это скучно и предсказуемо. Если он отвечает случайно — это хаос и неопределенность. Энтропия Шеннона — это число, которое точно измеряет эту самую неопределенность.

📉 Формула:

H = - Σ [p_i * log₂(p_i)]

Где:

H — энтропия (в битах).

p_i — вероятность каждого возможного события.

Σ — сумма по всем событиям.
———————————-————————————————————
Информационная энтропия подчиняется следующим закономерностям:

А) Энтропия события равна 0, если его вероятность равна 1 (100%);

Б) Энтропия двух независимых событий равна сумме энтропий этих событий;

В) Энтропия максимальна, если все события равновероятны.

Получается, чем сложнее предсказать исход события, тем больше информации оно несёт. Если событие редкое и непредсказуемое, мы называем его новостью и наделяем информационной ценностью. Если же оно повторяется часто и о нём постоянно рассказывают, его информационная ценность теряется.
———————————-————————————————————
🎲 Простой пример: Монетка

Честная монетка (орёл/решка по 50%).
Энтропия: H = - [0.5*log₂(0.5) + 0.5*log₂(0.5)] = 1 бит.
Максимальная неопределенность! Памяти на кодирование информации уйдет больше.

Нечестная монетка (орёл — 99%, решка — 1%).
Энтропия: H ≈ 0.08 бита.
Система предсказуема, неопределенность мала. Памяти на кодирование информации уйдет мало.

💡 Где это используется?
Энтропия — не просто теория, она везде в нашей цифровой жизни:

🔵Сжатие данных (ZIP, RAR): Алгоритмы ищут избыточность (низкую энтропию) в данных и упаковывают их меньше.

🔵Криптография: Случайные ключи должны иметь максимальную энтропию, чтобы их было невозможно угадать.

🔵Машинное обучение: С помощью энтропии строят деревья решений, задавая вопросы, которые сильнее всего уменьшают неопределенность.

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

Энтропия Шеннона — это фундаментальная мера хаоса и неопределенности, которая позволяет делать наши технологии эффективнее и умнее.

📚 Дополнительные материалы для прочтения:

Информация об информации. Энтропия Шеннона, демон Максвелла и предел Ландауэра

🧑‍💻@IT_Python_ZheglY | #python
#программирование #данные

🔥Задача с Leetcode #392: Is Subsequence

Условие:
Даны две строки s и t. Проверить, является ли s подпоследовательностью t.

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

Примеры:

s = "abc", t = "ahbgdc" → true

s = "axc", t = "ahbgdc" → false

💡Идея решения:

🔵Идем по строке t и ищем символы из s по порядку

🔵Когда находим совпадение - двигаем указатель s на следующий символ.

🔵Если прошли всю s - возвращаем true

Сложность:

⏰ Время: O(n) - проходим по строке t один раз

💾 Память: O(1) - используем только константную память

🖥 Видео разбор задачи NeetCode

🧑‍💻@IT_Python_ZheglY | #leetcode #python

🔡 ЧТО ТАКОЕ ASCII? 🔡

Знаете, как компьютер понимает буквы, цифры и даже смайлики? Всё начиналось с простого и гениального — кода ASCII (American Standard Code for Information Interchange — Американский стандартный код для обмена информацией).

📟 Что это такое?
Каждой букве, цифре и знаку препинания присвоен свой уникальный номер. Например:

A → 65
a → 97
0 → 48
! → 33

Чтобы узнать код символа надо лишь найти пересечение (сначала строка, потом столбец)

Компьютер хранит и обрабатывает эти числа, а когда нужно показать текст — просто подставляет нужную букву по таблице. Всё гениальное просто!

⚡️ История создания:

Таблица ASCII была создана аж в 1963 году! Изначально в ней было всего 128 символов (7 бит). Этого хватало для английского языка, цифр и базовых управляющих команд.

Позже появилась расширенная версия на 256 символов (1 байт), куда добавили символы псевдографики и буквы европейских языков.

При кодировании символов всех алфавитов (японского, китайского и других) одного байта недостаточно, поэтому применяется Unicode, который
измеряется двумя байтами – количество символов 216 = 65536.

🤔 КОИ-8, Windows-1251

С ASCII возникла проблема — кириллицы в ней не было! Поэтому в СССР и России придумали свои кодировки: КОИ-8, Windows-1251, а позже на смену им пришёл универсальный Unicode

🧠 Почему это важно знать?

Без ASCII не было бы ни текстовых сообщений, ни кода программ, ни интернета в том виде, в каком мы его знаем.

Это основа основ, фундамент, на котором построена вся цифровая текстовая информация.

📚 Дополнительные материалы для прочтения:

Википедия про ASCII

Статья на Хабр

🧑‍💻@IT_Python_ZheglY | #ASCII #кодировка #программирование