Изменения

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

263 байта добавлено, 18:26, 14 мая 2018

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

'''Node''' insert( h : '''Node''', key : '''Key''', value : '''Value'''):

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

'''if''' h == ''null''

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

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

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

colorFlip(h)

//Стандартная вставка [[Дерево поиска, наивная реализация|в дереве поиска]]

'''int''' cmp = key.compareTo(h.key)

'''if''' cmp == 0

'''else'''

h.right = insert(h.right, key, value)

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

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

h = rotateLeft(h)

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

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

h = rotateRight(h)

*Использование Переворота цветов и вращений сохраняет баланс черной связи.

*После удаления необходимо исправить правые красные связи и устранить узлы с <tex>4-</tex>я потомками

//Исправление правых красных связей '''Node''' fixUp(h : '''Node'''){ '''if''' (isRed(h.right)) h = rotateLeft(h); //Вращение <tex>red-red</tex> пары

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

h = rotateRight(h); //Балансировка узла с <tex>4</tex>-я потомками

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

colorFlip(h);

'''return''' h;

}

288

правок