Изменения

Перейти к: навигация, поиск

Сверхбыстрый цифровой бор

69 байт добавлено, 23:54, 8 июня 2013
succOrPred
Вторая модификация - добавим ссылки.
Операции поиска минимума и максимума дорогие, выполним их за О(1). Теперь становится понятно, что необязательно спускаться до минимума или максимума в дереве. Если у вершину нет левого сына (отметим одним битом) вместо ссылки на левого сына сделаем ссылку на минимум в правом поддереве, что удобно для нашей реализации succOrPred. Если нет правого сына, то храним ссылку на максимум в левом поддереве. [[File:TrieMin.jpg|thumb|200px400px|Ссылка на минимум]] [[File:Trie_max.jpg|thumb|400px|Ссылка на максимум]]
===insert===
Анонимный участник

Навигация