Изменения

As a warmup, consider the delete-the-minimum operation, where the goal is to delete the bottom node on the left spine while maintaining balance. To do so, we maintain the invariant that the current node or its left child is red. We can do so by moving to the left unless the current node is red and its left child and left grandchild are both black. In that case, we can do a color ip, which restores the invariant but may introduce successive reds on the right. In that case, we can correct the condition with two rotations and a color ip. These operations are implemented in the <tex>moveRedLeft()</tex> method on the next page. With <tex>moveRedLeft()</tex>, the recursive implementation of <tex>deleteMin()</tex> above is straightforward.

For general deletion, we also need <tex>moveRedRight()</tex>, which is similar, but simpler, and we need to rotate left-leaning red links to the right on the search path to maintain the invariant. If the node to be deleted is an internal node, we replace its key and value elds with those in the minimum node in its right subtree and then delete the minimum in the right subtree (or we could rearrange pointers to use the node instead of copying elds). The full implementation of <tex>delete()</tex> that dervies from this discussion is given on the facing page. It uses one-third to one-quarter the amount of code found in typical implementations. It has been demonstrated before [2, 11, 13] that maintaining a eld in each node containing its height can lead to code for delete that is similarly concise, but that extra space is a high price to pay in a practical implementation. With <tex>LLRB</tex> trees, we can arrange for concise code having a logarithmic performance guarantee and using no extra space.

'''void''' deleteMin()

root = deleteMin(root);

root.color = BLACK;

'''Node''' deleteMin(h : '''Node''')

if (h.left == ''null'') '''return''' ''null'';

h = moveRedLeft(h);

h.left = deleteMin(h.left);

Delete-the-minimum code for LLRB 2-3 trees

'''void''' deleteMin():

root = deleteMin(root)

root.color = BLACK

'''Node''' deleteMin( h : '''Node'''):

'''if''' h.left == ''null''

h = moveRedLeft(h)

h.left = deleteMin(h.left)

'''Node''' moveRedLeft('''Node''' : h):

colorFlip(h):

colorFlip(h)

'''return''' h

'''Node''' moveRedRight(h :'''Node''' ):

colorFlip(h)

colorFlip(h)

'''return''' h

'''void''' delete(key : '''Key'''):

root = delete(root, key)

root.color = BLACK

'''Node''' delete('''Node''' : h, '''Key''' : key):

'''if''' key.compareTo(h.key) < 0)

h.right = delete(h.right, key)

'''return''' fixUp(h)