Изменения

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

270 байт убрано, 13:37, 20 июня 2018

→‎Вставка

Если высота узла нулевая, возвращаем новый красный узел.

[[File:insertNode.png|310px|thumb|upright|Вставка нового узла]]

~~'''if''' (h == '''null''')~~

~~'''return''' new Node(key, value, RED)~~

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

Если левый предок и правый предок красные, запускаем переворот цветов от текущего узла.

[[File:Split4node.png|310px|thumb|upright|Расщепление узла]]

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

~~colorFlip(h)~~

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

[[File:Enforce.png|310px|thumb|upright|Принудительное вращение]]

Если правый предок красный, вращаем текущую вершину влево.

~~'''if''' (isRed(h.right))~~ ~~h = rotateLeft(h)~~

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

[[File:Balance4node.png|310px|thumb|Балансировка]]

Если левый предок красный и левый предок левого предка красный, то вращаем текущую вершину вправо.

~~'''if''' (isRed(h.left) && isRed(h.left.left))~~ ~~h = rotateRight(h)~~

===Псевдокод===

Анонимный участник