rbt.html

---
layout: default
---
<h1>Red Black Tree</h1>
<canvas id="canvas" width="1000" height="550"></canvas>
<script type="text/javascript">
  var	c = document.getElementById("canvas");
  var ctx = c.getContext("2d");
  var w = c.width;
  var h = c.height;

  var root;
  var MAX_NODES = 10000;
  var nodes_count = 0;

  function init() {
    root = null;
    nodes_count = 0;
  }

  function drawTree(node, ox, oy, dx, dy, px) {
    if(!node) return;

    var l = node.left ? node.left.w : 0;
    var r = node.right ? node.right.w : 0;
  

    //Current node dot
    ctx.fillStyle = "#000000";
    ctx.beginPath();
    ctx.arc(ox + l*dx, oy, 4, 0, 2*Math.PI)
    ctx.fill();

    if(px != null) {
      ctx.strokeStyle = node.red ? "#ff0000" : "#000000";
      ctx.beginPath()
      ctx.moveTo(ox + l*dx, oy);
      ctx.lineTo(ox + px*dx, oy - dy);
      ctx.stroke();
    }

    if(node.left) drawTree(node.left, ox, oy + dy , dx, dy, l);
    if(node.right) drawTree(node.right, ox + (l+1)*dx, oy + dy , dx, dy, -1);
  }

  function draw() {
    ctx.fillStyle = "#ffffff";
    ctx.fillRect(0,0,w,h);

    var size = BTSize(root);

    var ox = 10;
    var oy = 50;
    var dx = (w-20)/(size.w+1);
    var dy = (h-60)/(size.h+1);

    drawTree(root, ox, oy, dx, dy, null);

    ctx.strokeStyle = "#000000";
    ctx.strokeText("Height: " + size.h, 10, 10);
    ctx.strokeText("Nodes: " + nodes_count, 10, 20);					
    ctx.strokeText("Complete: " + (nodes_count > 0 ? (nodes_count*100/(Math.pow(2,size.h)-1)).toFixed(2) : "0") + "%", 10, 30);

  }

  function enterFrame() {
    if(nodes_count >= MAX_NODES) return;
    ++nodes_count;

    root = RBTAdd(root, Math.random()*1e10 | 0);

    draw();
  }

  init();

  setInterval(enterFrame, 100);
</script>