User Tools

Site Tools


This is an old revision of the document!


λ B-tree

======= Algorithm ======= <syntax js> function BTree(order) { this.order = order; this.values = []; this.children2 = []; }; BTree.prototype.insert = function (value) { var m_r = this.insertInternal(value); // Handle root split case. if (typeof m_r === "object") { var leftSplit = new BTree(this.order); leftSplit.values = this.values; leftSplit.children2 = this.children2; this.values = [m_r[0]]; this.children2 = [leftSplit, m_r[1]]; } }; BTree.prototype.insertInternal = function (value) { // Is a leaf node? if (this.children2.length === 0) { return this.insertAndSplit(value); } else { // Pick a child to insert into. for (var i=0, c=this.values.length; i<=c; i++) { if (i === c || value < this.values[i]) { var m_r = this.children2[i].insertInternal(value); if (typeof m_r === "object") { return this.insertAndSplit(m_r[0], m_r[1]); } break; } } } return false; }; BTree.prototype.insertAndSplit = function (value, newRight) { for (var i=0, c=this.values.length; i<=c; i++) { if (i === c || value < this.values[i]) { this.values.splice(i, 0, value); if (this.children2.length !== 0) { this.children2.splice(i+1, 0, newRight); } break; } } if (this.values.length >= this.order) { return this.split(); } return false; }; BTree.prototype.split = function () { // Splits a node into three: a this, a median value and a right node. var rightSplit = new BTree(this.order); var splitIndex = Math.ceil(this.values.length / 2); rightSplit.values = this.values.splice(splitIndex); var median = this.values.pop(); rightSplit.children2 = this.children2.splice(splitIndex); return [median, rightSplit]; }; // Returns the BTree node that contains 'value' or null if 'value' is not found BTree.prototype.find = function (value) { for (var i=0, c=this.values.length; i<=c; i++) { if (i === c || value < this.values[i]) { // Recurse and search the ordered child for 'value'. return this.children2[i].find(value); } else if (value === this.values[i]) { return this; } } return null; }; BTree.prototype.forEach = function (callback) { callback(this); for (var i=0, c=this.children.length; i<c; i++) { this.children[i].forEach(callback); } };</syntax> ======= Support ======= <syntax js> var btree = new BTree(3); /*btree.insert(23); btree.insert(44); btree.insert(56);*/ for (var i=0;i<10;i++) { btree.insert(Math.floor(Math.random()*100)); }</syntax> ======= Tests ======= <syntax js> /* Unit tests… function testA() { if (!ok) { throw "Not ok." } } */ </syntax> ======= Options ======= <syntax js> { "title":"B-tree", "preRunSource": true, "height":"500px" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <style> g.node { font-family: Helvetica, sans-serif; font-size: 13px; font-weight: bold; } rect.node-dot { fill: white; stroke: red; stroke-width: 1px; } g.current rect.node-dot { fill: rgb(3, 166, 249); stroke: blue; } g.min rect.node-dot { fill: rgb(249, 3, 104); stroke: blue; } g.found rect.node-dot { fill: rgb(249, 197, 3); stroke: rgb(255, 143, 0); } path.link { fill: none; stroke: gray; } path.move-data { fill: none; stroke: black; marker-end: url(#arrow); } input { width: 50px; } </style> <script src="algorithms-lib/d3.v3.min.js"></script> </head> <body> <div style="padding:2px" id="buttons"> <button onclick="random()">Random</button> <button onclick="insert()">Insert</button> <button onclick="bstRemove()">Remove</button> <button onclick="find()">Find</button> <input id="input" value="26"> </div> <div id="visualisation"></div> <script type="text/javascript"> var layoutRoot = d3.select("#visualisation") .append("svg").attr("width", 400).attr("height", 400) .append("g") .attr("class", "container") .attr("transform", "translate(20,20)"); layoutRoot.append("svg:defs").append("svg:marker") .attr("id", "arrow") .attr("viewBox", "0 0 10 10") .attr("refX", 0) .attr("refY", 5) .attr("markerWidth", 6) .attr("markerHeight", 6) .attr("orient", "auto") .append("svg:path") .attr("d", "M0,0 L10,5 L0,10 z"); function treeDepth(tree) { if (!tree) return 0; return 1+Math.max(treeDepth(tree.left), treeDepth(tree.right)); } var idCount = 0; function id(obj) { if (!obj.hasOwnProperty("id")) obj.id = idCount++; return obj.id; } function buildTree(current, minNode, foundNode, treeData, duration) { // var height = Math.min(500, 20*(1+treeDepth(treeData))); // size of the diagram var tree = d3.layout.tree() .sort(null) .nodeSize([60, 40]) .children(function(d) { return d.children2; }) .separation(function(a, b) { return (a.parent == b.parent ? 1.1 : 1.3); }); var nodes = tree.nodes(treeData); var links = tree.links(nodes); // Edges between nodes as a <path class="link" /> var linkNodes = layoutRoot.selectAll("path.link") .data(links, function(d) {return id(d.target);}); linkNodes.enter() .insert("path", "g") .attr("class", "link"); linkNodes.transition().duration(duration) .attr("d", function(a) {return "M"+a.source.x+","+a.source.y+"L"+a.target.x+","+a.target.y;}); // nodes var nodes = layoutRoot.selectAll("g.node") .data(nodes, function(d) {return id(d);}); var newNodes = nodes.enter() .append("g") .attr("class", "node") .attr("transform", function(d) { return "translate(" + d.x + "," + d.y + ")"; }) .style("opacity", 0); newNodes.append("rect") .attr("class", "node-dot") .attr("rx", 5) .attr("ry", 5) .attr("width", 0) .attr("height", 0); // Start small. newNodes.append("text") .attr("dy", 4) .attr("text-anchor", "middle"); var nodesUpdate = nodes.transition().duration(duration); nodes.classed("current", function(d) {return d===current;}); nodes.classed("found", function(d) {return d===foundNode;}); /*nodes.classed("min", function(d) {return d===minNode;}); // Animate setting of current data from minNode. if (foundNode && minNode && foundNode.text !== foundNode.data && foundNode.data === minNode.data) { var dx = foundNode.x-minNode.x; var dy = foundNode.y-minNode.y; var len = Math.sqrt(dx*dx+dy*dy); layoutRoot.append("path") .attr("class", "move-data") .attr("stroke-width", 2) .attr("opacity", 1) .attr("d", "M"+ (minNode.x+dx/len*10)+","+(minNode.y+dy/len*10)+"L"+(minNode.x+dx/len*10)+","+(minNode.y+dy/len*10)) .transition().duration(duration) .attr("d", "M"+ (minNode.x+dx/len*10)+","+(minNode.y+dy/len*10)+"L"+(foundNode.x-dx/len*20)+","+(foundNode.y-dy/len*20)); } else { layoutRoot.select("path.move-data") .transition().duration(duration) .attr("opacity", 0) .remove(); }*/ nodesUpdate.attr("transform", function(d) { return "translate(" + d.x + "," + d.y + ")"; }) .style("opacity", 1); nodesUpdate.select("rect") .attr("width", 60) .attr("height", 30) .attr("transform", "translate(-30,-15)"); nodes.select("text") .text(function(d) { return d.values? d.values.join(",") : "?"; }); // Centre. layoutRoot.transition().duration(duration) .attr("transform", "translate(" + (348/2-treeData.x+0.5) + ",20.5)"); var nodesExit = nodes.exit().transition().duration(duration); nodesExit.remove(); nodesExit.select("circle").attr("r", 0); nodesExit.select("text").attr("fill-opacity", 0); linkNodes.exit().remove(); } function globals() { // Clear out 'foundNode' global. return {"foundNode":undefined}; } function insert() { var data = document.getElementById('input').value; data = parseInt(data); runScript("btree.insert("+ data +")"); } function bstRemove() { var data = document.getElementById('input').value; data = parseInt(data); runScript("btree.remove("+ data +")"); } function random() { reset(); } function find() { var data = document.getElementById('input').value; data = parseInt(data); runScript("foundNode = btree.find("+ data +")"); } function thisInTopFunction(x, fn) { var fnThis = null; for (var i=x.stack.length-1; i>=0; i--) { if (x.stack[i].function === fn) { fnThis = x.stack[i].thisObject; break; } } return fnThis; } function varInTopFunction(x, v) { var fnVar = null; for (var i=x.stack.length-1; i>=0; i--) { fnVar = x.stack[i].lookupInScope(v); if (fnVar) { break; } } return fnVar; } function update(n, x, isRunning, duration, prev) { if (duration < 0) { return; // State-less visualisation. } if (x) { var btree = x.lookupInScope("btree"); var insertNode = thisInTopFunction(x, btree.split) || thisInTopFunction(x, btree.insertInternal) || thisInTopFunction(x, btree.insert) || thisInTopFunction(x, btree.find); var foundNode = varInTopFunction(x, "foundNode") || (x.returnedFrom === btree.find? x.returnedValue : null) var minNode;// = x.lookupInScope("min") || varInTopFunction(x, "rightMin") || (x.returnedFrom === bst.findMin? x.returnedValue : null); if(btree)buildTree(insertNode, minNode, foundNode, btree, duration); } // Disable buttons while running. d3.selectAll("#buttons *").attr('disabled', isRunning? 1 : null); } </script> </body> </html></syntax>

algorithm/b-tree.1438659461.txt.gz · Last modified: 2015/08/03 20:37 by will