3e:null 3f:["$","title",null,{"children":"Simple Binary Search Tree | Penn | Observable"}] 45:Tdae,tree1 = { const width = 800 const height = 600 const margin = 20 const radius = 10 const bst = new BinarySearchTree() const data = weBeSearchingOver1 data.forEach(d => { bst.insert(d) }) const tree = d3.tree().size([width, height]) const root = d3.hierarchy(bst.root, function(d) { d.children = [] if(d.left) { d.children.push(d.left) } if(d.right) { d.children.push(d.right) } return d.children }) root.x0 = width / 2 root.y0 = 0 var treeData = tree(root) var nodes = treeData.descendants() var links = treeData.descendants().slice(1) var svg = d3 .create('svg') .attr('width', width + margin * 2) .attr('height', height + margin * 2) var g = svg .append('g') .attr('transform', `translate(${margin},${margin})`) var link = g .selectAll('line.link') .data(links) var linkEnter = link .enter() .append('line') .attr('class', 'link') .attr('data-value', d => d.data.value) .attr('x1', d => d.parent.x) .attr('y1', d => d.parent.y) .attr('x2', d => d.x) .attr('y2', d => d.y) .attr('stroke', '#ddd') .attr('stroke-dasharray', '4px 8px') var node = g .selectAll('g.node') .data(nodes) var nodeEnter = node .enter() .append('g') .attr('class', 'node') nodeEnter .append('circle') .attr('data-value', d => d.data.value) .attr('r', radius) .attr('fill', '#FFF') .attr('stroke', '#ddd') .attr('transform', d => `translate(${d.x},${d.y})`) nodeEnter .append('text') .attr('text-anchor', 'middle') .attr('alignment-baseline', 'middle') .attr('transform', d => `translate(${d.x},${d.y + 1})`) .style('font-size', '14px') .text(d => d.data.value) if(searchFor1) { var path = bst.getSearchPath(searchFor1) mutable recurs1 = path.length var pathNodes = nodes.filter(n => path.includes(n.value)) var pathLinks = links.filter(l => path.includes(l.value)) for(let j = 0; j < path.length; j++) { g .selectAll('line.path') .data(pathLinks) .enter() .append('line') .attr('class', 'path') .attr('x1', d => d.parent.x) .attr('y1', d => d.parent.y) .attr('x2', d => d.x) .attr('y2', d => d.y) .attr('stroke', 'steelblue') .attr('stroke-width', 2) .attr('stroke-dasharray', d => length(d)) .attr('stroke-dashoffset', d => length(d)) .transition() .duration(500) .delay((d, i) => i * 500 + 1000) .attr('stroke-dashoffset', d => 0) g .selectAll('circle.path') .data(pathNodes) .enter() .append('circle') .attr('class', 'path') .attr('r', radius) .attr('fill', '#FFF') .attr('transform', d => `translate(${d.x},${d.y})`) .attr('stroke', 'steelblue') .attr('stroke-width', 2) .attr('stroke-dasharray', 2 * Math.PI * radius) .attr('stroke-dashoffset', 2 * Math.PI * radius) .transition() .duration(500) .delay((d, i) => i * 500) .attr('stroke-dashoffset', 0) g.selectAll('text.path') .data(pathNodes) .enter() .append('text') .attr('class', 'path') .attr('text-anchor', 'middle') .attr('alignment-baseline', 'middle') .attr('transform', d => `translate(${d.x},${d.y + 1})`) .style('font-size', '14px') .text(d => d.data.value) } } return svg.node() }46:Taa8,tree2 = { const width = 800 const height = 600 const margin = 20 const radius = .5 const bst = new BinarySearchTree() const data = d3.shuffle(d3.range(0, 10000)) data.forEach(d => { bst.insert(d) }) const tree = d3.tree().size([width, height]) const root = d3.hierarchy(bst.root, function(d) { d.children = [] if(d.left) { d.children.push(d.left) } if(d.right) { d.children.push(d.right) } return d.children }) root.x0 = width / 2 root.y0 = 0 var treeData = tree(root) var nodes = treeData.descendants() var links = treeData.descendants().slice(1) var svg = d3 .create('svg') .attr('width', width + margin * 2) .attr('height', height + margin * 2) var g = svg .append('g') .attr('transform', `translate(${margin},${margin})`) var link = g .selectAll('line.link') .data(links) var linkEnter = link .enter() .append('line') .attr('class', 'link') .attr('data-value', d => d.data.value) .attr('x1', d => d.parent.x) .attr('y1', d => d.parent.y) .attr('x2', d => d.x) .attr('y2', d => d.y) .attr('stroke', '#ddd') .attr('stroke-width', .5) var node = g .selectAll('g.node') .data(nodes) var nodeEnter = node .enter() .append('g') .attr('class', 'node') nodeEnter .append('circle') .attr('data-value', d => d.data.value) .attr('r', radius) .attr('fill', '#000') .attr('transform', d => `translate(${d.x},${d.y})`) if(searchFor2) { var path = bst.getSearchPath(searchFor2) mutable recurs2 = path.length var pathNodes = nodes.filter(n => path.includes(n.value)) var pathLinks = links.filter(l => path.includes(l.value)) for(let j = 0; j < path.length; j++) { g .selectAll('line.path') .data(pathLinks) .enter() .append('line') .attr('class', 'path') .attr('x1', d => d.parent.x) .attr('y1', d => d.parent.y) .attr('x2', d => d.x) .attr('y2', d => d.y) .attr('stroke', 'steelblue') .attr('stroke-width', 1) .attr('stroke-dasharray', d => length(d)) .attr('stroke-dashoffset', d => length(d)) .transition() .duration(500) .delay((d, i) => i * 500 + 500) .attr('stroke-dashoffset', d => 0) g .selectAll('circle.path') .data(pathNodes) .enter() .append('circle') .attr('class', 'path') .attr('r', radius*4) .attr('fill', 'none') .attr('transform', d => `translate(${d.x},${d.y})`) .transition() .duration(500) .delay((d, i) => i * 500) .attr('fill', 'steelblue') } } return svg.node() }47:T917,{ const height = 600 const margin = 20 const c = DOM.context2d(width, height, 1) const bst = new BinarySearchTree() const data = weBeSearchingOver3 data.forEach(d => { bst.insert(d) }) const hierarchy = d3.hierarchy(bst.root, function(d) { d.children = [] if(d.left) { d.children.push(d.left) } if(d.right) { d.children.push(d.right) } return d.children }) const tree = d3 .tree() .size([width - margin * 2, height - margin * 2]) .nodeSize([spread, 15]) const t = tree(hierarchy) const nodes = t.descendants() const links = t.links() const linkVertical = d3 .linkVertical() .context(c) .x(d => d.x + 10) .y(d => d.y + 10) function draw() { c.strokeStyle = "#ccc" c.lineWidth = 1 c.beginPath() for (let link of links) linkVertical(link) c.stroke() const circle = d3 .symbol() .type(d3.symbolCircle) .size(5) .context(c) for (const node of nodes) { c.beginPath() c.save() c.fillStyle = '#000' c.translate(node.x + 10, node.y + 10) circle(node) c.fill() c.restore() } if(searchFor3) { var path = bst.getSearchPath(searchFor3) mutable recurs3 = path.length var pathNodes = nodes.filter(n => path.includes(n.value)) var pathLinks = links.filter(l => path.includes(l.target.value)) c.strokeStyle = "steelblue" c.lineWidth = 2 c.beginPath() for (let link of pathLinks) linkVertical(link) c.stroke() const circle = d3 .symbol() .type(d3.symbolCircle) .size(10) .context(c) for (const node of pathNodes) { c.beginPath() c.save() c.fillStyle = 'steelblue' c.translate(node.x + 10, node.y + 10) circle(node) c.fill() c.restore() } } } function zoomed() { c.save() c.clearRect(0, 0, width, height) c.translate(d3.event.transform.x, d3.event.transform.y) c.scale(d3.event.transform.k, d3.event.transform.k) draw() c.restore() } d3.select(c.canvas).call( d3 .zoom() .scaleExtent([1 / 16, 4]) .on("zoom", zoomed) ); draw() c.canvas.style = "cursor: move" return c.canvas }48:T915,class BinarySearchTree { constructor() { this.root = null this.path = [] } insert(value) { var newNode = new Node(value) if(this.root === null) { this.root = newNode } else { this.insertNode(this.root, newNode) } } insertNode(node, newNode) { if(newNode.value < node.value) { if(node.left === null) { node.left = newNode } else { this.insertNode(node.left, newNode) } } else { if(node.right === null) { node.right = newNode } else { this.insertNode(node.right, newNode) } } } remove(value) { this.root = this.removeNode(this.root, value) } removeNode(node, key) { if(node === null) { return null } else if(key < node.value) { node.left = this.removeNode(node.left, key) return node } else if(key > node.value) { node.right = this.removeNode(node.right, key) return node } else { if(node.left === null && node.right === null) { node = null return node } if(node.left === null) { node = node.right return node } else if(node.right === null) { node = node.left return node } var aux = this.findMinNode(node.right) node.value = aux.value node.right = this.removeNode(node.right, aux.value) return node } } findMinMode(node) { if(node.left === null) { return node } else { return this.findMinNode(node.left) } } getRootNode() { return this.root } inorder(node) { if(node !== null) { this.inorder(node.left) console.log(node.value) this.inorder(node.right) } } search(node, value, initial = false) { if(initial) { this.path = [] } if(node === null) { return null } else if(value < node.value) { this.path.push(node.value) return this.search(node.left, value) } else if(value > node.value) { this.path.push(node.value) return this.search(node.right, value) } else { this.path.push(node.value) return node } } getPath() { return this.path } getSearchPath(value) { this.search(this.root, value, true) return this.getPath() } }49:[] 43:{"id":"6084d83c0000148c","slug":null,"title":"Simple Binary Search Tree","thumbnail":"e5b9294f8d9a7d4be2509cc91f53158a6db046aa3b26749dcbf533a8b700a8bf","access_level":"public","create_time":"$D2023-07-12T11:14:50.209Z","update_time":"$D2023-07-12T11:14:50.209Z","view_time":null,"first_public_time":"$D2023-07-12T11:14:50.209Z","has_unpublished_edits":null,"fork":{"id":"364fa054f520b3fa","slug":"simple-binary-search-tree","title":"Simple Binary Search Tree","owner":{"id":"15d67834e9550a94","login":"benjaminadk","name":"BVG Software"}},"stars":0,"starred":false,"owner":{"type":"team","id":"7dd579cd728bc7fb","login":"alwayscry","name":"Penn","avatar_url":"https://avatars-next.observableusercontent.com/ed7f2516457eb636384ee646fd29739a5990570a3e61524d2972fba33013fa42","tier":"starter_2024","bio":"","following":false},"version":514,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"fe17292941b86055","login":"alwayscry","name":"Penn","avatar_url":"https://avatars-next.observableusercontent.com/ed7f2516457eb636384ee646fd29739a5990570a3e61524d2972fba33013fa42","tier":null,"bio":"","following":false}],"members":[{"type":"individual","id":"fe17292941b86055","login":"alwayscry","name":"Penn","avatar_url":"https://avatars-next.observableusercontent.com/ed7f2516457eb636384ee646fd29739a5990570a3e61524d2972fba33013fa42","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Simple Binary Search Tree","cells":[{"id":0,"value":"md`# Simple Binary Search Tree`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":489,"value":"viewof reset1 = button('Re-Shuffle Array Values')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":363,"value":"weBeSearchingOver1 = {\n reset1\n return d3.shuffle(d3.range(0, 100))\n} ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":129,"value":"viewof searchFor1 = number({\n min: 0,\n max: weBeSearchingOver1.length - 1,\n step: 1,\n value: 50,\n submit: 'Watch Search'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":372,"value":"linear1 = {\n var count = 0\n for(let i = 0; i < weBeSearchingOver1.length; i++) {\n if(weBeSearchingOver1[i] === searchFor1) break\n count++ \n }\n return md`*Linear Search* of ${weBeSearchingOver1.length} items took **${count}** recursions`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":330,"value":"binary1 = {\n return recurs1 ? md`*Binary Search Tree* of ${weBeSearchingOver1.length} items took **${recurs1}** recursions` : md`Sumbit a value`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"$45","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":496,"value":"viewof reset2 = button('Re-Shuffle Array Values')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":417,"value":"weBeSearchingOver2 = {\n reset2\n return d3.shuffle(d3.range(0, 10000))\n} ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":310,"value":"viewof searchFor2 = number({\n min: 0,\n max: weBeSearchingOver2,\n step: 1,\n value: 5000,\n submit: 'Watch Search'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":423,"value":"linear2 = {\n var count = 0\n for(let i = 0; i < weBeSearchingOver2.length; i++) {\n if(weBeSearchingOver2[i] === searchFor2) break\n count++ \n }\n return md`*Linear Search* of ${weBeSearchingOver2.length} items took **${count}** recursions`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":347,"value":"binary2 = {\n return recurs2 ? md`*Binary Search Tree* of 10000 items took **${recurs2}** recursions` : md`Sumbit a value`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":302,"value":"$46","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":452,"value":"weBeSearchingOver3 = d3.shuffle(d3.range(0, 100000))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":455,"value":"viewof searchFor3 = number({\n min: 0,\n max: weBeSearchingOver3,\n step: 1,\n value: 50000,\n submit: 'Watch Search'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":478,"value":"{\n var count = 0\n for(let i = 0; i < weBeSearchingOver3.length; i++) {\n if(weBeSearchingOver3[i] === searchFor3) break\n count++ \n }\n return md`*Linear Search* of ${weBeSearchingOver3.length} items took **${count}** recursions`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":481,"value":"recurs3 ? md`*Binary Search Tree* of 100000 items took **${recurs3}** recursions` : md`Sumbit a value`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":439,"value":"viewof spread = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":438,"value":"$47","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":484,"value":"md`Canvas Tree Version modified from [@tmcw/octree-color-quantization](https://observablehq.com/@tmcw/octree-color-quantization)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"$48","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"class Node {\n constructor(value) {\n this.value = value\n this.left = null\n this.right = null\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":185,"value":"length = d => {\n return Math.sqrt(Math.pow(d.parent.x - d.x, 2) + Math.pow(d.parent.y - d.y, 2))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":393,"value":"binarySearch = (arr, target) => {\n let left = 0\n let right = arr.length - 1\n while (left <= right) {\n const mid = left + Math.floor((right - left) / 2)\n if (arr[mid] === target) {\n return mid\n }\n if (arr[mid] < target) {\n left = mid + 1\n } else {\n right = mid - 1\n }\n }\n return -1\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":126,"value":"import {number, button} from \"@benjaminadk/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"d3 = require('d3@5')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":337,"value":"mutable recurs1 = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":340,"value":"mutable recurs2 = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":460,"value":"mutable recurs3 = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W49","stdlib":"1"}} 44:"$43:body"