Edit in JSFiddle

//Plugins
$.fn.black = function(){ return this.addClass('black').removeClass('red'  ); };
$.fn.red   = function(){ return this.addClass('red'  ).removeClass('black'); };
$.fn.left  = function(){ return this.children('ul').children(':first'); };
$.fn.right = function(){ return this.children('ul').children(':last' ); };

$("#insert").click(insert);

function insert(){
var key = 2893, value = "Stargazer",
    root = $("#tree").children('.black:first');

//Find insert node
var node = root.left().right().left();

//Add new node
    node.red().data({'key': key})
        .append($('<span class="value"></span>').append(value))
        .append($('<ul><li class="black"></li><li class="black"></li></ul>'));

//Find Ancestors
var parent = node.closest('ul').closest('li'),
    grandparent = parent.closest('ul').closest('li');

//Rotate
    parent.left().replaceWith(node.right());
    grandparent.right().replaceWith(node.left());
    grandparent.replaceWith(node);

    node.children('ul').prepend(grandparent);
    node.children('ul').append(parent);

//Recolor    
    node.black();
    grandparent.red();
    parent.red();
}