Изменения

Перейти к: навигация, поиск

Fusion tree

342 байта добавлено, 20:30, 5 июня 2015
Структура
* у всех вершин, кроме листьев, <tex>B = w^{1/5}</tex> детей,
* время, за которое определяется, в каком поддереве находится вершина, равно <tex>O(1)</tex>.
Такое время работы достигается за счет хранения дополнительной информации в вершинах. Построим [[:Сверхбыстрый_цифровой_бор|цифровой бор]] из ключей узла дерева. Всего <tex>B - 1</tex> ветвящихся вершин. Биты, соответствующие уровням дерева, в которых происходит ветвление, назовем существенными и обозначим их номера <tex>b_0, b_1\ldots b_{r-1}</tex>. Количество существенных битов <tex>r</tex> равно не больше <tex>B - 1</tex> (все ребра на уровне детей ветвящейся вершины (обведены на рисунке) являются существенными битами, и так как ветвящихся вершин <tex>B - 1</tex>, значит, и количество уровней с детьми не больше <tex>B - 1</tex>, поскольку на одном уровне могут быть несколько ветвящихся вершин).
[[Файл:Fusion.png||500x400px|center|визуализация функции sketch]]
317
правок

Навигация