243
правки
Изменения
→Быстрый цифровой бор (x-fast-trie): добавлено немного зелёного цвета
При вставке с помощью <tex>\mathrm{succOrPred}</tex> и двусвязного списка находим следующий и предыдущий элементы и вставляем нужный элемент между ними. А также при создании новой вершины (у которой будет только один ребенок) на обратном пути рекурсии заменяем ссылки.
<code style = "display: inline-block;">
<font color="green">// prefixes {{---}} HashMap всех префиксов бора</font> <font color="green">// узлы списка и дерева будем хранить одним типом: узлом с ссылками на правый и левый элементы, а содержимым {{---}} целым числом</font> <font color="green">// только в списке будет храниться само число, а боре 1, если вершина {{---}} лист, и 0 в остальных случаях</font>
'''insert'''(x):
'''if''' x '''in''' prefixes <font color="green">// ''x'' содержится в боре</font> '''return''' <font color="green">// тогда не добавляем его</font> '''Node ''' left = pred(x), right = succ(x), node = Node(x) insert node между left и right в двусвязном списке листьев</font> // передаём ссылку на элемент в списке, чтобы сделать на него быструю ссылку в случае отсуствия отсутствия одного из сыновей</font>
root = insertNode(root, w, node)
prefixes.addAll(allPrefixes(x))
'''if''' depth == 0
'''return''' vertex
'''if''' bit(node.value, depth) == 0 <font color="green">// depth-й бит, т. е. соответствующий текущей глубине</font>
vertex.left = insertNode(vertex.left, depth - 1, node)
'''else'''
