src/main/java/com/workplacesystems/utilsj/collections/TransactionalBidiTreeMap.java
private void doRedBlackDeleteFixup(final Node<K,V> replacementNode,
                                       final int index) {

        Node<K,V> currentNode = replacementNode;

        while ((currentNode != rootNode[index])
                && (isBlack(currentNode, index))) {
            if (isLeftChild(currentNode, index)) {
                Node<K,V> siblingNode =
                    getRightChild(getParent(currentNode, index), index);

                if (isRed(siblingNode, index)) {
                    makeBlack(siblingNode, index);
                    makeRed(getParent(currentNode, index), index);
                    rotateLeft(getParent(currentNode, index), index);

                    siblingNode = getRightChild(getParent(currentNode, index), index);
                }

                if (isBlack(getLeftChild(siblingNode, index), index)
                        && isBlack(getRightChild(siblingNode, index),
                                   index)) {
                    makeRed(siblingNode, index);

                    currentNode = getParent(currentNode, index);
                } else {
                    if (isBlack(getRightChild(siblingNode, index), index)) {
                        makeBlack(getLeftChild(siblingNode, index), index);
                        makeRed(siblingNode, index);
                        rotateRight(siblingNode, index);

                        siblingNode =
                            getRightChild(getParent(currentNode, index), index);
                    }

                    copyColor(getParent(currentNode, index), siblingNode,
                              index);
                    makeBlack(getParent(currentNode, index), index);
                    makeBlack(getRightChild(siblingNode, index), index);
                    rotateLeft(getParent(currentNode, index), index);

                    currentNode = rootNode[index];
                }
            } else {
                Node<K,V> siblingNode = getLeftChild(getParent(currentNode, index), index);

                if (isRed(siblingNode, index)) {
                    makeBlack(siblingNode, index);
                    makeRed(getParent(currentNode, index), index);
                    rotateRight(getParent(currentNode, index), index);

                    siblingNode = getLeftChild(getParent(currentNode, index), index);
                }

                if (isBlack(getRightChild(siblingNode, index), index)
                        && isBlack(getLeftChild(siblingNode, index), index)) {
                    makeRed(siblingNode, index);

                    currentNode = getParent(currentNode, index);
                } else {
                    if (isBlack(getLeftChild(siblingNode, index), index)) {
                        makeBlack(getRightChild(siblingNode, index), index);
                        makeRed(siblingNode, index);
                        rotateLeft(siblingNode, index);

                        siblingNode =
                            getLeftChild(getParent(currentNode, index), index);
                    }

                    copyColor(getParent(currentNode, index), siblingNode,
                              index);
                    makeBlack(getParent(currentNode, index), index);
                    makeBlack(getLeftChild(siblingNode, index), index);
                    rotateRight(getParent(currentNode, index), index);

                    currentNode = rootNode[index];
                }
            }
        }

        makeBlack(currentNode, index);
    }
private void doRedBlackDeleteFixup(final Node<K,V> replacementNode,
                                       final int index) {

        Node<K,V> currentNode = replacementNode;

        while ((currentNode != rootNode[index])
                && (isBlack(currentNode, index))) {
            if (isLeftChild(currentNode, index)) {
                Node<K,V> siblingNode =
                    getRightChild(getParent(currentNode, index), index);

                if (isRed(siblingNode, index)) {
                    makeBlack(siblingNode, index);
                    makeRed(getParent(currentNode, index), index);
                    rotateLeft(getParent(currentNode, index), index);

                    siblingNode = getRightChild(getParent(currentNode, index), index);
                }

                if (isBlack(getLeftChild(siblingNode, index), index)
                        && isBlack(getRightChild(siblingNode, index),
                                   index)) {
                    makeRed(siblingNode, index);

                    currentNode = getParent(currentNode, index);
                } else {
                    if (isBlack(getRightChild(siblingNode, index), index)) {
                        makeBlack(getLeftChild(siblingNode, index), index);
                        makeRed(siblingNode, index);
                        rotateRight(siblingNode, index);

                        siblingNode =
                            getRightChild(getParent(currentNode, index), index);
                    }

                    copyColor(getParent(currentNode, index), siblingNode,
                              index);
                    makeBlack(getParent(currentNode, index), index);
                    makeBlack(getRightChild(siblingNode, index), index);
                    rotateLeft(getParent(currentNode, index), index);

                    currentNode = rootNode[index];
                }
            } else {
                Node<K,V> siblingNode = getLeftChild(getParent(currentNode, index), index);

                if (isRed(siblingNode, index)) {
                    makeBlack(siblingNode, index);
                    makeRed(getParent(currentNode, index), index);
                    rotateRight(getParent(currentNode, index), index);

                    siblingNode = getLeftChild(getParent(currentNode, index), index);
                }

                if (isBlack(getRightChild(siblingNode, index), index)
                        && isBlack(getLeftChild(siblingNode, index), index)) {
                    makeRed(siblingNode, index);

                    currentNode = getParent(currentNode, index);
                } else {
                    if (isBlack(getLeftChild(siblingNode, index), index)) {
                        makeBlack(getRightChild(siblingNode, index), index);
                        makeRed(siblingNode, index);
                        rotateLeft(siblingNode, index);

                        siblingNode =
                            getLeftChild(getParent(currentNode, index), index);
                    }

                    copyColor(getParent(currentNode, index), siblingNode,
                              index);
                    makeBlack(getParent(currentNode, index), index);
                    makeBlack(getLeftChild(siblingNode, index), index);
                    rotateRight(getParent(currentNode, index), index);

                    currentNode = rootNode[index];
                }
            }
        }

        makeBlack(currentNode, index);
    }
private void doRedBlackDeleteFixup ( final Node < K , V > replacementNode , final int index ) { Node < K , V > currentNode = replacementNode ; while ( ( currentNode != rootNode [ index ] ) && ( isBlack ( currentNode , index ) ) ) { if ( isLeftChild ( currentNode , index ) ) { Node < K , V > siblingNode = getRightChild ( getParent ( currentNode , index ) , index ) ; if ( isRed ( siblingNode , index ) ) { makeBlack ( siblingNode , index ) ; makeRed ( getParent ( currentNode , index ) , index ) ; rotateLeft ( getParent ( currentNode , index ) , index ) ; siblingNode = getRightChild ( getParent ( currentNode , index ) , index ) ; } if ( isBlack ( getLeftChild ( siblingNode , index ) , index ) && isBlack ( getRightChild ( siblingNode , index ) , index ) ) { makeRed ( siblingNode , index ) ; currentNode = getParent ( currentNode , index ) ; } else { if ( isBlack ( getRightChild ( siblingNode , index ) , index ) ) { makeBlack ( getLeftChild ( siblingNode , index ) , index ) ; makeRed ( siblingNode , index ) ; rotateRight ( siblingNode , index ) ; siblingNode = getRightChild ( getParent ( currentNode , index ) , index ) ; } copyColor ( getParent ( currentNode , index ) , siblingNode , index ) ; makeBlack ( getParent ( currentNode , index ) , index ) ; makeBlack ( getRightChild ( siblingNode , index ) , index ) ; rotateLeft ( getParent ( currentNode , index ) , index ) ; currentNode = rootNode [ index ] ; } } else { Node < K , V > siblingNode = getLeftChild ( getParent ( currentNode , index ) , index ) ; if ( isRed ( siblingNode , index ) ) { makeBlack ( siblingNode , index ) ; makeRed ( getParent ( currentNode , index ) , index ) ; rotateRight ( getParent ( currentNode , index ) , index ) ; siblingNode = getLeftChild ( getParent ( currentNode , index ) , index ) ; } if ( isBlack ( getRightChild ( siblingNode , index ) , index ) && isBlack ( getLeftChild ( siblingNode , index ) , index ) ) { makeRed ( siblingNode , index ) ; currentNode = getParent ( currentNode , index ) ; } else { if ( isBlack ( getLeftChild ( siblingNode , index ) , index ) ) { makeBlack ( getRightChild ( siblingNode , index ) , index ) ; makeRed ( siblingNode , index ) ; rotateLeft ( siblingNode , index ) ; siblingNode = getLeftChild ( getParent ( currentNode , index ) , index ) ; } copyColor ( getParent ( currentNode , index ) , siblingNode , index ) ; makeBlack ( getParent ( currentNode , index ) , index ) ; makeBlack ( getLeftChild ( siblingNode , index ) , index ) ; rotateRight ( getParent ( currentNode , index ) , index ) ; currentNode = rootNode [ index ] ; } } } makeBlack ( currentNode , index ) ; }
complicated red-black delete stuff. Based on Sun's TreeMap
implementation, though it's barely recognizable any more. This
rebalances the tree (somewhat, as red-black trees are not
perfectly balanced -- perfect balancing takes longer)

@param replacementNode the node being replaced
@param index KEY or VALUE
complicated red - black delete stuff . Based on Sun s TreeMap implementation though it s barely recognizable any more . This rebalances the tree ( somewhat as red - black trees are not perfectly balanced -- perfect balancing takes longer )