Method deleteNode

lib/java/util/TreeMap.java:2098–2134

(Node<K, V> node)

    }

    private void deleteNode(Node<K, V> node) {
        if (node.right == null) {
            if (node.left != null) {
                attachToParent(node, node.left);
           } else {
                attachNullToParent(node);
            }
            fixNextChain(node);
        } else if(node.left == null) { // node.right != null
            attachToParent(node, node.right);
            fixNextChain(node);
        } else {
            // Here node.left!=nul && node.right!=null
            // node.next should replace node in tree
            // node.next!=null by tree logic.
            // node.next.left==null by tree logic.
            // node.next.right may be null or non-null
            Node<K, V> toMoveUp = node.next;
            fixNextChain(node);
            if(toMoveUp.right==null){
                attachNullToParent(toMoveUp);
            } else {
                attachToParent(toMoveUp, toMoveUp.right);
            }
            // Here toMoveUp is ready to replace node
            toMoveUp.left = node.left;
            if (node.left != null) {
            	node.left.parent = toMoveUp;
            }
            toMoveUp.right = node.right;
            if (node.right != null) {
            	node.right.parent = toMoveUp;
            }
            attachToParentNoFixup(node,toMoveUp);
            toMoveUp.color = node.color;
        }
    }

    private void attachToParentNoFixup(Node<K, V> toDelete, Node<K, V> toConnect) {
        // assert toConnect!=null