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

        Node<K,V> currentNode = insertedNode;

        makeRed(currentNode, index);

        while ((currentNode != null) && (currentNode != rootNode[index])
                && (isRed(currentNode.getParent(index), index))) {
            if (isLeftChild(getParent(currentNode, index), index)) {
                Node<K,V> y = getRightChild(getGrandParent(currentNode, index),
                                       index);

                if (isRed(y, index)) {
                    makeBlack(getParent(currentNode, index), index);
                    makeBlack(y, index);
                    makeRed(getGrandParent(currentNode, index), index);

                    currentNode = getGrandParent(currentNode, index);
                } else {
                    if (isRightChild(currentNode, index)) {
                        currentNode = getParent(currentNode, index);

                        rotateLeft(currentNode, index);
                    }

                    makeBlack(getParent(currentNode, index), index);
                    makeRed(getGrandParent(currentNode, index), index);

                    if (getGrandParent(currentNode, index) != null) {
                        rotateRight(getGrandParent(currentNode, index),
                                    index);
                    }
                }
            } else {

                // just like clause above, except swap left for right
                Node<K,V> y = getLeftChild(getGrandParent(currentNode, index),
                                      index);

                if (isRed(y, index)) {
                    makeBlack(getParent(currentNode, index), index);
                    makeBlack(y, index);
                    makeRed(getGrandParent(currentNode, index), index);

                    currentNode = getGrandParent(currentNode, index);
                } else {
                    if (isLeftChild(currentNode, index)) {
                        currentNode = getParent(currentNode, index);

                        rotateRight(currentNode, index);
                    }

                    makeBlack(getParent(currentNode, index), index);
                    makeRed(getGrandParent(currentNode, index), index);

                    if (getGrandParent(currentNode, index) != null) {
                        rotateLeft(getGrandParent(currentNode, index), index);
                    }
                }
            }
        }

        makeBlack(rootNode[index], index);
    }
private void doRedBlackInsert(final Node<K,V> insertedNode, final int index) {

        Node<K,V> currentNode = insertedNode;

        makeRed(currentNode, index);

        while ((currentNode != null) && (currentNode != rootNode[index])
                && (isRed(currentNode.getParent(index), index))) {
            if (isLeftChild(getParent(currentNode, index), index)) {
                Node<K,V> y = getRightChild(getGrandParent(currentNode, index),
                                       index);

                if (isRed(y, index)) {
                    makeBlack(getParent(currentNode, index), index);
                    makeBlack(y, index);
                    makeRed(getGrandParent(currentNode, index), index);

                    currentNode = getGrandParent(currentNode, index);
                } else {
                    if (isRightChild(currentNode, index)) {
                        currentNode = getParent(currentNode, index);

                        rotateLeft(currentNode, index);
                    }

                    makeBlack(getParent(currentNode, index), index);
                    makeRed(getGrandParent(currentNode, index), index);

                    if (getGrandParent(currentNode, index) != null) {
                        rotateRight(getGrandParent(currentNode, index),
                                    index);
                    }
                }
            } else {

                // just like clause above, except swap left for right
                Node<K,V> y = getLeftChild(getGrandParent(currentNode, index),
                                      index);

                if (isRed(y, index)) {
                    makeBlack(getParent(currentNode, index), index);
                    makeBlack(y, index);
                    makeRed(getGrandParent(currentNode, index), index);

                    currentNode = getGrandParent(currentNode, index);
                } else {
                    if (isLeftChild(currentNode, index)) {
                        currentNode = getParent(currentNode, index);

                        rotateRight(currentNode, index);
                    }

                    makeBlack(getParent(currentNode, index), index);
                    makeRed(getGrandParent(currentNode, index), index);

                    if (getGrandParent(currentNode, index) != null) {
                        rotateLeft(getGrandParent(currentNode, index), index);
                    }
                }
            }
        }

        makeBlack(rootNode[index], index);
    }
complicated red-black insert stuff. Based on Sun's TreeMap
implementation, though it's barely recognizable any more

@param insertedNode the node to be inserted
@param index KEY or VALUE