Изменения

Проще говоря, данная структура позволяет хранить <tex>k</tex>-битные числа и производить над ними операции <tex>\mathttmathrm{find}</tex>, <tex>\mathttmathrm{insert}</tex>, <tex>\mathttmathrm{remove}</tex>, <tex>\mathttmathrm{next}</tex>, <tex>\mathttmathrm{prev}</tex>, <tex>\mathttmathrm{min}</tex>, <tex>\mathttmathrm{max}</tex> и некоторые другие операции, которые присущи всем деревьям поиска.

Пусть у нас есть <tex>k</tex>-битное число <tex>x</tex>. Разобьем это число таким образом, что <tex>\mathttmathrm{high(x)}</tex> {{---}} число, соответствующее <tex>k/2</tex> старшим битам числа <tex>x</tex>, а <tex>\mathttmathrm{low(x)}</tex> соответствует <tex>k/2</tex> младшим битам. Тогда информация, хранится ли в данном дереве число <tex>x</tex>, эквивалентна информации, содержится ли в дереве <tex>children[\mathttmathrm{high(x)}]</tex> число <tex>\mathttmathrm{low(x)}</tex>.

*иначе ищем число <tex>\mathttmathrm{low(x)}</tex> в поддереве <tex>children[\mathttmathrm{high(x)}]</tex>.

Заметим, что выполняя операцию <tex>\mathttmathrm{find}</tex>, мы либо спускаемся по дереву на один уровень ниже, либо, если нашли нужный нам элемент, выходим из нее. В худшем случае мы спустимся от корня до какого-нибудь 1-дерева, то есть выполним операцию <tex>\mathttmathrm{find}</tex> столько раз, какова высота нашего дерева. На каждом уровне мы совершаем <tex>O(1)</tex> операций. Следовательно время работы <tex>O(\log k)</tex>.

**вставим во вспомогательное дерево <tex>aux</tex> число <tex>\mathttmathrm{high(x)}</tex>, если соответствующее поддерево <tex>children[\mathttmathrm{high(x)}]</tex> до этого было пусто.**вставим число <tex>\mathttmathrm{low(x)}</tex> в поддерево <tex>children[\mathttmathrm{high(x)}]</tex>, за исключением ситуации, когда текущее дерево {{---}} это 1-дерево, и дальнейшая вставка не требуется.

Нетрудно увидеть, что данная операция работает за время <tex>O(\log k)</tex>. На каждом уровне дерева мы выполняем <tex>O(1)</tex> операций. После этого возможны 2 случая: поддерево <tex>children[\mathttmathrm{high(x)}]</tex> пусто, и мы будем производить дальнейшую вставку и в него, и во вспомогательное дерево <tex>aux</tex>, или же поддерево не пусто, и мы просто спустимся на уровень ниже. Но если поддерево <tex>children[\mathttmathrm{high(x)}]</tex> пусто, то вставка в него будет выполнена за <tex>O(1)</tex>, так как мы всего лишь обновим поля <tex>min</tex> и <tex>max</tex>. Все остальные операции будут выполнятся уже со вспомогательным деревом <tex>aux</tex>, высота которого на 1 уровень меньше, чем высота текущего. Если же поддерево <tex>children[\mathttmathrm{high(x)}]</tex> не пусто, то мы просто перейдем к вставке элемента в это поддерево, высота которого так же на 1 меньше, чем у текущего. В итоге, каждый раз, выполнив <tex>O(1)</tex> операций, мы переходим к дереву, высота которого на 1 меньше, чем у текущего. Следовательно, количество операций пропорционально высоте дерева, которая, как уже было показано, <tex>O(\log k)</tex>. То есть операция вставки займет <tex>O(\log k)</tex> времени.

*если же <tex> x \neq min </tex> и <tex> x \neq max </tex>, то мы должны удалить <tex>\mathttmathrm{low(x)}</tex> из поддерева <tex>children[\mathttmathrm{high(x)}]</tex>.Так как в поддеревьях хранятся не все биты исходных элементов, а только часть их, то для восстановления исходного числа, по имеющимся старшим и младшим битам, будем использовать функцию <tex> merge </tex>. Также нельзя забывать, что если мы удаляем последнее вхождение <tex>x</tex>, то мы должны удалить <tex>\mathttmathrm{high(x)}</tex> из вспомогательного дерева.

Оценка времени работы операции <tex>\mathttmathrm{remove}</tex> такая же, как и у операции <tex>\mathttmathrm{insert}</tex>. На каждом уровне дерева мы совершаем <tex>O(1)</tex> операций и переходим к удалению элементов максимум в двух деревьях(в одном поддереве и во вспомогательном дереве), чьи высоты на один меньше текущей. Но если мы производим операцию удаления из вспомогательного дерева, значит удаление из поддерева потребовало <tex>O(1)</tex> операций, так как оно содержало всего один элемент. В итоге, количество операций пропорционально высоте дерева, то есть <tex>O(\log k)</tex>.

**если в дереве есть еще числа, большие <tex> x </tex>, и чьи старшие биты равны <tex> \mathttmathrm{high(x)} </tex>, то продолжим поиск в поддереве <tex> children[\mathttmathrm{high(x)}] </tex>, где будем искать число, следующее после <tex> \mathttmathrm{low(x)} </tex>.

Время работы, как и всех предыдущих функций, оценивается так же, и равно <tex>O(\log k)</tex>. Функция <tex>\mathttmathrm{prev} </tex> реализуется аналогично.

*cортировка последовательности из <tex> n </tex> чисел. Вставим элементы в дерево, найдем минимум и <tex> n - 1</tex> раз вызовем функцию <tex> \mathttmathrm{next} </tex>. Так как все операции занимают не более <tex> O(\log k)</tex> времени, то итоговая асимптотика алгоритма <tex> O(n \cdot \log k)</tex>, что даже лучше, чем [[Цифровая сортировка|цифровая сортировка]], асимптотика которой <tex> O(n \cdot k)</tex>.