243
правки
Изменения
→Быстрый цифровой бор (x-fast-trie)
<font color="green">// узлы списка и дерева будем хранить одним типом: узлом с ссылками на правый и левый элементы, а содержимым {{---}} целым числом</font>
<font color="green">// только в списке будет храниться само число, а боре 1, если вершина {{---}} лист, и 0 в остальных случаях</font>
'''insertfunction'''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 color="green">// передаём ссылку на элемент в списке, чтобы сделать на него быструю ссылку в случае отсутствия одного из сыновей</font>
root = insertNode(root, w, node)
prefixes.addAll(allPrefixes(x))
'''insertNodefunction'''insertNode(vertex, depth, node):
'''if''' vertex == <tex> \varnothing </tex>
vertex = Node(left = <tex>\varnothing</tex>, right = <tex>\varnothing</tex>, terminal = depth == 0)
