Изменения
→Цифровой бор
Таким образом он имеет глубину w.
Цифровой бор поддерживает операции <tex>insert, remove, find, succ, pred</tex>.
Добавление вершины происходит так же, как и в обычном боре.
===succ===
Поиск следующего элемента осуществляется проходом от корня до вершины, из которой не можем пойти в нужную сторону. Если не смогли пойти влево (по ребру <tex>0</tex>), то ответ - минимум в правом поддереве. Если не смогли пойти вправо, поднимаемся наверх, пока являемся правым ребенком, если стали левым, то поднимаемся, пока у вершины нет правого ребенка (если такой ситуации нет, то запрос больше всех элементов). Тогда ответ - минимум в правом поддереве.
Преимущества: простая реализация, занимает <tex>O(n * w) </tex> памяти, все операции выполняются за <tex>O(w)</tex>.
Хуже [[Дерево ван Эмде Боаса | дерева Ван Эмде Боаса ]] по скорости, но памяти занимает меньше.
==Быстрый цифровой бор (x-fast-trie)==
