Изменения
Нет описания правки
[[File:Sverkhbystrybor.jpg|thumb|300px|y-fast-trie]]
Теперь усовершенствуем <tex>x{-}fast{-}trie</tex> до <tex>y{-}fast{-}trie</tex>, который занимает <tex>O(n)</tex> памяти, а все операции выполняются за <tex>O(\log w)</tex>, правда, для модифицирующих операций эта оценка будет амортизированной.
Уменьшим количество занимаемой памяти.
Выберем какое-то <tex>k</tex> (что за <tex>k</tex> - будет видно дальше). Разобьём их на <tex>s</tex> блоков размером от <tex>\frac{k}{2}</tex> до <tex>2k</tex>, а точнее <tex>B_{11} < B_{12} < ... < B_{1n1} < B_{21} < B_{22} < ... < B_{2n2} < ... < B_{s1} < B_{s2} < ... < B_{sns}</tex>
Выберем в каждом блоке какого-нибудь представителя. И поместим этих представителей в <tex>x-fast-trie</tex>. Всего в <tex>x-fast-trie</tex> будет <tex>O(\frac{2 \cdot n \cdot w} {k})</tex> элементов. Поэтому если выбрать <tex>k = \Omega(w)</tex>, то <tex>x{-}fast{-}trie</tex> будет занимать <tex>O(n)</tex> памяти.
Каждый лист <tex>x{-}fast{-}trie</tex> является представителем блока, а все остальные элементы блока (в т. ч. и представителя) подвесим к листу как сбалансированное двоичное дерево поиска. В дереве может храниться от <tex>\frac{w}{2}</tex> До <tex>2w</tex> элементов, поэтому его высота - <tex>O(\log w)</tex>.
Все деревья поиска занимают <tex>O(n)</tex> памяти, и <tex>x{-}fast{-}trie – O(n)</tex> памяти. Поэтому <tex>y{-}fast{-}trie</tex> тоже занимает <tex>O(n)</tex> памяти.
===find===
Находим <tex>succ = x</tex> среди представителей в <tex>x{-}fast{-}trie</tex>, а потом запускаем поиск <tex>succ(x)</tex> в дереве, подвешенном к листу <tex>x</tex>, а также в дереве, подвешенном к листу <tex>pred(x)</tex> среди представителей в <tex>x-fast-trie</tex>. Представителем дерева является необязательно минимальный или максимальный элемент, поэтому нужно запустить в двух деревьях. Заметим, что мы ищем элемент только в двух деревьях, так как искомый элемент точно находится между своим сакцессором и прецессором. <tex>O(\log w)</tex> на поиск в <tex>x{-}fast{-}trie</tex> и <tex>O(\log w)</tex> на поиск в деревьях поиска, поэтому итогая асимптотика - <tex>O(\log w)</tex>.
<tex>succ</tex> и <tex>pred</tex> выполняются аналогично.
===insert===
Вставка элемента <tex>x</tex> происходит следующим образом: найдём <tex>succ(x)</tex> и вставим его в подвешенное к листу дерево. Но может возникнуть плохая ситуация: размер дерева станет <tex>2 \cdot w + 1</tex>. Тогда поступим следующим образом - удалим наше дерево из <tex>x{-}fast{-}trie</tex>, разделим его на элементы, из которых построим два дерева размером <tex>w</tex> и <tex>w + 1</tex>, и вставим в <tex>x{-}fast{-}trie</tex> их оба. [[АВЛ-дерево |АВЛ-деревья]] или [[Красно-черное дерево |красно-чёрные]] позволяют выполнять слияние за линейное время, поэтому операция вставки выполняется за <tex>O(w)</tex>.
===delete===
