Изменения

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

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

33 байта добавлено, 18:24, 14 мая 2018
Псевдокод
'''Node''' insert( h : '''Node''', key : '''Key''', value : '''Value'''):
//Вставка нового узла к листу дерева</span>
'''if''' h == ''null''
'''return''' '''new''' Node(key, value)
//Расщепление узла с <tex>4</tex>-я потомками</span>
'''if''' isRed(h.left) '''&&''' isRed(h.right)
colorFlip(h)
//Стандартная вставка [[Дерево поиска, наивная реализация|в дереве поиска]]</span>
'''int''' cmp = key.compareTo(h.key)
'''if''' cmp == 0
'''else'''
h.right = insert(h.right, key, value)
//Принудительное вращение влево</span>
'''if''' isRed(h.right) '''&&''' '''!'''isRed(h.left)
h = rotateLeft(h)
////Балансировка узла с <tex>4</tex>-я потомками</span>
'''if''' isRed(h.left) '''&&''' isRed(h.left.left)
h = rotateRight(h)
282
правки

Навигация