Алгоритмы и структуры данных2:Тикеты — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎4 Задача о наименьшем общем предке)
(→‎1. Поисковые структуры данных)
 
(не показаны 4 промежуточные версии этого же участника)
Строка 6: Строка 6:
 
# [[АВЛ-дерево]]
 
# [[АВЛ-дерево]]
 
# [[2-3 дерево]]
 
# [[2-3 дерево]]
−
# взяли [[B-дерево]] 0,5
+
# [[B-дерево]]  
−
## все цифры в тех
+
# взяли [[Красно-черное дерево]] 10
−
# [[Красно-черное дерево]] 10
 
 
## добавить псевдокод для операций
 
## добавить псевдокод для операций
 
## расписать доказательства теорем и утверждений подробнее
 
## расписать доказательства теорем и утверждений подробнее
 
# [[Декартово дерево]]
 
# [[Декартово дерево]]
−
# взяли [[Декартово дерево по неявному ключу]] 1
+
# [[Декартово дерево по неявному ключу]]
−
## В псевдокоде нет проверок на ''null''
+
# [[Splay-дерево]]  
−
# взяли [[Splay-дерево]] 0,25
 
−
## См. также
 
 
# [[Взвешенное дерево]]  
 
# [[Взвешенное дерево]]  
 
# [[Tango-дерево]] 8
 
# [[Tango-дерево]] 8
Строка 23: Строка 20:
 
## См. также
 
## См. также
 
# [[Дерево ван Эмде Боаса]]
 
# [[Дерево ван Эмде Боаса]]
−
# [[Список с пропусками]] 7
+
# взяли [[Список с пропусками]] 7
 
## \theta cделать большой буквой
 
## \theta cделать большой буквой
 
## Определение в начале мутное
 
## Определение в начале мутное
Строка 50: Строка 47:
 
== 2. Дерево отрезков==
 
== 2. Дерево отрезков==
 
# [[Статистики на отрезках. Корневая эвристика]]
 
# [[Статистики на отрезках. Корневая эвристика]]
−
# взяли [[Дерево отрезков. Построение]] 0.5
+
# [[Дерево отрезков. Построение]]
−
## Поправить тех
+
# [[Реализация запроса в дереве отрезков сверху]]  
−
## Поправить псевдокод
 
−
# взяли [[Реализация запроса в дереве отрезков сверху]] 0.5
 
−
## Много пробелов в коде, отформатировать
 
−
## Заменить neutral на varepsilon, введя сначала моноид
 
−
## Добавить построение в См. также
 
−
## В примере случаи разной глубины красиво оформить
 
−
## Поправить псевдокод
 
 
# [[Реализация запроса в дереве отрезков снизу]]
 
# [[Реализация запроса в дереве отрезков снизу]]
 
# [[Несогласованные поддеревья. Реализация массового обновления]] 3
 
# [[Несогласованные поддеревья. Реализация массового обновления]] 3
Строка 86: Строка 76:
 
# [[Решение RMQ с помощью разреженной таблицы]]
 
# [[Решение RMQ с помощью разреженной таблицы]]
 
# [[Двумерная разреженная таблица]]
 
# [[Двумерная разреженная таблица]]
−
# [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
+
# [[Алгоритм Фарака-Колтона и Бендера]]  
 
# [[Алгоритм Хьюи]]
 
# [[Алгоритм Хьюи]]
 
# [[Heavy-light декомпозиция]]  
 
# [[Heavy-light декомпозиция]]  

Текущая версия на 13:58, 18 мая 2019

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 Задача о наименьшем общем предке

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритмы_и_структуры_данных2:Тикеты&oldid=71255»