Алгоритмы и структуры данных2:Тикеты — различия между версиями
м (→5. Поисковые структуры данных) |
м |
||
Строка 1: | Строка 1: | ||
+ | к проверке: кучи, дерева Фенвика, деревья поиска, деревья на отрезках, | ||
+ | |||
== 5. Поисковые структуры данных== | == 5. Поисковые структуры данных== | ||
:0. [[Поисковые структуры данных]] | :0. [[Поисковые структуры данных]] |
Версия 23:38, 8 февраля 2018
к проверке: кучи, дерева Фенвика, деревья поиска, деревья на отрезках,
Содержание
5. Поисковые структуры данных
- Упорядоченное множество
- Дерево поиска, наивная реализация
- АВЛ-дерево
- 2-3 дерево
- B-дерево 0,5
- все цифры в тех
- Красно-черное дерево 10
- добавить псевдокод для операций
- расписать доказательства теорем и утверждений подробнее
- Декартово дерево
- Декартово дерево по неявному ключу 1
- В псевдокоде нет проверок на null
- Splay-дерево 0,25
- См. также
- Взвешенное дерево
- Tango-дерево 8
- Доказательство теоремы Уилбера
- А причём тут вообще она?
- Рандомизированное бинарное дерево поиска 0,25
- См. также
- Дерево ван Эмде Боаса
- Список с пропусками 7
- \theta cделать большой буквой
- Определение в начале мутное
- Оформить правильно англоязычные термины
- Для log n уровней неясно: добавить знак умножения надо, и откуда там 2 log n взялось?
- Увеличить дроби
- Пояснить подробней структуру и разделить операции по псевдокодам, добавить пояснений
- Отформатировать псевдокод
- log заменить на \log
- Расписать связь вероятности монетки с числом уровней; добавить пару слов про различные варианты честности монетки и что от них зависит
- Оформить правильно источники информации
- Добавить См. также
- Написать, почему все так любят скиплист, особенно в вычислительной геометрии
- Fusion tree
- Сверхбыстрый цифровой бор 2
- Отформатировать псевдокоды
- Сказать, почему префиксы в хеше не буду есть много памяти
- Добавить См. также
- Многоточия заменить на \ldots
- Rope
- AA-дерево
6. Дерево отрезков
- Статистики на отрезках. Корневая эвристика
- Дерево отрезков. Построение
- Реализация запроса в дереве отрезков сверху 0.5
- Много пробелов в коде, отформатировать
- Заменить neutral на varepsilon, введя сначала моноид
- Добавить построение в См. также
- В примере случаи разной глубины красиво оформить
- Реализация запроса в дереве отрезков снизу
- Несогласованные поддеревья. Реализация массового обновления 3
- Добавить примеры массовых операций в начало
- В начале определение очень похоже на определение кольца, то есть возможно ДО работает на кольце. Надо бы это пояснить и кинуть интервики на кольцо (см. замечания в обсуждениях)
- Константы взять в tex
- Отформатировать псевдокод
- Обозначения перед псевдокодов взять в \mathtt или в \mathrm
- Оформить правильно источники информации
- Добавить см. также
- Многомерное дерево отрезков
- Сжатое многомерное дерево отрезков
7. Дерево Фенвика
- Дерево Фенвика
- Встречное дерево Фенвика
- Дерево Фенвика для некоммутативных операций 0.25
- Источники информации
- Многомерное дерево Фенвика 0,25
- См. также
8 Задача о наименьшем общем предке
- Алгоритм Мо
- Сведение задачи LCA к задаче RMQ
- Сведение задачи RMQ к задаче LCA
- Метод двоичного подъема 3
- добавить пример работы алгоритма
- Решение RMQ с помощью разреженной таблицы
- Двумерная разреженная таблица
- Алгоритм Фарака-Колтона и Бендера (решение +/-1 RMQ с помощью метода четырех русских)
- Алгоритм Хьюи
- Heavy-light декомпозиция 6
- "решается с помощью heavy-light декомпозиции" — может быть решена
- "Пусть A, B - ко" — дефисы нужно заменить на тире
- В начале у тебя идут вершины a,b и A,B, а потом u,v и a,b. Надо сделать единообразно, чтобы начало конспекта и его конец согласовывались. Например, сделать корни путей большими буквами — норм. Тогда можно либо a,b и A,B, либо u,v и U,V.
- "В данном случае корень одного из путей является вершиной другого." — а почему пути не могут пересекаться крест-на-крест?
- Слишком много повтором «Пусть» в доказательстве леммы.
- "Но LCA должен принадлежать двум путям. Но" — дублирование «Но»
- "Предположим, что LCA не равны" — криво написано, нужно формально исходя из формулировки
- Ну и вообще, как будто слов пожадничал на лемму и кое-как написал
- "Построим декомпозицию." — декомпозицию чего и для чего? Очень плохо оставлять открытый контекст, особенно в начале пункта. Лучше чуть более подробно описать, чтобы было понятно
- "Корень пути, на котором лежит текущая вершина.
- Из всех путей выбираем тот, чья начальная вершина наиболее удалена от корня дерева." — вообще непонятно, как связано то, что мы хотим сохранить с тем, что написано потом. Нет предложения-связки
- "Пусть требуется" — опять пуст
- "Пусть на данной итерации" — как будто других слов нет
- "LCA будет та" — это не по-русски
- Возьми LCA в тексте везде в \mathrm
- "Потому что бесконечно большое количество путей" — откуда в конечном дереве взялось бесконечно большое число путей?
- Алгоритм Шибера-Вишкина
- Алгоритм Тарьяна поиска LCA за O(1) в оффлайн 0,25
- См. также
- Link-Cut Tree
- Rake-Compress деревья 0,25
- Английские термины
9. Хеширование
- Хеш-таблица 0,25
- См. также
- Разрешение коллизий
- Хеширование кукушки
- Идеальное хеширование
- Перехеширование. Амортизационный анализ 1
- Пояснить, почему будет O(1) на добавление при перехешировании
- Фильтр Блума 0,25
- См. также
- Quotient filter 3
- Сделать нормальное описание алгоритма, а то ничего не понятно
- Универсальное семейство хеш-функций 0.5
- Добавить ссылок
- Англоязычные термины
- Смотри обсуждения
- Заменить многоточия на \dots
- Заменить \mod на \bmod
- Заменить знаки неравенств
- Добавить "информации" в источники
- Расширяемое хеширование 5
- Красивые картинки
- Понятное описание