BST Insert vs AVL

// BST insertion: one random value/sec. Toggle AVL balancing with B or tap "AVL"; reset with R or tap "reset".
// Near-sorted inputs make a plain BST degenerate; AVL keeps height ~log2(n).

let nodes, root, avlOn, nextAt, allValues, mode, sortedCursor, lastReset;
let btnAVL, btnReset;

function mkNode(v) { return { v, l: null, r: null, h: 1, x: 0, y: 0, tx: 0, ty: 0, flash: 1 }; }

function reset(time) {
  nodes = []; root = null; allValues = [];
  mode = mode === "random" ? "sorted" : "random";
  sortedCursor = 1;
  nextAt = time + 0.4;
  lastReset = time;
}

function init() { avlOn = false; mode = "sorted"; reset(0); }

const ht = n => n ? n.h : 0;
const bal = n => n ? ht(n.l) - ht(n.r) : 0;
const refresh = n => { n.h = 1 + Math.max(ht(n.l), ht(n.r)); };

function rotR(y) { const x = y.l, T = x.r; x.r = y; y.l = T; refresh(y); refresh(x); return x; }
function rotL(x) { const y = x.r, T = y.l; y.l = x; x.r = T; refresh(x); refresh(y); return y; }

function insertBST(n, v) {
  if (!n) { const nn = mkNode(v); nodes.push(nn); return nn; }
  if (v < n.v) n.l = insertBST(n.l, v);
  else if (v > n.v) n.r = insertBST(n.r, v);
  else return n;
  refresh(n);
  if (avlOn) {
    const b = bal(n);
    if (b > 1 && v < n.l.v) return rotR(n);
    if (b < -1 && v > n.r.v) return rotL(n);
    if (b > 1 && v > n.l.v) { n.l = rotL(n.l); return rotR(n); }
    if (b < -1 && v < n.r.v) { n.r = rotR(n.r); return rotL(n); }
  }
  return n;
}

// On toggle-on, rebuild via balanced bisection of in-order traversal so the
// existing nodes flow into an AVL shape without losing their animated positions.
function rebuildAVL() {
  const ord = [];
  (function walk(n) { if (!n) return; walk(n.l); ord.push(n); walk(n.r); })(root);
  function build(lo, hi) {
    if (lo > hi) return null;
    const m = (lo + hi) >> 1, n = ord[m];
    n.l = build(lo, m - 1); n.r = build(m + 1, hi);
    refresh(n); n.flash = Math.max(n.flash, 0.6);
    return n;
  }
  root = build(0, ord.length - 1);
}

const treeH = n => n ? 1 + Math.max(treeH(n.l), treeH(n.r)) : 0;
const treeN = n => n ? 1 + treeN(n.l) + treeN(n.r) : 0;

function layout(W, H) {
  const h = Math.max(1, treeH(root));
  const top = 70, levelGap = (H - 100) / Math.max(h, 1);
  const leaves = [];
  (function collect(n) { if (!n) return; collect(n.l); leaves.push(n); collect(n.r); })(root);
  if (leaves.length === 1) leaves[0].tx = W / 2;
  else for (let i = 0; i < leaves.length; i++) leaves[i].tx = 30 + ((W - 60) * i) / (leaves.length - 1);
  (function setY(n, d) { if (!n) return; n.ty = top + d * levelGap; setY(n.l, d + 1); setY(n.r, d + 1); })(root, 0);
  (function setX(n) {
    if (!n) return;
    setX(n.l); setX(n.r);
    if (n.l && n.r) n.tx = (n.l.tx + n.r.tx) / 2;
    else if (n.l) n.tx = n.l.tx;
    else if (n.r) n.tx = n.r.tx;
  })(root);
}

function drawEdges(ctx, n) {
  if (!n) return;
  ctx.strokeStyle = "rgba(180,200,255,0.55)"; ctx.lineWidth = 1.5;
  if (n.l) { ctx.beginPath(); ctx.moveTo(n.x, n.y); ctx.lineTo(n.l.x, n.l.y); ctx.stroke(); drawEdges(ctx, n.l); }
  if (n.r) { ctx.beginPath(); ctx.moveTo(n.x, n.y); ctx.lineTo(n.r.x, n.r.y); ctx.stroke(); drawEdges(ctx, n.r); }
}

function drawNodes(ctx, n) {
  if (!n) return;
  drawNodes(ctx, n.l); drawNodes(ctx, n.r);
  const b = bal(n);
  const hue = Math.abs(b) > 1 ? 0 : Math.abs(b) === 1 ? 35 : 145;
  ctx.fillStyle = `hsl(${hue}, 70%, ${55 + n.flash * 25}%)`;
  ctx.beginPath(); ctx.arc(n.x, n.y, 14, 0, Math.PI * 2); ctx.fill();
  ctx.strokeStyle = "rgba(0,0,0,0.6)"; ctx.lineWidth = 1; ctx.stroke();
  ctx.fillStyle = "#0b0b12"; ctx.font = "bold 11px monospace";
  ctx.textAlign = "center"; ctx.textBaseline = "middle";
  ctx.fillText(String(n.v), n.x, n.y);
}

function layoutButtons(W) {
  const bw = 92, bh = 36, gap = 8, pad = 10;
  btnAVL = { x: W - pad - bw * 2 - gap, y: pad, w: bw, h: bh };
  btnReset = { x: W - pad - bw, y: pad, w: bw, h: bh };
}

function hit(b, x, y) { return x >= b.x && x <= b.x + b.w && y >= b.y && y <= b.y + b.h; }

function drawButton(ctx, b, label, active) {
  ctx.fillStyle = active ? "rgba(80,180,120,0.85)" : "rgba(40,44,68,0.85)";
  ctx.fillRect(b.x, b.y, b.w, b.h);
  ctx.strokeStyle = "rgba(200,210,255,0.6)"; ctx.lineWidth = 1;
  ctx.strokeRect(b.x + 0.5, b.y + 0.5, b.w - 1, b.h - 1);
  ctx.fillStyle = "#e8ecff"; ctx.font = "bold 13px monospace";
  ctx.textAlign = "center"; ctx.textBaseline = "middle";
  ctx.fillText(label, b.x + b.w / 2, b.y + b.h / 2);
}

function tick({ dt, time, ctx, width: W, height: H, input }) {
  layoutButtons(W);

  let toggleAVL = false, doReset = false;
  for (const c of input.consumeClicks()) {
    if (hit(btnAVL, c.x, c.y)) toggleAVL = true;
    else if (hit(btnReset, c.x, c.y)) doReset = true;
  }

  if (input.justPressed("b") || input.justPressed("B") || toggleAVL) {
    avlOn = !avlOn;
    if (avlOn) rebuildAVL();
  }
  if (input.justPressed("r") || input.justPressed("R") || doReset) reset(time);

  if (time >= nextAt) {
    let v;
    if (mode === "sorted") {
      v = sortedCursor + ((Math.random() < 0.15) ? (((Math.random() * 3) | 0) - 1) : 0);
      if (v < 1) v = 1;
      sortedCursor += 1;
    } else {
      v = 1 + ((Math.random() * 99) | 0);
    }
    if (!allValues.includes(v)) { root = insertBST(root, v); allValues.push(v); }
    nextAt = time + 1.0;
  }

  if (allValues.length >= 31 && time - lastReset > 3) reset(time);

  layout(W, H);
  const k = Math.min(1, dt * 6);
  for (const n of nodes) {
    n.x += (n.tx - n.x) * k;
    n.y += (n.ty - n.y) * k;
    if (n.flash > 0) n.flash = Math.max(0, n.flash - dt * 1.5);
  }

  ctx.fillStyle = "rgba(8,8,14,0.35)"; ctx.fillRect(0, 0, W, H);

  const h = treeH(root), nc = treeN(root);
  const opt = nc > 0 ? Math.ceil(Math.log2(nc + 1)) : 0;
  ctx.textAlign = "left"; ctx.textBaseline = "top";
  ctx.fillStyle = "#cfd6ff"; ctx.font = "bold 14px monospace";
  ctx.fillText(`AVL: ${avlOn ? "ON " : "OFF"}   mode: ${mode}`, 10, 8);
  ctx.font = "12px monospace"; ctx.fillStyle = "#9aa3c7";
  ctx.fillText(`n=${nc}   height=${h}   optimal=${opt}   ratio=${nc > 0 ? (h / Math.max(1, opt)).toFixed(2) : "—"}`, 10, 28);
  ctx.fillStyle = "#7a82a8";
  ctx.fillText("tap buttons or press B / R", 10, 48);

  if (root) { drawEdges(ctx, root); drawNodes(ctx, root); }
  else {
    ctx.fillStyle = "#666"; ctx.font = "12px monospace"; ctx.textAlign = "center";
    ctx.fillText("(empty — first insert in " + Math.max(0, nextAt - time).toFixed(1) + "s)", W / 2, H / 2);
  }

  drawButton(ctx, btnAVL, "AVL: " + (avlOn ? "on" : "off"), avlOn);
  drawButton(ctx, btnReset, "reset", false);
}