privateclassNode{ private Key key; // key private Value val; // associated data private Node left, right; // links to left and right subtrees privateboolean color; // color of parent link privateint size; // subtree count
// flip the colors of a node and its two children privatevoidflipColors(Node h){ // h must have opposite color of its two children // assert (h != null) && (h.left != null) && (h.right != null); // assert (!isRed(h) && isRed(h.left) && isRed(h.right)) // || (isRed(h) && !isRed(h.left) && !isRed(h.right)); h.color = !h.color; h.left.color = !h.left.color; h.right.color = !h.right.color; }
// insert the key-value pair in the subtree rooted at h private Node put(Node h, Key key, Value val) { // 如果没有找到，新键一个节点 // 新键默认为红色，即新插入节点会形成 3 节点或 4 节点 if (h == null) return new Node(key, val, RED, 1);
// 递归查找，新键插入到左子树还是右子树 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;
// fix-up any right-leaning links // 如果右子节点是红色而左子节点是黑色，则将该节点左旋转 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.size = size(h.left) + size(h.right) + 1;
public Value get(Key key){ if (key == null) thrownew IllegalArgumentException("argument is null"); return get(root, key); }
// value associated with the given key in subtree rooted at x; // null if no such key private Value get(Node x, Key key){ while (x != null) { int cmp = key.compareTo(x.key); if (cmp < 0) x = x.left; elseif (cmp > 0) x = x.right; elsereturn x.val; } returnnull; }
public K getKey(){return key;} public V getValue(){return value;} public V setValue(V value){...} publicbooleanequals(Object o){...} publicinthashCode(){...} public String toString(){...} }
/** * Returns the successor of the specified Entry, or null if no such. */ static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t){ if (t == null) returnnull; // t 的右子树不空，则 t 的后继是其右子树中最小的那个元素 elseif (t.right != null) { Entry<K,V> p = t.right; while (p.left != null) p = p.left; return p; } else { // t 的右子树为空，则 t 的后继是其第一个向左走的祖先 Entry<K,V> p = t.parent; Entry<K,V> ch = t; while (p != null && ch == p.right) { ch = p; p = p.parent; } return p; } }
/** * Returns the predecessor of the specified Entry, or null if no such. */ static <K,V> Entry<K,V> predecessor(Entry<K,V> t){ if (t == null) returnnull; elseif (t.left != null) { Entry<K,V> p = t.left; while (p.right != null) p = p.right; return p; } else { Entry<K,V> p = t.parent; Entry<K,V> ch = t; while (p != null && ch == p.left) { ch = p; p = p.parent; } return p; } }
节点的假设： 被删除的节点为 X，其替换节点（孩子节点）为 N，大部分学习资料上，在讲删除后修复时，都是将 X 节点省略掉了，直接使用 N 节点替代了 X 节点的位置。不管是修复被删节点还是修复替换节点，本文使用 R 表示被修复节点。 而修复时，被修复节点 R 的父节点为 P，兄弟节点为 S；S 的左子节点为 SL，右子节点为 SR。
// If strictly internal, copy successor's element to p and then make p // point to successor. // 如果被删节点的两个子节点不为空 if (p.left != null && p.right != null) { // 找到后继节点，并将键值对复制给被删节点 Entry<K,V> s = successor(p); p.key = s.key; p.value = s.value; // 被删节点指向后继节点；即后继节点作为新的被删节点 p = s; } // p has 2 children
// Start fixup at replacement node, if it exists. // 2. 找替换节点：替换节点为被删节点子节点 // 默认左子节点，如果左子节点为空，则替换节点为右子节点 Entry<K,V> replacement = (p.left != null ? p.left : p.right);
// Null out links so they are OK to use by fixAfterDeletion. // 被删节点三条链接置空 p.left = p.right = p.parent = null;
// Fix replacement if (p.color == BLACK) fixAfterDeletion(replacement); } elseif (p.parent == null) { // return if we are the only node. root = null; } else { // No children. Use self as phantom replacement and unlink. // 替换节点为空，则先修复再删除 if (p.color == BLACK) fixAfterDeletion(p);
