书上的文字描述是这样的：
在沿着左链接向下的过程中，保证以下情况之一成立：
1、如果当前节点的左子节点不是2-节点，完成；
2、如果当前节点的左子节点时2-节点，而他的亲兄弟节点不是2-节点，将左子节点的兄弟节点中的一个键移动到左子节点中；
3、如果当前节点的左子节点和它的亲兄弟节点都是2-节点，将左子节点，父亲节点中的最小键和左子节点最近的兄弟节点合并一个4-节点。
这样的话删除后仍可以保持红黑树的状态。上面这段话我是看懂了，但是放到代码里就不知道哪里有对应上面这段话中的操作，代码如下：
代码我贴了红黑树的全部API,只要看删除最小键那就好了。
package unit3_3;public class RedBlackBST { 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); }} |
天盟APP下载
