Изменения

[[АВЛ-дерево |АВЛ-деревья]] или [[Красно-черное дерево |красно-чёрные]] позволяют выполнять слияние и разделение за линейное время, поэтому операции вставки и удаления выполняются за <tex>O(w)</tex>.

Заметим, что вставка, которая не модифицирует верхний бор, выполняется за истинный <tex>\log w</tex>, также и <tex>succ, pred</tex>.

Плохие операции {{---}} которые модифицируют верхний бор. Но они не происходят слишком часто.