이진 탐색 트리

body{display:block} .stage{position:absolute;inset:0;display:flex;flex-direction:column;padding:clamp(9px,3vmin,20px);gap:5px}
.top{display:flex;align-items:center;justify-content:space-between;gap:8px;font-size:clamp(11px,2.7vmin,14px);font-weight:700;white-space:nowrap}
.top span:last-child{color:var(--muted);font-weight:500}canvas{width:100%;height:0;flex:1 1 0;min-height:0}
.controls{display:none;align-items:center;gap:9px;font-size:12px;color:var(--muted)}
button{border:1px solid var(--line);background:var(--surface);color:var(--fg);border-radius:7px;padding:5px 10px;cursor:pointer}
input{width:100px;accent-color:var(--accent)}
@media(min-width:600px){.controls{display:flex}}

const ALGORITHM_KIND = "binary-search-tree";

const kind = ALGORITHM_KIND;
const root = document.createElement('div'); root.className = 'stage';
root.innerHTML = '<div class="top"><span id="state"></span><span id="count"></span></div><canvas></canvas><div class="controls"><button id="reset">다시 시작</button><button id="step">한 단계</button><label>속도 <input id="speed" type="range" min="1" max="5" value="3"></label></div>';
document.body.append(root);
const canvas = root.querySelector('canvas'), ctx = canvas.getContext('2d');
const title = root.querySelector('#state'), count = root.querySelector('#count');
const style = getComputedStyle(document.documentElement);
const colors = Object.fromEntries(['bg','fg','muted','line','accent','accent-2','accent-3','surface'].map(k => [k, style.getPropertyValue('--' + k).trim()]));
const palette = {base:colors.accent, active:colors['accent-2'], done:colors['accent-3'], text:colors.fg, faint:colors.muted, line:colors.line, surface:colors.surface};
let generation = 0, states = [], index = 0, elapsed = 0;
function rng(seed){return function(){seed |= 0;seed = seed + 0x6D2B79F5 | 0;let t = Math.imul(seed ^ seed >>> 15, 1 | seed);t = t + Math.imul(t ^ t >>> 7, 61 | t) ^ t;return ((t ^ t >>> 14) >>> 0) / 4294967296}}
function shuffled(){const a=[3,8,2,7,4,9,1,6,5];const random=rng(42+generation*23);for(let i=a.length-1;i>0;i--){const j=Math.floor(random()*(i+1));[a[i],a[j]]=[a[j],a[i]]}return a}
function push(values, active=[], done=[], note='', extra={}){states.push({values:[...values],active:[...active],done:[...done],note,extra})}
function makeStates(){
  states=[];
  const a=shuffled(), n=a.length;
  push(a,[],[],'시작');
  if(kind==='big-o') {states=[];for(let size=1;size<=12;size++)push([],[],[],'입력 크기 n = '+size,{size});return}
  if(kind==='bubble-sort'){for(let end=n-1;end>0;end--){for(let j=0;j<end;j++){push(a,[j,j+1],Array.from({length:n-end-1},(_,k)=>n-1-k),'이웃한 두 값 비교');if(a[j]>a[j+1]){[a[j],a[j+1]]=[a[j+1],a[j]];push(a,[j,j+1],[],'순서가 반대라 교환')}}push(a,[],Array.from({length:n-end},(_,k)=>n-1-k),'가장 큰 값 확정')}push(a,[],a.map((_,i)=>i),'정렬 완료')}
  if(kind==='selection-sort'){for(let i=0;i<n;i++){let min=i;for(let j=i+1;j<n;j++){push(a,[min,j],Array.from({length:i},(_,k)=>k),'최솟값 탐색');if(a[j]<a[min])min=j}[a[i],a[min]]=[a[min],a[i]];push(a,[i,min],Array.from({length:i+1},(_,k)=>k),'최솟값을 앞에 배치')}}
  if(kind==='insertion-sort'){for(let i=1;i<n;i++){let j=i;while(j>0&&a[j-1]>a[j]){push(a,[j-1,j],[],'앞의 값과 비교');[a[j-1],a[j]]=[a[j],a[j-1]];push(a,[j-1,j],Array.from({length:i+1},(_,k)=>k),'왼쪽으로 삽입');j--}push(a,[],Array.from({length:i+1},(_,k)=>k),'왼쪽 부분 정렬됨')}}
  if(kind==='merge-sort'){function merge(lo,hi){if(hi-lo<=1)return;const mid=(lo+hi)>>1;push(a,Array.from({length:hi-lo},(_,i)=>lo+i),[],'구간 분할: '+lo+'–'+(hi-1));merge(lo,mid);merge(mid,hi);const sorted=[...a.slice(lo,mid)], right=[...a.slice(mid,hi)];let l=0,r=0;for(let k=lo;k<hi;k++){a[k]=r>=right.length||(l<sorted.length&&sorted[l]<=right[r])?sorted[l++]:right[r++];push(a,[k],Array.from({length:k-lo+1},(_,i)=>lo+i),'작은 값부터 병합')}}merge(0,n);push(a,[],a.map((_,i)=>i),'정렬 완료')}
  if(kind==='quick-sort'){function quick(lo,hi){if(lo>=hi)return;const pivot=a[hi];let i=lo;push(a,[hi],[],'피벗 '+pivot+' 선택');for(let j=lo;j<hi;j++){push(a,[j,hi],[],'피벗과 비교');if(a[j]<pivot){[a[i],a[j]]=[a[j],a[i]];push(a,[i,j],[],'작은 값을 왼쪽으로');i++}}[a[i],a[hi]]=[a[hi],a[i]];push(a,[i],[i],'피벗 자리 확정');quick(lo,i-1);quick(i+1,hi)}quick(0,n-1);push(a,[],a.map((_,i)=>i),'정렬 완료')}
  if(kind==='heap-sort'){function sift(size,i){while(2*i+1<size){let child=2*i+1;if(child+1<size&&a[child+1]>a[child])child++;push(a,[i,child],[],'부모와 큰 자식 비교');if(a[i]>=a[child])break;[a[i],a[child]]=[a[child],a[i]];push(a,[i,child],[],'큰 값을 위로');i=child}}for(let i=(n>>1)-1;i>=0;i--)sift(n,i);for(let end=n-1;end>0;end--){[a[0],a[end]]=[a[end],a[0]];push(a,[0,end],Array.from({length:n-end},(_,k)=>end+k),'최댓값을 끝으로');sift(end,0)}push(a,[],a.map((_,i)=>i),'정렬 완료')}
  if(kind==='counting-sort'){const freq=Array(10).fill(0);for(let i=0;i<n;i++){freq[a[i]]++;push(freq,[a[i]],[],'값 '+a[i]+'의 개수 세기',{histogram:true})}let k=0;for(let value=1;value<=9;value++)while(freq[value]-- > 0){a[k++]=value;push(a,[k-1],Array.from({length:k},(_,i)=>i),'개수대로 출력')}push(a,[],a.map((_,i)=>i),'정렬 완료')}
  if(kind==='binary-search'){states=[];const b=[1,2,3,4,5,6,7,8,9];let lo=0,hi=8,target=7;push(b,[],[],'정렬된 배열에서 7 찾기');while(lo<=hi){let mid=(lo+hi)>>1;push(b,[mid],[],'가운데 '+b[mid]+'와 비교',{range:[lo,hi]});if(b[mid]===target){push(b,[mid],[mid],'7 찾음');break}if(b[mid]<target)lo=mid+1;else hi=mid-1;push(b,[],[],'절반 제외',{range:[lo,hi]})}}
  if(kind==='two-pointers'){states=[];const b=[1,2,3,4,5,6,7,8,9];let l=0,r=8;push(b,[l,r],[],'합계 10 찾기');while(l<r){push(b,[l,r],[],'합 '+(b[l]+b[r])+' 비교');if(b[l]+b[r]===10){push(b,[l,r],[l,r],'합계 10인 쌍');l++;r--}else if(b[l]+b[r]<10)l++;else r--}}
  if(kind==='sliding-window'){states=[];const b=[2,1,4,3,5,2,6,1,4];let sum=b.slice(0,3).reduce((x,y)=>x+y,0);push(b,[0,1,2],[],'크기 3, 합 '+sum);for(let start=1;start<=b.length-3;start++){sum+=b[start+2]-b[start-1];push(b,[start,start+1,start+2],[],'왼쪽 제거 · 오른쪽 추가 → 합 '+sum)}}
  if(kind==='stack'||kind==='queue'){states=[];const b=[];const acts=kind==='stack'?[['push',3],['push',8],['push',2],['pop'],['push',7],['pop'],['pop']]:[['enqueue',3],['enqueue',8],['enqueue',2],['dequeue'],['enqueue',7],['dequeue'],['dequeue']];push(b,[],[],'빈 '+(kind==='stack'?'스택':'큐'));for(const [op,value] of acts){let changed;if(op==='push'||op==='enqueue'){b.push(value);changed=b.length-1}else{changed=kind==='stack'?b.length-1:0;b.splice(changed,1)}push(b,[Math.max(0,Math.min(changed,b.length-1))],[],op+(value?' '+value:''),{operation:op})}}
  if(kind==='linked-list'){states=[];const nodes=[3,8,2,7].map(value=>({value,next:null}));for(let i=0;i<nodes.length-1;i++)nodes[i].next=nodes[i+1];const head=nodes[0];function snapshot(){const result=[];for(let node=head;node;node=node.next)result.push(node.value);return result}push(snapshot(),[],[],'노드와 다음 포인터');let node=head,i=0;while(node){push(snapshot(),[i++],[],'처음부터 '+node.value+' 방문');node=node.next}nodes[1].next={value:5,next:nodes[1].next};push(snapshot(),[2],[],'포인터 연결을 바꿔 5 삽입');node=head;i=0;while(node){push(snapshot(),[i++],[],'다시 순회: '+node.value);node=node.next}}
  if(kind==='hash-table'){states=[];const names=['A','F','B','G','C','H'];const buckets=Array.from({length:5},()=>[]);push([],[],[],'5개 버킷',{buckets:buckets.map(x=>[...x])});for(const name of names){const bucket=(name.charCodeAt(0)-65)%5;buckets[bucket].push(name);push([], [bucket],[],'키 '+name+' → 버킷 '+bucket,{buckets:buckets.map(x=>[...x])})}}
  if(kind==='binary-search-tree'){states=[];const order=[5,3,8,1,4,7,9],tree=[];for(const value of order){let i=0;while(tree[i]!==undefined)i=value<tree[i]?2*i+1:2*i+2;tree[i]=value;push(tree,[i],[],'값 '+value+' 삽입',{tree:true})}let i=0;while(tree[i]!==4){push(tree,[i],[],'4와 '+tree[i]+' 비교',{tree:true});i=4<tree[i]?2*i+1:2*i+2}push(tree,[i],[i],'값 4 찾음',{tree:true})}
  if(kind==='heap-priority-queue'){states=[];const h=[];function insert(x){h.push(x);let i=h.length-1;push(h,[i],[],'우선순위 '+x+' 추가');while(i>0){let p=(i-1)>>1;if(h[p]>=h[i])break;[h[i],h[p]]=[h[p],h[i]];i=p;push(h,[i],[],'큰 값을 부모로')}}for(const x of [3,8,2,7,5])insert(x);for(let t=0;t<2;t++){const max=h[0];h[0]=h.pop();push(h,[0],[],'최댓값 '+max+' 꺼냄');let i=0;while(2*i+1<h.length){let c=2*i+1;if(c+1<h.length&&h[c+1]>h[c])c++;if(h[i]>=h[c])break;[h[i],h[c]]=[h[c],h[i]];i=c;push(h,[i],[],'힙 복구')}}}
  if(kind==='recursion'){states=[];for(let d=1;d<=5;d++)push(Array.from({length:d},(_,i)=>5-i),[d-1],[],'factorial('+ (6-d) +') 호출',{call:true});let result=1;for(let d=5;d>=1;d--){result*=6-d;push(Array.from({length:d-1},(_,i)=>5-i),[],[],'반환값 '+result,{call:true})}}
  if(kind==='divide-and-conquer'){states=[];const b=[8,3,7,2,6,1,5,4];function visit(lo,hi){push(b,Array.from({length:hi-lo},(_,i)=>lo+i),[],'범위 '+lo+'–'+(hi-1)+' 분할',{range:[lo,hi-1]});if(hi-lo>1){const mid=(lo+hi)>>1;visit(lo,mid);visit(mid,hi);const left=b.slice(lo,mid),right=b.slice(mid,hi);let l=0,r=0;for(let k=lo;k<hi;k++)b[k]=r>=right.length||(l<left.length&&left[l]<=right[r])?left[l++]:right[r++];push(b,Array.from({length:hi-lo},(_,i)=>lo+i),[],'작은 결과를 병합')}}visit(0,b.length);push(b,[],b.map((_,i)=>i),'전체 결과')}
  if(kind==='prefix-sum'){states=[];const b=[2,1,4,3,5,2,6,1,4], prefix=[0];push(b,[],[],'원본 배열',{prefix:[0]});for(let i=0;i<b.length;i++){prefix.push(prefix[i]+b[i]);push(b,[i],Array.from({length:i+1},(_,j)=>j),'누적합 P['+(i+1)+'] = '+prefix[i+1],{prefix:[...prefix]})}push(b,[2,3,4,5],[],'구간 2–5 합 = P[6] − P[2] = '+(prefix[6]-prefix[2]),{prefix:[...prefix]})}
}
function resize(){const dpr=Math.min(devicePixelRatio||1,2);const w=canvas.clientWidth,h=canvas.clientHeight;canvas.width=Math.max(1,Math.round(w*dpr));canvas.height=Math.max(1,Math.round(h*dpr));ctx.setTransform(dpr,0,0,dpr,0,0);draw()}
function text(value,x,y,size=12,color=palette.text,align='center'){ctx.fillStyle=color;ctx.font='600 '+size+'px system-ui,sans-serif';ctx.textAlign=align;ctx.fillText(String(value),x,y)}
function round(x,y,w,h,r=7){ctx.beginPath();ctx.roundRect(x,y,w,h,r)}
function draw(){if(!states.length)return;const s=states[index], w=canvas.clientWidth,h=canvas.clientHeight;ctx.clearRect(0,0,canvas.width,canvas.height);title.textContent=s.note;count.textContent=(index+1)+' / '+states.length;const values=s.values;
 if(kind==='big-o'){const pad=26,gw=w-pad*2,gh=h-48;ctx.strokeStyle=palette.line;ctx.beginPath();ctx.moveTo(pad,12);ctx.lineTo(pad,h-27);ctx.lineTo(w-pad,h-27);ctx.stroke();const curves=[['O(1)',x=>1,palette.done],['O(log n)',x=>Math.log2(x+1)*5,palette.base],['O(n)',x=>x*3,palette.active],['O(n²)',x=>x*x*.65,palette.faint]];for(const [label,fn,color] of curves){ctx.strokeStyle=color;ctx.lineWidth=2;ctx.beginPath();for(let x=1;x<=s.extra.size;x++){const px=pad+(x/12)*gw,py=h-27-Math.min(gh,fn(x)/100*gh);if(x===1)ctx.moveTo(px,py);else ctx.lineTo(px,py)}ctx.stroke()}curves.forEach(([label,_,color],i)=>text(label,pad+38+i*(gw/4),h-6,10,color));return}
 if(kind==='hash-table'){const buckets=s.extra.buckets;const gap=w/5;for(let i=0;i<5;i++){const x=i*gap+gap*.08;round(x,h*.18,gap*.84,h*.64);ctx.fillStyle=s.active.includes(i)?palette.active:palette.surface;ctx.fill();ctx.strokeStyle=palette.line;ctx.stroke();text(i,x+gap*.42,h*.14,12,palette.faint);buckets[i].forEach((v,j)=>text(v,x+gap*.42,h*.3+j*20,12,s.active.includes(i)?colors.bg:palette.text))}return}
 if(kind==='binary-search-tree'||kind==='heap-priority-queue'){const nodes=values;const positions=[];for(let i=0;i<nodes.length;i++){const depth=Math.floor(Math.log2(i+1)),first=2**depth-1,slot=i-first;positions.push([(slot+1)*w/(2**depth+1),(depth+1)*h/4])}ctx.strokeStyle=palette.line;for(let i=1;i<nodes.length;i++){const p=(i-1)>>1;ctx.beginPath();ctx.moveTo(...positions[p]);ctx.lineTo(...positions[i]);ctx.stroke()}nodes.forEach((v,i)=>{const [x,y]=positions[i];ctx.beginPath();ctx.arc(x,y,Math.min(17,w/22),0,Math.PI*2);ctx.fillStyle=s.active.includes(i)?palette.active:palette.base;ctx.fill();text(v,x,y+4,12,colors.bg)});return}
 if(kind==='stack'||kind==='queue'||kind==='linked-list'||kind==='recursion'){const gap=w/Math.max(6,values.length+1);values.forEach((v,i)=>{const x=(i+1)*gap-gap*.34,y=h*.3;round(x,y,gap*.68,h*.33);ctx.fillStyle=s.active.includes(i)?palette.active:palette.base;ctx.fill();text(v,x+gap*.34,y+h*.19,14,colors.bg);if(kind==='linked-list'&&i<values.length-1)text('→',x+gap*.84,y+h*.2,16,palette.faint)});if(kind==='stack')text('위쪽에서 넣고 꺼냄',w/2,h*.83,11,palette.faint);if(kind==='queue')text('앞에서 꺼내고 뒤에 넣음',w/2,h*.83,11,palette.faint);if(kind==='recursion')text('호출 스택의 깊이',w/2,h*.83,11,palette.faint);return}
 const n=values.length,gap=w/(n+1),barWidth=Math.min(gap*.74,44),max=Math.max(9,...values);for(let i=0;i<n;i++){const x=(i+1)*gap-barWidth/2,barH=Math.max(7,values[i]/max*(h-42));const active=s.active.includes(i),done=s.done.includes(i);const outOfRange=s.extra.range&&(i<s.extra.range[0]||i>s.extra.range[1]);round(x,h-23-barH,barWidth,barH,Math.min(6,barWidth/4));ctx.fillStyle=outOfRange?palette.line:active?palette.active:done?palette.done:palette.base;ctx.fill();text(values[i],x+barWidth/2,h-7,Math.min(12,Math.max(9,gap*.3)),palette.text)}
 if(s.extra.prefix){const p=s.extra.prefix;text('P: '+p.join('  '),w/2,14,Math.min(12,w/30),palette.faint)}
}
function advance(){index=(index+1)%states.length;draw()}
function startIndex(){return kind==='big-o'?5:kind==='heap-priority-queue'?2:0}
function reset(){generation++;makeStates();index=startIndex();draw()}
root.querySelector('#reset').addEventListener('click',reset);root.querySelector('#step').addEventListener('click',advance);
addEventListener('resize',resize);makeStates();index=startIndex();resize();const speed=root.querySelector('#speed');setInterval(()=>{if(document.hidden)return;elapsed+=100;const baseDelay=kind==='divide-and-conquer'?1500:1050;if(elapsed>=baseDelay-Number(speed.value)*160){elapsed=0;advance()}},100);