3622
правки
Изменения
→4. Поисковые структуры данных (проверяются)
== 4. Поисковые структуры данных (проверяются)==
:0. [[Поисковые структуры данных]] (''10''):# Табличка поисковых структур как в Сортировке :# Здесь хочется видеть какую-нибудь классификацию, время работы разных процедур (худшее, среднее), занимаемую память и особенности:# Неплохо бы также сказать о различных деревьях, которых нет на викиконспектах# [[Упорядоченное множество]](''4'')## Расширить определение до элементов, на которых задан порядок## Пункт определение не нужен
## Названия функций в тексте обернуть в \mathrm
## Имена функций оформить в lowerCamelCase
## Добавить ссылок
## Сказать примечание, что если нам не нужна упорядоченность, то с этой задачей неплохо ещё хеши справляются# '''!!!''' [[Дерево поиска, наивная реализация]](''7'')## Правильно оформить англоиязычные термины
## Тире заменить на шаблон
## Отформатировать псевдокод
## Функции в тексте обернуть в \mathrm
## Ссылки объединить с литературой, добавить больше ссылок, оформить красиво
# # Заменить названия обходов на preorder и postorder## Добавить простые рекурсивные варианты всех (или почти всех операций), когда нам не нужно хранить родителей, в удалении есть два способа реализации, пояснить разницу## Кажется, что удаление можно написать проще, даже в таком варианте# '''!!!''' [[АВЛ-дерево]](''7'')
## Исправить знаки неравенств в tex
## Заменить тире на шаблон
## Константы обернуть в tex
## Литературу заменить на источники информации, добавить ссылок
## Англоязычные термины
## Псевдокоды поворотов (с родителями и без)
## Картинки, поясняющие расстановку балансов после поворотов (большого и малого), то есть со шкалой высот рядом
## '''!!!''' Рассмотреть реализацию с меньшим количеством памяти в узлах
# [[2-3 дерево]](''1.5'')## Ссылки Как-то структура криво оформлена; неплохо бы ещё сказать, как это на практике хранится/удобно реализовывается.## Источники информаии оформить красивоправильно
## Случаи сделать списком
## Пояснить во вставке про изменения ключей в родителях## ''+4'' за красивую картинку вставки с расщеплением нескольких узлов# [[B-дерево]](''1.5'')## Опять бы структуру красивей оформить
## Увеличить дроби
## Отформатировать псевдокод
## Оформить правильно См. также и Источники информации# '''!!!''' [[Красно-черное дерево]](''7'')## Дефис в определении заменить на тиреАнгоязычные термины
## Тире в тексте {{---}} на шаблон
## Константы взять в tex
## Оформить красиво источники информации
## Добавить См. также
## Определение выделить жирным
## В Кормене чуть другое определение красно-чёрного дерева: рассмотреть эквивалентность
## Добавить операцию [http://citeseerx.ist.psu.edu/viewdoc/downloadА что будет, если сделать корень дерева красным?doi=10.## Чем же 1.бит - это преимущество? Во всех современных ЯП самый маленький тип имеет размер 1байт.109.4875&rep=rep1&type=pdf split]# '''!!!''' [[Декартово дерево]](''6'')
## Тире заменить на шаблон
## Имена функций оформить в lowerCamelCase
## Сделать псевдокод менее похожим на код С++ (без ссылок): пусть split возвращает пару деревьев
## Отформатировать псевдокодРазобраться с приоритетами (см. обсуждение)## Какое-то палево в удалении с k.x - eps## Оформить правильно источники информации## Заменить знаки неравенств# [[Декартово дерево по неявному ключу]](''4'')
## Добавить псевдокод
## Тире заменить на шаблон
## Добавить ссылок
## Функции в тексте обернуть в \mathrm и оформить их в lowerCamelCase
# '''!!!''' [[Splay-дерево]](''8'')## Оформить правильно англоязычные термины
## Исправить знаки неравенств в tex
## Увеличить дроби
## Тире Дефисы заменить на шаблонтире
## Показать, что лемма верна для любого фиксированного веса узла
## Функции оформить в lowerCamelCase
## Пример, когда move to root занимает <tex>\Omega(n)</tex> времени, и заменить O на омегу## Знаки умножения заменить на \cdot## Заменить многоточия на \ldots# '''!!!''' [[Tango-дерево]] (''8'')## Доказательство теоремы Уилбера## А причём тут вообще она?# [[Рандомизированное бинарное дерево поиска]](''4'')
## Отформатировать псевдокод
## Функции в тексте взять в \mathrm
## Умножение сделать везде единообразным, например, через \cdot
## Переменные и константы в тексте взять в tex
## Увеличить дроби## Первое определение выделить жирным## Вертикальную черту в tex заменить на \mid## Оформить правильно источники информации## Убрать скобки вокруг похожих идей# [[Дерево ван Эмде Боаса]](''1'')
## Имена функций взять в \mathrm
## Отформатировать псевдокод
## Англоязычные термины## Оформить правильно источники информации## Добавить См. также# '''!!!''' [[Список с пропусками]](''7'')
## \theta cделать большой буквой
## Определение в начале мутное
## Оформить правильно англоязычные термины
## Для log n уровней неясно: добавить знак умножения надо, и откуда там 2 log n взялось?
## Увеличить дроби
## Пояснить подробней структуру и разделить операции по псевдокодам, добавить пояснений
## Отформатировать псевдокод
## log заменить на \log
## Расписать связь вероятности монетки с числом уровней; добавить пару слов про различные варианты честности монетки и что от них зависит
# # Оформить правильно источники информации## Добавить См. также## Написать, почему все так любят скиплист, особенно в вычислительной геометрии# '''!!!''' [[Fusion tree]](''5'')
## Тире заменить на шаблон
## sketch cделать везде с маленькой буквы, а кое-где исправить snetch на sketch
## XOR заменить на \oplus
## AND тоже заменить на что-то хорошее
## succ cделать с маленькой буквы
## Добавить про цикл Де Брюина и сказать, где он применяется (см. лекции Станкевича)## Оформить правильно источники информации## Сделать в утверждении список через #, убрать ";"## +1 в карму за нахождение непонятно объяснённого момента# [[Сверхбыстрый цифровой бор]](''3'')## Отформатировать псевдокоды## Сказать, почему префиксы в хеше не буду есть много памяти## Добавить См. также# [[Rope]] (''+2 в карму'')## Почему бы не хранить просто вектор указателей на строки, а подстроки брать slice'ами?## И что ещё можно делать с Rope?
== 5. Дерево отрезков (проверяется)==
