build/module/RBTree.js
function rbInsertFixup(tree, n) {
    // When inserting the node (at any place other than the root), we always color it red.
    // This is so that we don't violate the height invariant.
    // However, this may violate the color invariant, which we address by recursing back up the tree.
    n.flag = true;
    if (!n.p.flag) {
        throw new Error("n.p must be red.");
    }
    while (n.flag) {
        /**
         * The parent of n.
         */
        var p = n.p;
        if (n === tree.root) {
            tree.root.flag = false;
            return;
        }
        else if (p === tree.root) {
            tree.root.flag = false;
            return;
        }
        /**
         * The leader of the formation.
         */
        var lead = p.p;
        // Establish the n = red, p = red, g = black condition for a transformation.
        if (p.flag && !lead.flag) {
            if (p === lead.l) {
                var aux = lead.r;
                if (aux.flag) {
                    n = colorFlip(p, lead, aux);
                }
                else if (n === p.r) {
                    n = diamondLeftToVic(lead);
                }
                else {
                    n = echelonLeftToVic(lead);
                }
            }
            else {
                var aux = lead.l;
                if (aux.flag) {
                    n = colorFlip(p, lead, aux);
                }
                else if (n === n.p.l) {
                    n = diamondRightToVic(lead);
                }
                else {
                    n = echelonRightToVic(lead);
                }
            }
        }
        else {
            break;
        }
    }
    tree.root.flag = false;
}
function rbInsertFixup(tree, n) {
    // When inserting the node (at any place other than the root), we always color it red.
    // This is so that we don't violate the height invariant.
    // However, this may violate the color invariant, which we address by recursing back up the tree.
    n.flag = true;
    if (!n.p.flag) {
        throw new Error("n.p must be red.");
    }
    while (n.flag) {
        /**
         * The parent of n.
         */
        var p = n.p;
        if (n === tree.root) {
            tree.root.flag = false;
            return;
        }
        else if (p === tree.root) {
            tree.root.flag = false;
            return;
        }
        /**
         * The leader of the formation.
         */
        var lead = p.p;
        // Establish the n = red, p = red, g = black condition for a transformation.
        if (p.flag && !lead.flag) {
            if (p === lead.l) {
                var aux = lead.r;
                if (aux.flag) {
                    n = colorFlip(p, lead, aux);
                }
                else if (n === p.r) {
                    n = diamondLeftToVic(lead);
                }
                else {
                    n = echelonLeftToVic(lead);
                }
            }
            else {
                var aux = lead.l;
                if (aux.flag) {
                    n = colorFlip(p, lead, aux);
                }
                else if (n === n.p.l) {
                    n = diamondRightToVic(lead);
                }
                else {
                    n = echelonRightToVic(lead);
                }
            }
        }
        else {
            break;
        }
    }
    tree.root.flag = false;
}
function rbInsertFixup ( tree , n ) { // When inserting the node (at any place other than the root), we always color it red. // This is so that we don't violate the height invariant. // However, this may violate the color invariant, which we address by recursing back up the tree. n . flag = true ; if ( ! n . p . flag ) { throw new Error ( "n.p must be red." ) ; } while ( n . flag ) { /**
         * The parent of n.
         */ var p = n . p ; if ( n === tree . root ) { tree . root . flag = false ; return ; } else if ( p === tree . root ) { tree . root . flag = false ; return ; } /**
         * The leader of the formation.
         */ var lead = p . p ; // Establish the n = red, p = red, g = black condition for a transformation. if ( p . flag && ! lead . flag ) { if ( p === lead . l ) { var aux = lead . r ; if ( aux . flag ) { n = colorFlip ( p , lead , aux ) ; } else if ( n === p . r ) { n = diamondLeftToVic ( lead ) ; } else { n = echelonLeftToVic ( lead ) ; } } else { var aux = lead . l ; if ( aux . flag ) { n = colorFlip ( p , lead , aux ) ; } else if ( n === n . p . l ) { n = diamondRightToVic ( lead ) ; } else { n = echelonRightToVic ( lead ) ; } } } else { break ; } } tree . root . flag = false ; }
In this algorithm we start with the node that has been inserted and make our way up the tree.
This requires carefully maintaining parent pointers.
In this algorithm we start with the node that has been inserted and make our way up the tree . This requires carefully maintaining parent pointers .