Алгоритмы и структуры данных2:Тикеты

Материал из Викиконспекты
Перейти к: навигация, поиск

1. Поисковые структуры данных

0. Поисковые структуры данных
  1. Упорядоченное множество
  2. Дерево поиска, наивная реализация
  3. АВЛ-дерево
  4. 2-3 дерево
  5. B-дерево
  6. взяли Красно-черное дерево 10
    1. добавить псевдокод для операций
    2. расписать доказательства теорем и утверждений подробнее
  7. Декартово дерево
  8. Декартово дерево по неявному ключу
  9. Splay-дерево
  10. Взвешенное дерево
  11. Tango-дерево 8
    1. Доказательство теоремы Уилбера
    2. А причём тут вообще она?
  12. взяли Рандомизированное бинарное дерево поиска 0,25
    1. См. также
  13. Дерево ван Эмде Боаса
  14. взяли Список с пропусками 7
    1. \theta cделать большой буквой
    2. Определение в начале мутное
    3. Оформить правильно англоязычные термины
    4. Для log n уровней неясно: добавить знак умножения надо, и откуда там 2 log n взялось?
    5. Увеличить дроби
    6. Пояснить подробней структуру и разделить операции по псевдокодам, добавить пояснений
    7. Отформатировать псевдокод
    8. log заменить на \log
    9. Расписать связь вероятности монетки с числом уровней; добавить пару слов про различные варианты честности монетки и что от них зависит
    10. Оформить правильно источники информации
    11. Добавить См. также
    12. Написать, почему все так любят скиплист, особенно в вычислительной геометрии
  15. Fusion tree
  16. Сверхбыстрый цифровой бор 2
    1. Отформатировать псевдокоды
    2. Сказать, почему префиксы в хеше не буду есть много памяти
    3. Добавить См. также
    4. Многоточия заменить на \ldots
  17. Rope
  18. AA-дерево
  19. Техника частичного каскадирования
    1. Правильно оформить источники информации
  20. Centroid decomposition

2. Дерево отрезков

  1. Статистики на отрезках. Корневая эвристика
  2. Дерево отрезков. Построение
  3. Реализация запроса в дереве отрезков сверху
  4. Реализация запроса в дереве отрезков снизу
  5. Несогласованные поддеревья. Реализация массового обновления 3
    1. Добавить примеры массовых операций в начало
    2. В начале определение очень похоже на определение кольца, то есть возможно ДО работает на кольце. Надо бы это пояснить и кинуть интервики на кольцо (см. замечания в обсуждениях)
    3. Константы взять в tex
    4. Отформатировать псевдокод
    5. Обозначения перед псевдокодов взять в \mathtt или в \mathrm
    6. Оформить правильно источники информации
    7. Добавить см. также
  6. Многомерное дерево отрезков
  7. Сжатое многомерное дерево отрезков

3. Дерево Фенвика

4 Задача о наименьшем общем предке