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") { // 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.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 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.children2[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.children2.length > 0) { var foundNode = this.children2[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.children2.length === 0) { nodeToRemove.values.splice(indexToRemove, 1); nodeStack.shift(); nodeToRemove.rebalance(nodeStack); } else { // Find the min value > 'value'. var minStack = nodeToRemove.children2[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.children2[parentIndex-1]; if (leftSibling.values.length > minValues) { this.values.unshift(parent.values[parentIndex-1]); parent.values[parentIndex-1] = leftSibling.values.pop(); if (leftSibling.children2.length > 0) { this.children2.unshift(leftSibling.children2.pop()); } didRotate = true; } } // Rotate left? if (!didRotate && parentIndex < parent.children2.length-1) { var rightSibling = parent.children2[parentIndex+1]; if (rightSibling.values.length > minValues) { this.values.push(parent.values[parentIndex]); parent.values[parentIndex] = rightSibling.values.shift(); if (rightSibling.children2.length > 0) { this.children2.push(rightSibling.children2.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.children2, rightSibling.children2); parent.values.splice(mergeIndex, 1); parent.children2.splice(mergeIndex+1, 1); nodeStack.shift(); parent.rebalance(nodeStack); } } else if (this.values.length === 0 && !parent) { // Eliminate an empty root. this.values = this.children2[0].values; this.children2 = this.children2[0].children2; } }; BTree.prototype.forEach = function (callback) { var numChildren = this.children2.length; if (numChildren > 0) { for (var i=0; i<numChildren; i++) { this.children2[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); for (var i=0;i<10;i++) { btree.insert(Math.floor(Math.random()*100)); } function fixBTree(fixbtree) { if (fixbtree && !(fixbtree instanceof BTree)) { var mybtree = new BTree(fixbtree.order); mybtree.values = fixbtree.values; fixbtree.children2.forEach(function (x) { mybtree.children2.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.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="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 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 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"); 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[0] : 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.1438751626.txt.gz · Last modified: 2015/08/04 22:13 by will