Изменения

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

6 байт добавлено, 01:32, 14 марта 2018

Нет описания правки

==Вставка==

Вставка в LLRB базируется на <tex>4<\/tex> протых операциях:

*Вставка нового узла к листу дерева:

if (h == null)

return new Node(key, value, RED);

*Расщепление узла с <tex>4<\/tex>-я потомками:

if (isRed(h.left) && isRed(h.right))

colorFlip(h);

*Принудительное вращение влево:

if (isRed(h.right))

h = rotateLeft(h);

*Балансировка узла с <tex>4<\tex>-я потомками:

if (isRed(h.left) && isRed(h.left.left))

h = rotateRight(h);

288

правок