# Algorithm Wiki

### Site Tools

This is an old revision of the document!

# λ B-tree

======= Algorithm ======= <syntax js> function BTree(order) { this.order = order; this.values = []; this.children = []; }; BTree.prototype.insert = function (value) { var lMR = this.insert2(value); // Handle root split case. if (typeof lMR === "object") { var leftSplit = new BTree(this.order); leftSplit.values = this.values; leftSplit.children = this.children; this.values = [lMR[1]]; this.children = [lMR[0], lMR[2]]; } }; BTree.prototype.insert2 = function (value) { // Is a leaf node? if (this.children.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 lMR = this.children[i].insert2(value); if (typeof lMR === "object") { return this.insertAndSplit(lMR[1], lMR[2]); } 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.children.length !== 0) { this.children.splice(i, 0, newRight); } break; } } if (this.values.length >= this.order) { return this.split(); } return false; }; BTree.prototype.split = function () { var leftSplit = this; var rightSplit = new BTree(this.order); rightSplit.values = this.values.splice(0, Math.ceil(this.values.length / 2)); var median = this.values.pop(); rightSplit.children = this.children.splice(Math.floor(this.children.length / 2)); /*rightSplit.children.forEach(function(c) { c.parent = rightSplit; };*/ /*if (this.parent) { rightSplit.parent = this.parent; //this.parent.insertAndSplit(median); } /*else { var leftSplit = new BTree(this.order); leftSplit.values = this.values; leftSplit.children = this.children; this.values = [median]; this.children = [leftSplit, rightSplit]; leftSplit.parent = this; rightSplit.parent = this; }*/ return [leftSplit, median, rightSplit]; }; BTree.prototype.insert3 = function (value) { var destination = this.pickChild(value); if (typeof destination === "number") { this.insert.call(this.children[destination], value); } else { this.values.push(value); this.sortNode(); if (this.isOverloaded()) { this.split(); } } }; BTree.prototype.sortNode = function () { this.values.sort(function (a, b) {return a - b; }); }; BTree.prototype.isOverloaded = function () { return this.values.length === this.order; }; BTree.prototype.split2 = function () { var leftSplit = new BTree(this.order); var rightSplit = new BTree(this.order); leftSplit.values = this.values.splice(0, Math.ceil(this.values.length / 2) - 1); var median = this.values.splice(0, 1)[0]; rightSplit.values = this.values.splice(0); for (var i = 0; i < this.children.length; i++) { if (i + 1 <= this.children.length / 2) { this.children[i].parent = leftSplit; } else { this.children[i].parent = rightSplit; } } leftSplit.children = this.children.splice(0, this.children.length / 2); //TODO rightSplit.children = this.children.splice(0); if (this.parent) { var parent = this.parent; leftSplit.parent = parent; rightSplit.parent = parent; var destination = parent.pickChild(leftSplit.values[0]); parent.children.splice(destination, 1, leftSplit, rightSplit); parent.insert(median); } else { this.values[0] = median; this.children = [leftSplit, rightSplit]; leftSplit.parent = this; rightSplit.parent = this; } }; BTree.prototype.pickChild = function (value) { var hasOpenSlots = ((this.children.length - 1) - this.values.length) > 0; if (this.children.length !== 0 && !hasOpenSlots) { for (var destination = 0; destination < this.values.length; destination++) { if (value < this.values[destination]) { break; } } return destination; } return null; }; BTree.prototype.contains = function (value) { var found = false; this.traverse(function (node) { for (var i = 0; i < node.values.length; i++){ found = found || value === node.values[i]; } }); return found; } BTree.prototype.traverse = function (callback) { callback(this); for (var i = 0; i < this.children.length; i++) { this.traverse.call(this.children[i], callback); } }; var btree = new BTree(3); btree.insert(23); btree.insert(44); btree.insert(56);</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", "preRunSource1": 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) { // Add dummy nodes to ensure a binary looking tree. //if (d.left || d.right) { // return [d.left? d.left : {}, d.right? d.right : {}]; //} return d.children; }) .separation(function(a, b) { return (a.parent == b.parent ? 1 : 1.5); }); var nodes = tree.nodes(treeData); var links = tree.links(nodes); // Filter to remove dummy nodes. //nodes = nodes.filter(function(d) {return d.hasOwnProperty("data") && d.data !== undefined;}); //links = links.filter(function(d) {return d.target.hasOwnProperty("data");}); // 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("min", function(d) {return d===minNode;}); nodes.classed("found", function(d) {return d===foundNode;}); // 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(" + (400/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 = bst.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, bst.insert) || /*thisInTopFunction(x, bst.remove) ||*/ thisInTopFunction(x, bst.find); var foundNode;// = varInTopFunction(x, "foundNode") || (x.returnedFrom === bst.find? x.returnedValue : null) var minNode;// = x.lookupInScope("min") || varInTopFunction(x, "rightMin") || (x.returnedFrom === bst.findMin? x.returnedValue : null); buildTree(insertNode, minNode, foundNode, btree, duration); } // Disable buttons while running. d3.selectAll("#buttons *").attr('disabled', isRunning? 1 : null); } </script> </body> </html></syntax>