% Lazy stream article input boxes scale := 1; dotsize = scale * 3pt; xspacing = .25in; yspacing = .1in; beginfig(1); boxit.key(btex key etex); boxit.data(btex data etex); boxit.keyl(btex key etex); boxit.datal(btex data etex); boxit.keyr(btex key etex); boxit.datar(btex data etex); key.sw = data.nw; key.se = data.ne; keyl.sw = datal.nw; keyl.se = datal.ne; keyr.sw = datar.nw; keyr.se = datar.ne; data.dx = .2in; datal.dx = .2in; datar.dx = .2in; key.sw = (keyl.ne) + (xspacing, yspacing); key.se = (keyr.nw) + (-xspacing, yspacing); drawboxed(key, data, keyl, datal, keyr, datar); drawarrow key.sw -- keyl.n cutafter bpath keyl; drawarrow key.se -- keyr.n cutafter bpath keyr; endfig ; def bintree(suffix r, p, q) = r.sw = p.ne + (xspacing,yspacing); r.se = q.nw + (-xspacing,yspacing); enddef; beginfig(2); boxit.a("A"); boxit.b("B"); boxit.c("C"); boxit.d("D"); boxit.e("E"); bintree(d,b,e); bintree(b,a,c); drawboxed(a,b,c,d,e); drawarrow d.sw -- b.c cutafter bpath b; drawarrow d.se -- e.c cutafter bpath e; drawarrow b.sw -- a.c cutafter bpath a; drawarrow b.se -- c.c cutafter bpath c; endfig; beginfig(31); boxit.b("B"); drawboxed(b); endfig; beginfig(32); boxit.b("B"); boxit.d("D"); b.se = d.nw + (-xspacing,yspacing); drawboxed(b, d); drawarrow b.se -- d.c cutafter bpath d; endfig; beginfig(33); boxit.b("B"); boxit.d("D"); boxit.c("C"); b.se = d.nw + (-xspacing,yspacing); d.sw = c.ne + (xspacing,yspacing); drawboxed(b, d, c); drawarrow b.se -- d.c cutafter bpath d; drawarrow d.sw -- c.c cutafter bpath c; endfig; beginfig(34); boxit.b("B"); boxit.d("D"); boxit.c("C"); boxit.a("A"); b.se = d.nw + (-xspacing,yspacing); b.sw = a.ne + (xspacing,yspacing); d.sw = c.ne + (xspacing,yspacing); drawboxed(b, d, c, a); drawarrow b.se -- d.c cutafter bpath d; drawarrow b.sw -- a.c cutafter bpath a; drawarrow d.sw -- c.c cutafter bpath c; endfig; beginfig(35); boxit.b("B"); boxit.d("D"); boxit.c("C"); boxit.a("A"); boxit.e("E"); b.se = d.nw + (-xspacing,yspacing); b.sw = a.ne + (xspacing,yspacing); d.sw = c.ne + (xspacing,yspacing); d.se = e.nw + (-xspacing,yspacing); drawboxed(b, d, c, a, e); drawarrow b.se -- d.c cutafter bpath d; drawarrow b.sw -- a.c cutafter bpath a; drawarrow d.sw -- c.c cutafter bpath c; drawarrow d.se -- e.c cutafter bpath e; endfig; beginfig(4); boxit.a("A"); boxit.b("B"); boxit.c("C"); boxit.d("D"); boxit.e("E"); a.se = b.nw + (-xspacing,yspacing); b.se = c.nw + (-xspacing,yspacing); c.se = d.nw + (-xspacing,yspacing); d.se = e.nw + (-xspacing,yspacing); drawboxed(b, d, c, a, e); drawarrow a.se -- b.c cutafter bpath b; drawarrow b.se -- c.c cutafter bpath c; drawarrow c.se -- d.c cutafter bpath d; drawarrow d.se -- e.c cutafter bpath e; endfig; beginfig(51); boxit.key("Key"); boxit.lst(btex Left subtree etex); boxit.rst(btex Right subtree etex); key.sw = (lst.ne) + (xspacing, yspacing); key.se = (rst.nw) + (-xspacing, yspacing); drawboxed(key, key, lst, rst); drawarrow key.sw -- lst.c cutafter bpath lst; drawarrow key.se -- rst.c cutafter bpath rst; endfig; beginfig(52); boxjoin(a.se=b.sw; a.ne=b.nw); boxit.k0(btex ${\rm Key}_0$ etex); boxit.k1(btex ${\rm Key}_1$ etex); boxit.k2(btex ${\rm Key}_2$ etex); boxit.kddd(btex $\cdots$ etex); boxit.knm1(btex ${\rm Key}_{N-1}$ etex); stspc := .2in; % Space between subtree boxes boxjoin(a.se + (stspc, 0) = b.sw; a.ne + (stspc, 0) = b.nw); boxit.st0(btex ${\rm Subtree}_0$ etex); boxit.st1(btex ${\rm Subtree}_1$ etex); boxit.st2(btex ${\rm Subtree}_2$ etex); boxit.stddd1(btex $ \cdots $ etex); boxit.stddd2(btex $ \cdots $ etex); boxit.stnm1(btex ${\rm Subtree}_{N-1}$ etex); boxit.stn(btex ${\rm Subtree}_N$ etex); rowshift := stspc*5; % subtree nodes start this distance to left of keys yshift := stspc*2.5; % subtree nodes are this distance below keys st0.ne = k0.se + (-rowshift, -yshift); drawboxed(k0, k1, k2, kddd, knm1); drawboxed(st0, st1, st2, stddd1, stddd2, stnm1, stn); drawarrow k0.sw -- st0.n cutafter bpath st0; drawarrow k1.sw -- st1.n cutafter bpath st1; drawarrow k2.sw -- st2.n cutafter bpath st2; drawarrow k2.se -- stddd1.n cutafter bpath stddd1; drawarrow kddd.s -- stddd2.n cutafter bpath stddd2 cutbefore bpath kddd; drawarrow knm1.sw -- stnm1.n cutafter bpath stnm1; drawarrow knm1.se -- stn.n cutafter bpath stn; endfig; beginfig(61); boxjoin(a.se=b.sw; a.ne=b.nw); boxit.k0(btex ${\rm Key}_0$ etex); boxit.k1(btex ${\rm Key}_1$ etex); boxit.k2(btex ${\rm Key}_2$ etex); boxit.k3(btex ${\rm Key}_3$ etex); boxit.k4(btex ${\rm Key}_4$ etex); stspc := .2in; % Space between subtree boxes boxjoin(a.se + (stspc, 0) = b.sw; a.ne + (stspc, 0) = b.nw); boxit.st0(btex ${\rm Subtree}_0$ etex); boxit.st1(btex ${\rm Subtree}_1$ etex); boxit.st2(btex ${\rm Subtree}_2$ etex); boxit.st3(btex ${\rm Subtree}_3$ etex); boxit.st4(btex ${\rm Subtree}_4$ etex); boxit.st5(btex ${\rm Subtree}_5$ etex); % rowshift = stspc*5; % subtree nodes start this distance to left of keys yshift := stspc*2.5; % subtree nodes are this distance below keys % st0.ne = k0.se + (-rowshift, -yshift); xpart (st2.c + st3.c)*.5 = xpart k2.c; ypart st2.c = (ypart k2.c) - yshift; drawboxed(k0, k1, k2, k3, k4); drawboxed(st0, st1, st2, st3, st4, st5); drawarrow k0.sw -- st0.n cutafter bpath st0; drawarrow k1.sw -- st1.n cutafter bpath st1; drawarrow k2.sw -- st2.n cutafter bpath st2; drawarrow k3.sw -- st3.n cutafter bpath st3; drawarrow k4.sw -- st4.n cutafter bpath st4; drawarrow k4.se -- st5.n cutafter bpath st5; endfig; beginfig(62); boxjoin(a.se=b.sw; a.ne=b.nw); boxit.k0(btex ${\rm Key}_0$ etex); boxit.k1(btex ${\rm Key}_1$ etex); boxjoin(); boxit.k2(btex ${\rm Key}_2$ etex); boxjoin(a.se=b.sw; a.ne=b.nw); boxit.k3(btex ${\rm Key}_3$ etex); boxit.k4(btex ${\rm Key}_4$ etex); stspc := .2in; % Space between subtree boxes boxjoin(a.se + (stspc, 0) = b.sw; a.ne + (stspc, 0) = b.nw); boxit.st0(btex ${\rm Subtree}_0$ etex); boxit.st1(btex ${\rm Subtree}_1$ etex); boxit.st2(btex ${\rm Subtree}_2$ etex); boxjoin(a.se + (stspc, 0) = b.sw; a.ne + (stspc, 0) = b.nw); boxit.st3(btex ${\rm Subtree}_3$ etex); boxit.st4(btex ${\rm Subtree}_4$ etex); boxit.st5(btex ${\rm Subtree}_5$ etex); % rowshift = stspc*5; % subtree nodes start this distance to left of keys yshift := stspc*2.5; % subtree nodes are this distance below keys % st0.ne = k0.se + (-rowshift, -yshift); xpart (k0.c + k1.c)*.5 = xpart st1.c; xpart (k3.c + k4.c)*.5 = xpart st4.c; xpart (k3.c - k2.c) = xpart (k2.c - k1.c) = stspc*6; ypart k2.c = (ypart k1.c) + yshift; ypart k1.c = ypart k3.c; ypart k1.c = (ypart st1.c) + yshift; ypart k4.c = (ypart st4.c) + yshift; drawboxed(k0, k1, k2, k3, k4); drawboxed(st0, st1, st2, st3, st4, st5); drawarrow k0.sw -- st0.n cutafter bpath st0; drawarrow k1.sw -- st1.n cutafter bpath st1; drawarrow k1.se -- st2.n cutafter bpath st2; % drawarrow k2.sw -- st2.n cutafter bpath st2; drawarrow k3.sw -- st3.n cutafter bpath st3; drawarrow k4.sw -- st4.n cutafter bpath st4; drawarrow k4.se -- st5.n cutafter bpath st5; endfig; beginfig(71); boxit.a("A"); drawboxed(a); endfig; beginfig(72); boxjoin(a.se=b.sw; a.ne=b.nw); boxit.a("A"); boxit.b("B"); drawboxed(a, b); endfig; beginfig(73); boxit.a("A"); boxit.b("B"); boxit.c("C"); b.se = c.nw + (-xspacing,yspacing); b.sw = a.ne + (xspacing,yspacing); drawboxed(a, b, c); drawarrow b.sw -- a.n; drawarrow b.se -- c.n; endfig; beginfig(74); boxit.a("A"); boxit.b("B"); boxit.c("C"); boxit.d("D"); c.se=d.sw; c.ne=d.nw; b.se = c.n + (-xspacing,yspacing); b.sw = a.ne + (xspacing,yspacing); drawboxed(a, b, c, d); drawarrow b.sw -- a.n; drawarrow b.se -- c.ne; endfig; beginfig(75); boxit.a("A"); boxit.b("B"); boxit.c("C"); boxit.d("D"); boxit.e("E"); c.se=d.sw; c.ne=d.nw; d.se=e.sw; d.ne=e.nw; b.se = d.n + (-xspacing,yspacing); b.sw = a.ne + (xspacing,yspacing); drawboxed(a, b, c, d, e); drawarrow b.sw -- a.n; drawarrow b.se -- d.n; endfig; beginfig(76); boxit.a("A"); boxit.b("B"); boxit.c("C"); boxit.d("D"); boxit.e("E"); b.se=d.sw; b.ne=d.nw; d.se = e.nw + (-xspacing,yspacing); b.sw = a.ne + (xspacing,yspacing); b.se = c.n + (0, yspacing); drawboxed(a, b, c, d, e); drawarrow b.sw -- a.n; drawarrow d.se -- e.n; drawarrow b.se -- c.n; endfig; beginfig(83); boxit.b("B"); boxit.c("C"); boxit.d("D"); c.se = d.nw + (-xspacing,yspacing); c.sw = b.ne + (xspacing,yspacing); drawboxed(b, c, d); drawarrow c.sw -- b.n; drawarrow c.se -- d.n; endfig; beginfig(85); boxit.a("A"); boxit.b("B"); boxit.c("C"); boxit.d("D"); boxit.e("E"); a.se=b.sw; a.ne=b.nw; d.se=e.sw; d.ne=e.nw; c.se = d.ne + (-xspacing,yspacing); c.sw = a.ne + (xspacing,yspacing); drawboxed(a, b, c, d, e); drawarrow c.sw -- a.ne; drawarrow c.se -- d.ne; endfig; beginfig(86); boxit.a("A"); boxit.b("B"); boxit.c("C"); boxit.d("D"); boxit.e("E"); boxit.f("F"); a.se=b.sw; a.ne=b.nw; c.se=e.sw; c.ne=e.nw; c.sw = a.ne + (xspacing,yspacing); e.se = f.nw + (-xspacing,yspacing); c.se = d.n + (0, yspacing); drawboxed(a, b, c, d, e, f); drawarrow c.sw -- a.ne; drawarrow c.se -- d.n; drawarrow e.se -- f.nw; endfig; beginfig(91); boxjoin(a.se=b.sw; a.ne=b.nw); boxit.kdddm(btex $\cdots$ etex); boxit.kwm2(btex ${\rm Key}_{\$where-2}$ etex); boxit.kwm1(btex ${\rm Key}_{\$where-1}$ etex); boxit.kw (btex ${\rm Key}_{\$where}$ etex); boxit.kwp1(btex ${\rm Key}_{\$where+1}$ etex); boxit.kdddp(btex $\cdots$ etex); stspc := .5in; % Space between subtree boxes verbatimtex \def\stk#1#2{$\displaystyle{\matrix{#1\cr#2\cr}}$} etex verbatimtex \def\stkk#1#2#3{$\displaystyle{\matrix{#1\cr#2\cr#3\cr}}$} etex boxjoin(a.se + (stspc, 0) = b.sw; a.ne + (stspc, 0) = b.nw); % boxit.stdddm(btex $\cdots$ etex); boxit.stwm1(btex \stkk{\hbox{\rm Some unimportant}} {\hbox{\rm node $X$ is attached here}} {\hbox{\rm as subnode ${\tt\$where}-1$}} etex); boxit.stw (btex \stkk{\hbox{\rm {\tt \$cur\_node} is}} {\hbox{\rm attached here}} {\hbox{\rm as subnode {\tt \$where}}} etex); boxit.stwp1(btex \stkk{\hbox{\rm Another unimportant}} {\hbox{\rm node $Y$ is attached here}} {\hbox{\rm as subnode ${\tt\$where}+1$}} etex); % boxit.stdddp(btex $\cdots$ etex); % rowshift = stspc*5; % subtree nodes start this distance to left of keys yshift := yspacing; % subtree nodes are this distance below keys % st0.ne = k0.se + (-rowshift, -yshift); xpart stw.c = xpart kw.sw; ypart stw.n = (ypart kw.s) - yshift*2; drawunboxed(kdddm); drawboxed(kwm2, kwm1, kw, kwp1); drawunboxed(kdddp); % drawunboxed(stdddm); drawboxed(stwm1, stw, stwp1); % drawunboxed(stdddp); % drawarrow kdddm.sw -- stdddm.n; drawarrow kwm1.sw -- stwm1.n; drawarrow kw.sw -- stw.n; drawarrow kwp1.sw -- stwp1.n; % drawarrow kdddp.sw -- stdddp.n; endfig; beginfig(92); boxjoin(a.se=b.sw; a.ne=b.nw); boxit.kdddm(btex $\cdots$ etex); boxit.kwm1(btex ${\rm Key}_{\$where-1}$ etex); boxit.kkdp (btex {\tt \$kdp} etex); boxit.kw (btex ${\rm Key}_{\$where}$ etex); boxit.kdddp(btex $\cdots$ etex); stspc := .5in; % Space between subtree boxes % verbatimtex \def\stk#1#2{$\displaystyle{\matrix{#1\cr#2\cr}}$} etex % verbatimtex \def\stkk#1#2#3{$\displaystyle{\matrix{#1\cr#2\cr#3\cr}}$} etex boxjoin(a.se + (stspc, 0) = b.sw; a.ne + (stspc, 0) = b.nw); % boxit.stdddm(btex $\cdots$ etex); boxit.stwm1(btex \stk{\hbox{\rm Unimportant}} {\hbox{\rm node $X$ }} etex); boxit.stnl (btex {\tt \$newleft} etex); boxit.stnr (btex {\tt \$newright} etex); boxit.stwp1(btex \stk{\hbox{\rm Unimportant}} {\hbox{\rm node $Y$}} etex); % boxit.stdddp(btex $\cdots$ etex); % rowshift = stspc*5; % subtree nodes start this distance to left of keys yshift := yspacing; % subtree nodes are this distance below keys % st0.ne = k0.se + (-rowshift, -yshift); (xpart (stnl.c + stnr.c)) *.5 = xpart kkdp.c; ypart stnl.n = (ypart kkdp.s) - yshift*2; drawunboxed(kdddm); drawboxed(kwm1, kkdp, kw); drawunboxed(kdddp); % drawunboxed(stdddm); drawboxed(stwm1, stnl, stnr, stwp1); % drawunboxed(stdddp); % drawarrow kdddm.sw -- stdddm.n; drawarrow kwm1.sw -- stwm1.n; drawarrow kkdp.sw -- stnl.n; drawarrow kkdp.se -- stnr.n; drawarrow kw.se -- stwp1.n; % drawarrow kdddp.sw -- stdddp.n; endfig; beginfig(10); gap := .5in; space := .25in; boxjoin(a.se = b.sw; a.ne = b.nw); boxit.k0(btex ${\rm Key}_0$ etex); boxit.k1(btex ${\rm Key}_1$ etex); boxit.k2(btex ${\rm Key}_2$ etex); boxit.kddd(btex $\cdots$ etex); boxit.knm1(btex ${\rm Key}_{N-1}$ etex); boxjoin(a.se = b.sw; a.ne = b.nw); boxit.d0(btex ${\rm Data}_0$ etex); boxit.d1(btex ${\rm Data}_1$ etex); boxit.d2(btex ${\rm Data}_2$ etex); boxit.dddd(btex $\cdots$ etex); boxit.dnm1(btex ${\rm Data}_{N-1}$ etex); boxjoin(a.se = b.sw; a.ne = b.nw); boxit.s0(btex ${\rm Subnode}_0$ etex); boxit.s1(btex ${\rm Subnode}_1$ etex); boxit.s2(btex ${\rm Subnode}_2$ etex); boxit.sddd(btex $\cdots$ etex); boxit.snm1(btex ${\rm Subnode}_{N-1}$ etex); boxit.sn(btex ${\rm Subnode}_N$ etex); boxjoin(a.se = b.ne; a.sw = b.nw); boxit.mk(); boxit.md(); boxit.ms(); mk.dx = 12bp; mk.dy = md.dy = ms.dy = 12bp; xpart k0.w = (xpart mk.e) + gap; xpart d0.w = (xpart md.e) + gap; xpart s0.w = (xpart ms.e) + gap; % ypart k0.s = (ypart d0.n) + space; % ypart d0.s = (ypart s0.n) + space; ypart mk.e = ypart k0.w; ypart md.e = ypart d0.w; ypart ms.e = ypart s0.w; drawboxed(mk, md, ms); drawboxed(k0, k1, k2, kddd, knm1); drawboxed(d0, d1, d2, dddd, dnm1); drawboxed(s0, s1, s2, sddd, snm1, sn); drawarrow mk.c -- k0.w; drawarrow md.c -- d0.w; drawarrow ms.c -- s0.w; endfig; end