Изменения

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

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

263 байта добавлено, 18:26, 14 мая 2018
Нет описания правки
'''Node''' insert( h : '''Node''', key : '''Key''', value : '''Value'''):
<span style="color:#008000">//Вставка нового узла к листу дерева</span>
'''if''' h == ''null''
'''return''' '''new''' Node(key, value)
<span style="color:#008000">//Расщепление узла с <tex>4</tex>-я потомками</span>
'''if''' isRed(h.left) '''&&''' isRed(h.right)
colorFlip(h)
<span style="color:#008000">//Стандартная вставка [[Дерево поиска, наивная реализация|в дереве поиска]]</span>
'''int''' cmp = key.compareTo(h.key)
'''if''' cmp == 0
'''else'''
h.right = insert(h.right, key, value)
<span style="color:#008000">//Принудительное вращение влево</span>
'''if''' isRed(h.right) '''&&''' '''!'''isRed(h.left)
h = rotateLeft(h)
<span style="color:#008000">//Балансировка узла с <tex>4</tex>-я потомками</span>
'''if''' isRed(h.left) '''&&''' isRed(h.left.left)
h = rotateRight(h)
*Использование Переворота цветов и вращений сохраняет баланс черной связи.
*После удаления необходимо исправить правые красные связи и устранить узлы с <tex>4-</tex>я потомками
<span style="color:#008000">//Исправление правых красных связей</span> '''Node''' fixUp(h : '''Node'''){ '''if''' (isRed(h.right)) h = rotateLeft(h); <span style="color:#008000">//Вращение <tex>red-red</tex> пары</span>
'''if''' (isRed(h.left) '''&&''' isRed(h.left.left))
h = rotateRight(h); <span style="color:#008000">//Балансировка узла с <tex>4</tex>-я потомками</span>
'''if''' (isRed(h.left) '''&&''' isRed(h.right))
colorFlip(h);
'''return''' h;
}
282
правки

Навигация