删除一个元素

我们看看 java 代码是怎么实现的：

public V remove(Object key) {

     // 先用二分法获取这个元素，如果为 null ，不需要继续了

     Entry p = getEntry(key);

     if (p == null)

         return null;

     V oldValue = p.value;

     deleteEntry(p);

     return oldValue;

}

private void deleteEntry(Entry p) {

     modCount++;

     size--;

     // If strictly internal, copy successor's element to p and then make p

     // point to successor.

     // 如果 p 有两个儿子，就把 p 指向它的后继者，也就是它后边的元素

     if (p.left != null && p.right != null) {

         Entry 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.

     // p 有一个儿子，外汇跟单gendan5.com或者没有儿子，获取到之后放在 replacement 中

     Entry replacement = (p.left != null ? p.left : p.right);

     // p 有儿子

     if (replacement != null) {

         // Link replacement to parent

         // 把 p 的子孙接在 p 的父级

         replacement.parent = p.parent;       

         //p 是根节点

         if (p.parent == null)

             root = replacement;

         //p 是左儿子

         else if (p == p.parent.left)

             p.parent.left  = replacement;

         // p 是右儿子

         else

             p.parent.right = replacement;

         // 把 p 的链接都删掉

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

     } else if (p.parent == null) { // return if we are the only node.

         root = null;

     } else {

         //p 没有儿子

         //  No children. Use self as phantom replacement and unlink.

         if (p.color == BLACK)

             fixAfterDeletion(p);

         // 把其父节点链接到 p 的都去掉

         if (p.parent != null) {

             if (p == p.parent.left)

                 p.parent.left = null;

             else if (p == p.parent.right)

                 p.parent.right = null;

             p.parent = null;

         }

     }

}

修正调整的方法：

private void fixAfterDeletion(Entry x) {

     while (x != root && colorOf(x) == BLACK) {

         // x 是左儿子

         if (x == leftOf(parentOf(x))) {

             // sib 是 x 的兄弟

             Entry sib = rightOf(parentOf(x));       

             // 兄弟是红色的

             if (colorOf(sib) == RED) {

                 setColor(sib, BLACK);

                 setColor(parentOf(x), RED);

                 rotateLeft(parentOf(x));

                 sib = rightOf(parentOf(x));

             }          

             // 兄弟没有孩子或者孩子是黑色的

             if (colorOf(leftOf(sib))  == BLACK &&

                 colorOf(rightOf(sib)) == BLACK) {

                 setColor(sib, RED);

                 x = parentOf(x);

             } else {

                 // 兄弟的右孩子是黑色的

                 if (colorOf(rightOf(sib)) == BLACK) {

                     setColor(leftOf(sib), BLACK);

                     setColor(sib, RED);

                     rotateRight(sib);

                     sib = rightOf(parentOf(x));

                 }

                 setColor(sib, colorOf(parentOf(x)));

                 setColor(parentOf(x), BLACK);

                 setColor(rightOf(sib), BLACK);

                 rotateLeft(parentOf(x));

                 x = root;

             }

         } else { // symmetric

             Entry sib = leftOf(parentOf(x));

             if (colorOf(sib) == RED) {

                 setColor(sib, BLACK);

                 setColor(parentOf(x), RED);

                 rotateRight(parentOf(x));

                 sib = leftOf(parentOf(x));

             }

             if (colorOf(rightOf(sib)) == BLACK &&

                 colorOf(leftOf(sib)) == BLACK) {

                 setColor(sib, RED);

                 x = parentOf(x);

             } else {

                 if (colorOf(leftOf(sib)) == BLACK) {

                     setColor(rightOf(sib), BLACK);

                     setColor(sib, RED);

                     rotateLeft(sib);

                     sib = leftOf(parentOf(x));

                 }

                 setColor(sib, colorOf(parentOf(x)));

                 setColor(parentOf(x), BLACK);

                 setColor(leftOf(sib), BLACK);

                 rotateRight(parentOf(x));

                 x = root;

             }

         }

     }

 

     setColor(x, BLACK);

}