Изменения

{{ Определение

'''Node '''rotateRight(h : '''Node '''):

'''return ''' x

root = insert(root, key, value); root.color = BLACK;

'''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);

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);

public '''Value ''' search(key : '''Key key'''): '''Node ''' x = root;

'''int ''' cmp = key.compareTo(x.key); if (cmp == 0) '''return ''' x.val;

if (cmp < 0) x = x.left;

if (cmp > 0) x = x.right; '''return ''' null;

void deleteMin(): root = deleteMin(root); root.color = BLACK;</code><code> '''Node''' deleteMin( h : '''Node'''): '''if''' h.left == null '''return''' null '''if''' !isRed(h.left) '''&&''' !isRed(h.left.left) h = moveRedLeft(h) h.left = deleteMin(h.left) '''return''' fixUp(h)

'''Node deleteMin''' moveRedLeft( '''Node''' h ): Node colorFlip(h): '''if ''' isRed(h.right.left ) h.right =rotateRight(h.right) h = rotateLeft(h) colorFlip(h) '''return''' h </code>  <code> '''Node’’’ moveRedRight(h :'''Node''' ): colorFlip(h) '''if''' isRed(h.left.left)) h = nullrotateRight(h) colorFlip(h) '''return null;''' h </code><code> '''void''' delete(key : '''Key'''): root = delete(root, key) root.color = BLACK </code> <code> '''Node''' delete('''Node''' : h, '''Key''' : key): '''if ''' key.compareTo(h.key) < 0) '''if''' !isRed(h.left) '''&& ''' !isRed(h.left.left) h = moveRedLeft(h) h.left = delete(h.left, key) '''else''' '''if''' isRed(h.left) h = rotateRight(h) '''if''' key.compareTo(h .key) = moveRedLeft= 0 '''&&''' (h.right == null); '''return''' null '''if''' !isRed(h.right) && !isRed(h.right.left ) h = moveRedRight(h) '''if''' key.compareTo(h.key) == 0 h.val = get(h.right, min(h.right).key) h.key = min(h.right).key h.right = deleteMin(h.leftright) '''else''' h.right = delete(h.right, key); '''return ''' fixUp(h);