删除一个元素

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

public V remove(Object key) {

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

      Entry<K,V> p = getEntry(key);

      if (p == null)

          return null;

      V oldValue = p.value;

      deleteEntry(p);

      return oldValue;

}

private void deleteEntry(Entry<K,V> 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<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.

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

      Entry<K,V> 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 {