User Tools

Site Tools


This is an old revision of the document!


λ B-tree

======= Algorithm ======= <syntax js> // https://github.com/dsernst/data-structures/blob/master/sprint-two/src/bTree.js var BTree = function (order) { this.order = order; this.values = []; this.children = []; }; BTree.prototype.insert = 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.split = 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); } };</syntax> ======= Support ======= <syntax js> var btree = new BTree(); 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", "height":"500px" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <script> /* Optional functions function globals() { return {}; } function args() { return null; } */ function update(n, x, isRunning, duration, prev) { if (duration < 0) { return; // State-less visualisation. } var out = x.lookupInScope("out"); document.body.innerHTML = "out = "+JSON.stringify(out); } </script> </head> <body> </body> </html> </syntax>

algorithm/b-tree.1438416086.txt.gz · Last modified: 2015/08/01 01:01 by will