Изменения

Теперь усовершенствуем <tex>x-fast-trie </tex> до <tex>y-fast-trie</tex>, который занимает <tex>O(n) </tex> памяти, а все операции выполняются за <tex>O(\log w)</tex>, правда, для модифицирующих операций эта оценка будет амортизированной.

Пусть <tex>a_1 < a_2 < a_3 < ... < a_n </tex> - числа, которые нужно хранить в боре.Выберем какое-то <tex>k </tex> (что за <tex>k </tex> - будет видно дальше). Разобьём их на <tex>s </tex> блоков размером от <tex>\frac{k}{2}</2 tex> до <tex>2k</tex>, а точнее<tex>B_{11} < B_{12} < ... < B_{1n1} < B_{21} < B_{22} < ... < B_{2n2} < ... < B_{s1} < B_{s2} < ... < B_{sns}Выберем в каждом блоке какого-нибудь представителя. И поместим этих представителей в x-fast-trie. Всего в x-fast-trie будет O(2 * n * w </ k) элементов. Поэтому если выбрать k = Omega(w), то x-fast-trie будет занимать O(n) памяти.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)</2 До 2 * w элементовtex>, поэтому его высота то <tex>x- fast-trie</tex> будет занимать <tex>O(log wn)</tex> памяти.

Каждый лист <tex>x-fast-trie</tex> является представителем блока, а все остальные элементы блока (в т. ч. и представителя) подвесим к листу как сбалансированное двоичное дерево поиска. В дереве может храниться от <tex>\frac{w}{2} До <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> памяти.

Находим <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> выполняются аналогично.

Вставка элемента <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>.

Удаление происходит аналогично, только если размер дерева станет <tex>\frac{w/}{2 } - 1</tex>, то надо его слить с любым соседним деревом. А если после слияния размер получившегося дерева станет больше <tex>2 * \cdot w</tex>, то надо его разделить аналогично предыдущему случаю.

Заметим, что вставка, которая не модифицирует верхний бор, выполняется за истинный <tex>\log(w)</tex>, также и <tex>succ, pred</tex>.

Применим амортизационный анализ, используя метод предоплаты. Копим деньги на дешевых операциях. Слиянием массивов осуществляется за <tex>O(w)</tex>, как и разделение. Поэтому, если мы накопим <tex>\Omega(w) </tex> дополнительных денег на дешёвых операциях, то сумеем расплатиться за все остальные, просто кладя положив константное число дополнительных монет во время каждой операции. Худший случай для разделенияслучай произойдет, если мы дальше будем только добавлять элементы - было <tex>\frac{w/}{2 } - 1 </tex> и <tex>2 * \cdot w</tex>, слили, стало больше <tex>2 * \cdot w</tex>, разделели, таким образом получили два дерева с <tex>\frac{5\cdot w}{4}</4 * w tex> элементами. Худший случай для слияния, когда у нас <tex>w </tex> элементов (просиходит после разделения <tex>2 * \cdot w + 1 </tex> дерева). Заметим, что в каждом случае дерево находится на расстоянии <tex>\Theta(w) </tex> от границ. Следовательно, если мы будем класть определённое константное число монет, то скопим их достаточно, чтобы расплатиться за преобразование верхнего дерева.

Получаем амортизированную оценку <tex>O(\log(w)) </tex> и истинную - <tex>O(w)</tex>.

Получилась та же оценка на операции, что и у [[Дерево ван Эмде Боаса | Ван Эмде Боаса]], но структура данных занимает <tex>O(n) </tex> памяти.