Изменения

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

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

121 байт добавлено, 22:53, 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>.
Анонимный участник

Навигация