Изменения

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

Левосторонние красно-чёрные деревья

110 байт добавлено, 18:23, 14 мая 2018
Удаление минимума
'''Node''' deleteMin(h : '''Node''')
<span style="color:#008000">//удаляем узел на нижнем уровне(h должен быть красным по инварианту)</span>
if (h.left == ''null'')
'''return''' ''null'';
<span style="color:#008000">//Если необходимо, пропушим красную ссылку вниз</span>
'''if !'''isRed(h.left) '''&& !'''isRed(h.left.left)
h = moveRedLeft(h);
<span style="color:#008000">//опускаемся на уровень ниже</span>
h.left = deleteMin(h.left);
'''return''' fixUp(h);
 
==Асимптотика==
Асимптотика методов в левосторонних красно-черных деревьях эквивалентна асимптотике [[Красно-черное дерево|левосторонних красно-черных деревьях]].
288
правок

Навигация