Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-03-10

1 <ul><li><a>1. Балансировка красно-чёрных деревьев - Три случая</a></li>

2 <li><a>2. Ход конём по битам. Шахматный Bitboard</a></li>

3 <li><a>3. Алгоритм Джонсона на орграфе с отрицательными дугами</a></li>

4 <li><a>4. Удаление узлов из красно-чёрного дерева</a></li>

5 <li><a>5. Идеальное хэширование</a></li>

6 <li><a>6. Пирамидальная сортировка выбором</a></li>

7 </ul><h2><a>1. Балансировка красно-чёрных деревьев - Три случая</a></h2>

8 <p>Двоичные деревья поиска - эта структура данных для хранения элементов с возможностью быстрого поиска. Идея проста и гениальна: "меньше - налево, больше - направо". На этом простота заканчивается и начинаются сложные вопросы балансировки дерева, чтобы оно не превратилось в длинную ветку.</p>

9 <p><em>В этой статье мы дадим определение, перечислим правила размещения элементов в красно-чёрном дереве, рассмотрим алгоритм балансировки и закрепим сказанное на примере. Более подробно эту тему, а также другие виды двоичных деревьев поиска мы изучаем на курсе <a>"Алгоритмы для разработчиков"</a>.</em><a>Читать</a></p>

10 <h2><a>2. Ход конём по битам. Шахматный Bitboard</a></h2>

11 <p>Шахматный конь стоит на шахматной доске и задумчиво смотрит в шахматную даль. Сколько разных ходов он может сделать?</p>

12 <p>Хвала изобретателю шахмат, на доске <strong>64</strong> клетки.Хвала архитектору компьютеров - у типа <strong>ulong</strong> тоже <strong>64</strong> бита.Это же надо было случиться такому совпадению!Напрашивается гениальная идея - хранить <strong>всю доску</strong> в <em>одном целом числе</em>! Для этого решения существует даже специальный термин - <strong>Bitboard</strong> - битовая доска.</p>

13 <p>Так как же <strong>быстро</strong> найти количество ходов шахматного коня, используя эту идею?<a>Читать</a></p>

14 <h2><a>3. Алгоритм Джонсона на орграфе с отрицательными дугами</a></h2>

15 <p>Алгоритм Джонсона находит кратчайший путь между всеми парами вершин во взвешенном ориентированном графе с отрицательными весами без негативных контуров.</p>

16 <p>О, как звучит! Давайте разберём условие задачи по частям.<a>Читать</a></p>

17 <h2><a>4. Удаление узлов из красно-чёрного дерева</a></h2>

18 <p>Удаление узлов из красно-чёрного дерева - непростая задача, поэтому имеет смысл разделить её на несколько частей и рассмотреть каждый случай отдельно.</p>

19 <p>В <a>прошлой статье</a> мы рассмотрели правила формирования красно-чёрного дерева поиска и рассмотрели случаи балансировки при добавлении элементов.</p>

20 <p>Теперь поговорим об удалении элементов.<a>Читать</a></p>

21 <h2><a>5. Идеальное хэширование</a></h2>

22 <p>Какова сложность поиска элемента по ключу? Это зависит от того, какую структуру данных использовать.</p>

23 <p>В односвязном списке - линейная сложность.В отсортированном массиве или в двоичном дереве поиска - логарифмическая сложность.В хэш-таблице - сложность константная. Но это в лучшем случае. А в худшем … стремится к линейной…</p>

24 <p>А можно ли создать идеальную хэш-таблицу, чтобы сложность поиска элемента даже в худшем случае оставалась константной?<a>Читать</a></p>

25 <h2><a>6. Пирамидальная сортировка выбором</a></h2>

26 <p>Один из самых необычных алгоритмов сортировки массива - это HeapSort, в основе которого лежит алгоритм сортировки выбором, используется структура данных "куча" для быстрого нахождения максимального элемента, а также способ хранения двоичного дерева в линейном массиве.<a>Разберёмся со всем по порядку.</a></p>