29:null 2a:["$","title",null,{"children":"Binary tree looks like | Chuncheng | Observable"}] 2f:[{"id":"f0a15c298167aea5b083e7c7910f8e75f83244501093ffb35b471f8134b6e32153d3aef5f8e7f65ceb165857cdaaf2c35ef1f4fdf7ca872bc872021d49bde9e0","href":"https://static.observableusercontent.com/files/f0a15c298167aea5b083e7c7910f8e75f83244501093ffb35b471f8134b6e32153d3aef5f8e7f65ceb165857cdaaf2c35ef1f4fdf7ca872bc872021d49bde9e0","name":"bad.png","type":"image/png","lastModified":1729235565035.69,"size":51092},{"id":"5dbbd4866fd9c1020078a148622884507aece7825c6193d3820cf838db5ba89279319ccc45dd6e648a1d6f919915f4ad12bde1fe7fb8e78e8dddc78d98aca298","href":"https://static.observableusercontent.com/files/5dbbd4866fd9c1020078a148622884507aece7825c6193d3820cf838db5ba89279319ccc45dd6e648a1d6f919915f4ad12bde1fe7fb8e78e8dddc78d98aca298","name":"good.png","type":"image/png","lastModified":1729235565101.786,"size":79266}] 2d:{"id":"a81cbf97435019ef","slug":null,"title":"Binary tree looks like","thumbnail":"be91c353105b56a1eac31bf52fdd9d0a86fcf29f5a84905d47149bc4964d8387","access_level":"public","create_time":"$D2024-10-18T03:16:55.207Z","update_time":"$D2024-10-18T07:24:33.391Z","view_time":null,"first_public_time":"$D2024-10-18T03:19:26.777Z","fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"bcd65cef1cb4d2ed","login":"listenzcc","name":"Chuncheng","avatar_url":"https://avatars-next.observableusercontent.com/bb3c68e77a708a587ffc2d663bb83421f20d67991dbe6c1623c6e5d2fb73d15e","tier":"starter_2024"},"version":137,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"16328058352682a8","login":"listenzcc","name":"Chuncheng","avatar_url":"https://avatars-next.observableusercontent.com/bb3c68e77a708a587ffc2d663bb83421f20d67991dbe6c1623c6e5d2fb73d15e","tier":null}],"members":[{"type":"individual","id":"16328058352682a8","login":"listenzcc","name":"Chuncheng","avatar_url":"https://avatars-next.observableusercontent.com/bb3c68e77a708a587ffc2d663bb83421f20d67991dbe6c1623c6e5d2fb73d15e","tier":null,"role":"editor"},{"type":"team","id":"bcd65cef1cb4d2ed","login":"listenzcc","name":"Chuncheng","avatar_url":"https://avatars-next.observableusercontent.com/bb3c68e77a708a587ffc2d663bb83421f20d67991dbe6c1623c6e5d2fb73d15e","tier":"starter_2024","role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Binary tree looks like","cells":[{"id":0,"value":"# Binary tree looks like\n\nFor the simplest binary tree, the more branches the better.\nHere are the good vs bad tree examples.\nThe more branches mean the expecting steps are required to query a certain value.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":107,"value":"htl.html`\n

Bad tree

Good tree

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":128,"value":"## Interactive example\n\nDrag the amount slider to **re-generate** the tree with random values.\nThe amount is how many points are building the tree.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":52,"value":"viewof amount = Inputs.range([10, 200], { label: \"Amount\", step: 1 })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":63,"value":"{\n let plt,\n { newTree } = pt;\n\n newTree.map((d) => (d._x = d.x - Math.pow(2, d.y - 1)));\n\n plt = Plot.plot({\n x: { nice: true, type: \"symlog\" },\n y: { nice: true },\n color: { legend: true, scheme: \"Blues\" },\n marks: [\n Plot.link(\n newTree.filter((d) => d.left),\n {\n x1: \"_x\",\n y1: \"y\",\n x2: (d) => newTree[d.left]._x,\n y2: (d) => newTree[d.left].y\n }\n ),\n Plot.link(\n newTree.filter((d) => d.right),\n {\n x1: \"_x\",\n y1: \"y\",\n x2: (d) => newTree[d.right]._x,\n y2: (d) => newTree[d.right].y\n }\n ),\n Plot.dot(newTree, {\n x: \"_x\",\n y: \"y\",\n tip: true,\n fill: \"orange\",\n stroke: \"y\",\n r: 10\n }),\n Plot.text(newTree, {\n x: \"_x\",\n y: \"y\",\n text: \"v\"\n })\n ]\n });\n\n return plt;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":110,"value":"FileAttachment(\"bad.png\").url()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":105,"value":"bad = FileAttachment(\"bad.png\").image()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":106,"value":"good = FileAttachment(\"good.png\").image()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":43,"value":"tree.map((d) => d.v).sort((a, b) => a - b)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":36,"value":"pt = parseTree(tree)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"tree = mkTree()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"parseTree = (tree) => {\n let rootPtr = 0,\n output = [];\n\n let loop = (ptr, x, y) => {\n let node = tree[ptr];\n Object.assign(node, { x, y });\n if (node.left) {\n loop(node.left, x * 2, y + 1);\n }\n output.push(node.v);\n if (node.right) {\n loop(node.right, x * 2 + 1, y + 1);\n }\n };\n\n loop(rootPtr, 0, 0);\n\n return { newTree: tree, sorted: output };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"mkTree = () => {\n let array = randomValues(amount),\n nodes = [];\n\n nodes.push(mkNode(array[0]));\n\n array.slice(1).map((v) => {\n // Add the v into the tree from the root\n let ptr = 0;\n\n let goto = (ptr) => {\n let node = nodes[ptr];\n\n if (v == node.v) {\n node.v += 1;\n }\n if (v > node.v) {\n if (node.right) {\n goto(node.right);\n } else {\n nodes.push(mkNode(v));\n node.right = nodes.length - 1;\n }\n }\n if (v < node.v) {\n if (node.left) {\n goto(node.left);\n } else {\n nodes.push(mkNode(v));\n node.left = nodes.length - 1;\n }\n }\n };\n\n goto(0);\n });\n\n return nodes;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"node = mkNode(3)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"mkNode = (v) => {\n let left,\n right,\n count = 1;\n return { v, count, left, right };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"array = randomValues()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"randomValues = (n = 100) => {\n let array = [...new Array(n)]\n .fill(0)\n .map((_) => parseInt(Math.random() * 1000));\n return array;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W2f","stdlib":"1","titling":"auto"}} 2e:"$2d:body"