1. Балансировка красно-чёрных деревьев — Три случая
Двоичные деревья поиска — эта структура данных для хранения элементов с возможностью быстрого поиска. Идея проста и гениальна: «меньше – налево, больше – направо». На этом простота заканчивается и начинаются сложные вопросы балансировки дерева, чтобы оно не превратилось в длинную ветку.
В этой статье мы дадим определение, перечислим правила размещения элементов в красно-чёрном дереве, рассмотрим алгоритм балансировки и закрепим сказанное на примере. Более подробно эту тему, а также другие виды двоичных деревьев поиска мы изучаем на курсе «Алгоритмы для разработчиков». Читать
2. Ход конём по битам. Шахматный Bitboard
Шахматный конь стоит на шахматной доске и задумчиво смотрит в шахматную даль. Сколько разных ходов он может сделать?
Хвала изобретателю шахмат, на доске 64 клетки.
Хвала архитектору компьютеров — у типа ulong тоже 64 бита.
Это же надо было случиться такому совпадению!
Напрашивается гениальная идея — хранить всю доску в одном целом числе! Для этого решения существует даже специальный термин — Bitboard — битовая доска.
Так как же быстро найти количество ходов шахматного коня, используя эту идею? Читать
3. Алгоритм Джонсона на орграфе с отрицательными дугами
Алгоритм Джонсона находит кратчайший путь между всеми парами вершин во взвешенном ориентированном графе с отрицательными весами без негативных контуров.
О, как звучит! Давайте разберём условие задачи по частям. Читать
4. Удаление узлов из красно-чёрного дерева
Удаление узлов из красно-чёрного дерева — непростая задача, поэтому имеет смысл разделить её на несколько частей и рассмотреть каждый случай отдельно.
В прошлой статье мы рассмотрели правила формирования красно-чёрного дерева поиска и рассмотрели случаи балансировки при добавлении элементов.
Теперь поговорим об удалении элементов. Читать
5. Идеальное хэширование
Какова сложность поиска элемента по ключу? Это зависит от того, какую структуру данных использовать.
В односвязном списке — линейная сложность.
В отсортированном массиве или в двоичном дереве поиска — логарифмическая сложность.
В хэш-таблице — сложность константная. Но это в лучшем случае. А в худшем … стремится к линейной…
А можно ли создать идеальную хэш-таблицу, чтобы сложность поиска элемента даже в худшем случае оставалась константной? Читать
6. Пирамидальная сортировка выбором
Один из самых необычных алгоритмов сортировки массива — это HeapSort, в основе которого лежит алгоритм сортировки выбором, используется структура данных «куча» для быстрого нахождения максимального элемента, а также способ хранения двоичного дерева в линейном массиве. Разберёмся со всем по порядку.
