3622
правки
Изменения
м
→Цифровой бор
==Цифровой бор==
Работаем с целыми числами, которые представляются с помощью <tex>w</tex> битов, аналогично [[Дерево ван Эмде Боаса | дереву Ван Эмде Боаса]]. Мы можем их складывать, вычитать, умножать, сдвигать, производить с ними логические операции, адресоваться ими. В модели памяти <tex>\mathrm{unit~cost~RAM}</tex>, которая сейчас применима к большинству процессоров, эти операции могут быть выполнены за <tex>O(1)</tex>.
'''Цифровой бор''' {{---}} [[Бор | бор]], в котором в качестве строк используются двоичные записи чисел, включая ведущие нули.
Таким образом он имеет глубину <tex>w</tex>.
Цифровой бор поддерживает операции <tex>\mathrm{insert}, ~\ \mathrm{remove}, ~\ \mathrm{find}, ~\ \mathrm{succ}, ~\ \mathrm{pred}</tex>.
Добавление вершины происходит так же, как и в обычном боре.
