λ B-tree

======= Algorithm ======= <syntax js> function BTree(order) { this.order = order; this.values = []; this.children = []; }; BTree.prototype.insert = function (value) { var m_r = this.insertInternal(value); // Handle root split case. if (typeof m_r === "object") { // If the root(this) split into root,median,right copy this into // into a new `leftSplit` child, and make this into: // leftSplit <- [median] -> rightSplit var leftSplit = new BTree(this.order); leftSplit.values = this.values; leftSplit.children = this.children; this.values = [m_r.median]; this.children = [leftSplit, m_r.rightSplit]; } }; BTree.prototype.insertInternal = 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 m_r = this.children[i].insertInternal(value); if (typeof m_r === "object") { return this.insertAndSplit(m_r.median, m_r.rightSplit); } 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+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.children = this.children.splice(splitIndex); return {leftSplit:this, median:median, rightSplit:rightSplit}; }; // Returns the BTree node and index containing `value` or null if not found. // currently hacked for deletion... BTree.prototype.find = function (value, asStack) { 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`. var foundNode = this.children[i].find(value, asStack); if (asStack && foundNode) foundNode.push([this, i]); return foundNode; } else if (value === this.values[i]) { if (asStack) return [[this, i]]; return [this, i]; } } return null; }; BTree.prototype.findMin = function () { if (this.children.length > 0) { var foundNode = this.children[0].findMin(); foundNode.push([this, 0]); return foundNode; } else { return [[this, 0]]; } }; BTree.prototype.remove = function (value) { var nodeStack = this.find(value, true); if (!nodeStack) return; var nodeToRemove = nodeStack[0][0], indexToRemove = nodeStack[0][1]; if (nodeToRemove.children.length === 0) { nodeToRemove.values.splice(indexToRemove, 1); nodeStack.shift(); nodeToRemove.rebalance(nodeStack); } else { // Find the min value > 'value'. var minStack = nodeToRemove.children[indexToRemove+1].findMin(); var minNode = minStack[0][0]; // Replace 'value' with the next min value. nodeToRemove.values[indexToRemove] = minNode.values.shift(); // Rebalance the tree from the node the min value came from. nodeStack[0][1]++; extendArray(minStack, nodeStack); minStack.shift(); minNode.rebalance(minStack); } }; BTree.prototype.rebalance = function (nodeStack) { var parent, parentIndex; if (nodeStack.length > 0) { parent = nodeStack[0][0], parentIndex = nodeStack[0][1]; } var minValues = Math.floor(this.order/2); if (this.values.length < minValues && parent) { // Rotate right? var didRotate = false; if (parentIndex > 0) { var leftSibling = parent.children[parentIndex-1]; if (leftSibling.values.length > minValues) { this.values.unshift(parent.values[parentIndex-1]); parent.values[parentIndex-1] = leftSibling.values.pop(); if (leftSibling.children.length > 0) { this.children.unshift(leftSibling.children.pop()); } didRotate = true; } } // Rotate left? if (!didRotate && parentIndex < parent.children.length-1) { var rightSibling = parent.children[parentIndex+1]; if (rightSibling.values.length > minValues) { this.values.push(parent.values[parentIndex]); parent.values[parentIndex] = rightSibling.values.shift(); if (rightSibling.children.length > 0) { this.children.push(rightSibling.children.shift()); } didRotate = true; } } // Merge siblings? if (!didRotate) { var mergeIndex; if (leftSibling) { rightSibling = this; mergeIndex = parentIndex-1; } else { leftSibling = this; mergeIndex = parentIndex; } leftSibling.values.push(parent.values[mergeIndex]); extendArray(leftSibling.values, rightSibling.values); extendArray(leftSibling.children, rightSibling.children); parent.values.splice(mergeIndex, 1); parent.children.splice(mergeIndex+1, 1); nodeStack.shift(); parent.rebalance(nodeStack); } } else if (this.values.length === 0 && !parent) { // Eliminate an empty root. this.values = this.children[0].values; this.children = this.children[0].children; } }; BTree.prototype.forEach = function (callback) { var numChildren = this.children.length; if (numChildren > 0) { for (var i=0; i<numChildren; i++) { this.children[i].forEach(callback); if (i<numChildren-1) { callback(this.values[i]); } } } else { // No children case, just pass all the values to `callback`. this.values.forEach(callback); } };</syntax> ======= Support ======= <syntax js> var btree = new BTree(3); function setup() { // Make sure we don't add 'i' to the environment. for (var i=0;i<10;i++) { btree.insert(Math.floor(Math.random()*100)); } } setup(); function fixBTree(fixbtree) { if (fixbtree && !(fixbtree instanceof BTree)) { var mybtree = new BTree(fixbtree.order); mybtree.values = fixbtree.values; fixbtree.children.forEach(function (x) { mybtree.children.push(fixBTree(x)); }); return mybtree; } return fixbtree; } function preRun() { btree = fixBTree(btree); } function extendArray(a, b) { Array.prototype.push.apply(a, b); }</syntax> ======= Tests ======= <syntax js> function insertTest(order, count) { var btree = new BTree(order); var inserted = []; var result = []; for (var i=0;i<count;i++) { var x = Math.floor(Math.random()*100); inserted.push(x); btree.insert(x); } btree.forEach(function(x){result.push(x);}); inserted.sort(function(a,b){return a-b;}); assertEqual(result.length, inserted.length); for (var i=0; i<result.length; i++) { assertEqual(result[i], inserted[i]); } } function testBasic() { insertTest(3, 10); } function testHigherOrder() { insertTest(7, 100); } function testDeletion() { var btree = new BTree(3); var inserted = []; var toDelete = []; var result = []; for (var i=0;i<20;i++) { var x = Math.floor(Math.random()*100); if (Math.random()>0.5) toDelete.push(x); else inserted.push(x); btree.insert(x); } for (var i=0;i<toDelete.length;i++) { btree.remove(toDelete[i]); } btree.forEach(function(x){result.push(x);}); inserted.sort(function(a,b){return a-b;}); assertEqual(result.length, inserted.length); for (var i=0; i<result.length; i++) { assertEqual(result[i], inserted[i]); } } </syntax> ======= Options ======= <syntax js> { "title":"B-tree", "preRunSource": true, "height":"500px", "persistentGlobals": ["btree"] } </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.new tspan { opacity: 0.5; } g.new .node-dot { stroke-dasharray:5,5; } 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); } tspan.index { fill: red; } 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="btreeRemove()">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 d3Node(node) { if (!node) return node; if (!node._d3Node) { node._d3Node = {node:node}; } return node._d3Node; } function inTree(tree, node) { if (tree===node) return true; for (var i=0; i<tree.children.length; i++) { if (inTree(tree.children[i], node)) { return true; } } return false; } function buildTree(x, btree, duration) { var current = 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); if (foundNode && foundNode.length === 2 && foundNode[0].length === 2) foundNode = foundNode[0][0]; else if (foundNode && foundNode.length === 2) foundNode = foundNode[0]; var minNode;// = x.lookupInScope("min") || varInTopFunction(x, "rightMin") || (x.returnedFrom === bst.findMin? x.returnedValue : null); var index = x.lookupInScope("i"); var m_r = varInTopFunction(x, "m_r"); var rightSplit = x.lookupInScope("rightSplit"); var splitSibling = current; if (!rightSplit && x.returnedValue) { rightSplit = x.returnedValue.rightSplit; splitSibling = x.returnedValue.leftSplit; } if (!rightSplit && m_r) { rightSplit = m_r.rightSplit; splitSibling = m_r.leftSplit; } if (inTree(btree, rightSplit)) { rightSplit = null; } foundNode = d3Node(foundNode); minNode = d3Node(minNode); rightSplit = d3Node(rightSplit); splitSibling = d3Node(splitSibling); current = d3Node(current); // size of the diagram var tree = d3.layout.tree() .sort(null) .nodeSize([60, 40]) .children(function(d) { var d3Children = d.node.children.map(d3Node); var currentChildIndex = d3Children.indexOf(splitSibling); if (currentChildIndex !== -1 && rightSplit && d3Children.indexOf(rightSplit) === -1) { d3Children.splice(currentChildIndex+1, 0, rightSplit); } return d3Children; }) .separation(function(a, b) { return (a.parent == b.parent ? 1.1 : 1.3); }); var nodes = tree.nodes(d3Node(btree)); 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;}); linkNodes.attr("visibility", function(d){return (d.target===rightSplit)?"hidden":"visible"}); // 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("new", function(d) {return d===rightSplit;}); /*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)"); function zipData(values, node) { var z = []; values.forEach(function(x){ z.push([x,node]); }); return z; } // Create the text for each node out of 'tspans'. var nodeText = nodes.select("text"); var spans = nodeText.selectAll("tspan") .data(function(nodeD) { return zipData(nodeD.node.values, nodeD.node); }); spans.enter().append("tspan"); spans.text(function(d, i) { return d[0] + (d[1].values.length>i+1? "," : ""); }); spans.classed("index", function(d, i) {return d[1]===current && i===index;}); spans.exit().remove(); // Centre. layoutRoot.transition().duration(duration) .attr("transform", "translate(" + (348/2-d3Node(btree).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 btreeRemove() { 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"); if (btree) { buildTree(x, btree, duration); } } // Disable buttons while running. d3.selectAll("#buttons *").attr('disabled', isRunning? 1 : null); } </script> </body> </html></syntax>