sub _insert {
    my ($node, $cmp, $key, $val) = @_;

    my ($found, @stack);
    while ($node) {
        _colorFlip($node) if _isRed($node->[RIGHT]) && _isRed($node->[LEFT]); 
        push @stack, [$node, undef];

        my $result = $cmp->($key, $node->[KEY]);

        # Dup key, replace value
        if ($result == EQUAL) {
            ($found, $node->[VALUE]) = (1, $val);
            $node = undef;
        }

        # Descend right
        elsif ($result == MORE) {
            $stack[LAST][DIR] = RIGHT;
            $node = $node->[RIGHT];
        }

        # Descend right
        else {
            $stack[LAST][DIR] = LEFT;
            $node = $node->[LEFT];
        }
    }
    push @stack, [[RED, $key, $val, undef, undef], undef] if ! $found;

    my $assign;
    while (@stack) {
        my $unwind = pop @stack;
        my ($item, $dir) = @{$unwind}[NODE, DIR];
        if ($assign || $found) {
            $item->[$dir] = $assign->[NODE] if $assign;
            $item = _rotateLeft($item)  if _isRed($item->[RIGHT]) && ! _isRed($item->[LEFT]);
            $item = _rotateRight($item) if _isRed($item->[LEFT])  &&   _isRed($item->[LEFT][LEFT]);
        }
        $assign = [$item, undef];
    }
    return $assign->[NODE];
}