Изменения

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

Деревья Эйлерова обхода

8 байт добавлено, 22:54, 18 декабря 2016
Реализация структуры
[[Файл:Balanced tree.png |center]]
Объединение и разделение красно-черных деревьев выполняется за <tex>O(\log n)</tex><ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.4875&rep=rep1&type=pdf {{---}} Parser generator]</ref>{{---}}.
Для каждой вершины храним указатели на её первое и последнее вхождение в последовательность. Значит, имеем доступ к ним за <tex>O(1)</tex>.
Анонимный участник

Навигация