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