红黑树中的删除最小键操作看不懂(算法第四版中的)

Question

书上的文字描述是这样的：在沿着左链接向下的过程中，保证以下情况之一成立：1、如果当前节点的左子节点不是2-节点，完成；2、如果当前节点的左子节点时2-节点，而他的亲兄弟节点不是2-节点，将左子节点的兄弟节点中的一个键移动到左子节点中；3、如果当前节点的左子节点和它的亲兄弟节点都是2-节点，将左子节点，父亲节点中的最小键和左子节点最近的兄弟节点合并一个4-节点。这样的话删除后仍可以保持红黑树的状态。上面这段话我是看懂了，但是放到代码里就不知道哪里有对应上面这段话中的操作，代码如下：代码我贴了红黑树的全部API,只要看删除最小键那就好了。package unit3_3; public class RedBlackBST<Key extends Comparable<Key>, Value> {     private Node root;     private static final boolean RED = true;     private static final boolean BLACK = false;     private class Node {         Key key;         Value val;         Node left, right;         int N;         boolean color;         Node(Key key, Value val, int N, boolean color) {             this.key = key;             this.val = val;             this.N = N;             this.color = color;         }     }     private boolean isRed(Node x) {         if (x == null)             return false;         return x.color = RED;     }     // 节点左旋     private Node rotateLeft(Node h) {         Node x = h.right;         h.right = x.left;         x.left = h;         x.color = h.color;         h.color = RED;         x.N = h.N;         h.N = 1 + size(h.left) + size(h.right);         return x;     }     // 节点右旋     private Node rotateRight(Node h) {         Node x = h.left;         h.left = x.right;         x.right = h;         x.color = h.color;         x.N = h.N;         h.N = 1 + size(h.left) + size(h.right);         return x;     }     // 改变颜色     void flipColors(Node h) {         h.color = !h.color;         h.left.color = !h.left.color;         h.right.color = !h.right.color;     }     public int size() {         return size(root);     }     private int size(Node x) {         if (x == null) {             return 0;         } else             return x.N;     }     public void put(Key key, Value val) {         root = put(root, key, val);         root.color = BLACK;     }     public Node put(Node h, Key key, Value val) {         if (h == null)             return new Node(key, val, 1, RED);         int cmp = key.compareTo(h.key);         if (cmp < 0)             h.left = put(h.left, key, val);         else if (cmp > 0)             h.right = put(h.right, key, val);         else             h.val = val;         if (isRed(h.right) && !isRed(h.left))             h = rotateLeft(h);         if (isRed(h.left) && isRed(h.left.left))             h = rotateRight(h);         if (isRed(h.left) && isRed(h.right))             flipColors(h);         h.N = size(h.left) + size(h.right) + 1;         return h;     }     public boolean isEmpty() {         return size() == 0;     }     private Node balance(Node h) {         if (isRed(h.right))             h = rotateLeft(h);         if (isRed(h.right) && !isRed(h.left))             h = rotateLeft(h);         if (isRed(h.left) && isRed(h.left.left))             h = rotateRight(h);         if (isRed(h.left) && isRed(h.right))             flipColors(h);         h.N = size(h.left) + size(h.right) + 1;         return h;     }     public Value get(Key key) {         return get(root, key);     }     private Value get(Node x, Key key) {         if (x == null)             return null;         int cmp = key.compareTo(x.key);         if (cmp < 0)             return get(x.left, key);         else if (cmp > 0)             return get(x.right, key);         else             return x.val;     }     // 求最小值     public Key min() {         return min(root).key;     }     private Node min(Node x) {         if (x.left == null)             return x;         return min(x.left);     }     // 删除最小键     private Node removeRedLeft(Node h) {         flipColors(h);         if (isRed(h.right.left)) {             h.right = rotateRight(h.right);             h = rotateLeft(h);         }         return h;     }     public void deleteMin() {         if (!isRed(root.left) && !isRed(root.right))             root.color = RED;         root = deleteMin(root);         if (!isEmpty())             root.color = BLACK;     }     private Node deleteMin(Node h) {         if (h.left == null)             return null;         if (!isRed(h.left) && !isRed(h.left.left))             h = removeRedLeft(h.left);         h.left = deleteMin(h.left);         return balance(h);     }     // 删除最大键     private Node moveRedRight(Node h) {         flipColors(h);         if (!isRed(h.left.left))             h = rotateRight(h);         return h;     }     public void deleteMax() {         if (!isRed(root.left) && !isRed(root.right))             root.color = RED;         root = deleteMax(root);         if (!isEmpty())             root.color = BLACK;     }     private Node deleteMax(Node h) {         if (isRed(h.left))             h = rotateRight(h);         if (h.right == null)             return null;         if (!isRed(h.right) && !isRed(h.right.left))             h = moveRedRight(h);         h.right = deleteMax(h.right);         return balance(h);     }     // 删除任意键     public void delete(Key key) {         if (!isRed(root.left) && !isRed(root.right))             root.color = RED;         root = delete(root, key);         if (!isEmpty())             root.color = BLACK;     }     private Node delete(Node h, Key key) {         if (key.compareTo(h.key) < 0) {             if (!isRed(h.left) && !isRed(h.left.left))                 h = removeRedLeft(h);             h.left = delete(h.left, key);         } else {             if (isRed(h.left))                 h = rotateRight(h);             if (key.compareTo(h.key) == 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.right);             } else                 h.right = delete(h.right, key);         }         return balance(h);     } }

Answer 1

我看了一下删除最小键的地方，没有无法理解的地方，你具体说一下哪里不懂，或者是多少行，回复我吧