Left-leaning Red-Black Trees

LLRB.js

// see Robert Sedgewick :: Left-leaning Red-Black Trees

const RED   = true;
const BLACK = false;

var Node = function(key, value) {
         this.key   = key;
         this.value = value;
         this.color = RED;
         this.N = 1;
         this.height = 1;
         this.left = null;
         this.right = null;
};

function minKey(node) {
      if (node.left === null) return node.key;
      else return minKey(node.left);
}

function maxKey(node) {
   if (node.right === null) return node.key;
   else return maxKey(node.right);
}

function getValue(node, key){
      if (node === null) return null;
      if (key === node.key) return node.value;
      if (key < node.key) return getValue(node.left,  key);
      else return getValue(node.right, key);
}

// -- insert 

function isRed(node) {
   if (node === null) return false;
   return (node.color === RED);
}

function colorFlip(node) {  
      node.color        = !node.color;
      node.left.color   = !node.left.color;
      node.right.color  = !node.right.color;
}

function size(node) { 
   if (node === null) return 0;
   else return node.N;
}

function height(node) { 
   if (node === null) return 0;
   else return node.height;
}

function setN(node){
   node.N = size(node.left) + size(node.right) + 1;
   if (height(node.left) > height(node.right)) node.height = height(node.left) + 1;
   else node.height = height(node.right) + 1;
   return node;
}

function rotateLeft(r) {  
      var x = r.right;
      r.right = x.left;
      x.left = setN(r);
      x.color = x.left.color;                   
      x.left.color = RED;                     
      return setN(x);
}

function rotateRight(r) {  
      var x = r.left;
      r.left = x.right;
      x.right = setN(r);
      x.color = x.right.color;                   
      x.right.color = RED;                     
      return setN(x);
}

function insert(node, key, value) { 
      if (node === null) return new Node(key, value);

      if (key === node.key) {
         node.value = value;
         return node;
      }
      else if (key < node.key) node.left = insert(node.left, key, value); 
      else node.right = insert(node.right, key, value); 

      if (isRed(node.right)) node = rotateLeft(node);
      if (isRed(node.left) && isRed(node.left.left)) node = rotateRight(node);
      if (isRed(node.left) && isRed(node.right)) colorFlip(node);

      return setN(node);
}

// --- delete

function moveRedLeft(node){  
       colorFlip(node);
       if (isRed(node.right.left))
       { 
          node.right = rotateRight(node.right);
          node = rotateLeft(node);
          colorFlip(node);
       }
      return node;
}

function fixUp(node) {
      if (isRed(node.right)) node = rotateLeft(node);
      if (isRed(node.left) && isRed(node.left.left)) node = rotateRight(node);
      if (isRed(node.left) && isRed(node.right)) colorFlip(node);
      return setN(node);
}

function deleteMin(node) { 
      if (node.left === null) return null;
      if (!isRed(node.left) && !isRed(node.left.left)) node = moveRedLeft(node);
      node.left = deleteMin(node.left);
      return fixUp(node);
}