Изменения
→Способы реализации структуры
==Способы реализации структуры==
Операции объединения и разделения красно-черных деревьев выполняется за <tex>O(\log n)</tex><ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.4875&rep=rep1&type=pdf Ron Wein {{---}} Efficient Implementation of Red-Black Trees.]</ref>.
===Декартово дерево по неявному ключу===
Также, можем хранить последовательности вершин эйлерова обхода в [[Декартово_дерево_по_неявному_ключу|декартовом дереве по неявному ключу]]. Глубина декартового дерева, построенного на массиве из n вершин, будет поддерживаться logn. Операции объединения и разделения так же выполняются за log n.
==См. также==
