Изменения

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

23 байта добавлено, 02:20, 8 декабря 2017

→‎Методы

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

'''if''' h == null

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

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

colorFlip(h)

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

'''if''' cmp == 0

h.val = value

'''else'''

'''if''' cmp < 0

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

'''else'''

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

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

h = rotateLeft(h)

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

h = rotateRight(h)

'''return''' ''h''

</code>

while (x != null)

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

'''if ''' cmp == 0) '''return''' x.val '''else''' '''if ''' cmp < 0) x = x.left '''else ''' '''if ''' cmp > 0) x = x.right '''return''' null

</code>

==Удаление==

<code>

288

правок