Изменения

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

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

6 байт добавлено, 01:51, 15 июня 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)
h.val = value
'''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)
'''return''' ''h''
288
правок

Навигация