This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
algorithm:b-tree [2015/08/08 15:26] will Better new nodes. |
algorithm:b-tree [2015/08/09 15:30] (current) will improve insert viz |
||
---|---|---|---|
Line 7: | Line 7: | ||
this.order = order; | this.order = order; | ||
this.values = []; | this.values = []; | ||
- | this.children2 = []; | + | this.children = []; |
}; | }; | ||
Line 19: | Line 19: | ||
var leftSplit = new BTree(this.order); | var leftSplit = new BTree(this.order); | ||
leftSplit.values = this.values; | leftSplit.values = this.values; | ||
- | leftSplit.children2 = this.children2; | + | leftSplit.children = this.children; |
this.values = [m_r.median]; | this.values = [m_r.median]; | ||
- | this.children2 = [leftSplit, m_r.rightSplit]; | + | this.children = [leftSplit, m_r.rightSplit]; |
} | } | ||
}; | }; | ||
Line 27: | Line 27: | ||
BTree.prototype.insertInternal = function (value) { | BTree.prototype.insertInternal = function (value) { | ||
// Is a leaf node? | // Is a leaf node? | ||
- | if (this.children2.length === 0) { | + | if (this.children.length === 0) { |
return this.insertAndSplit(value); | return this.insertAndSplit(value); | ||
} | } | ||
Line 34: | Line 34: | ||
for (var i=0, c=this.values.length; i<=c; i++) { | for (var i=0, c=this.values.length; i<=c; i++) { | ||
if (i === c || value < this.values[i]) { | if (i === c || value < this.values[i]) { | ||
- | var m_r = this.children2[i].insertInternal(value); | + | var m_r = this.children[i].insertInternal(value); |
if (typeof m_r === "object") { | if (typeof m_r === "object") { | ||
return this.insertAndSplit(m_r.median, m_r.rightSplit); | return this.insertAndSplit(m_r.median, m_r.rightSplit); | ||
Line 49: | Line 49: | ||
if (i === c || value < this.values[i]) { | if (i === c || value < this.values[i]) { | ||
this.values.splice(i, 0, value); | this.values.splice(i, 0, value); | ||
- | if (this.children2.length !== 0) { | + | if (this.children.length !== 0) { |
- | this.children2.splice(i+1, 0, newRight); | + | this.children.splice(i+1, 0, newRight); |
} | } | ||
break; | break; | ||
Line 68: | Line 68: | ||
rightSplit.values = this.values.splice(splitIndex); | rightSplit.values = this.values.splice(splitIndex); | ||
var median = this.values.pop(); | var median = this.values.pop(); | ||
- | rightSplit.children2 = this.children2.splice(splitIndex); | + | rightSplit.children = this.children.splice(splitIndex); |
return {leftSplit:this, median:median, rightSplit:rightSplit}; | return {leftSplit:this, median:median, rightSplit:rightSplit}; | ||
Line 79: | Line 79: | ||
if (i === c || value < this.values[i]) { | if (i === c || value < this.values[i]) { | ||
// Recurse and search the ordered child for `value`. | // Recurse and search the ordered child for `value`. | ||
- | var foundNode = this.children2[i].find(value, asStack); | + | var foundNode = this.children[i].find(value, asStack); |
if (asStack && foundNode) foundNode.push([this, i]); | if (asStack && foundNode) foundNode.push([this, i]); | ||
return foundNode; | return foundNode; | ||
Line 92: | Line 92: | ||
BTree.prototype.findMin = function () { | BTree.prototype.findMin = function () { | ||
- | if (this.children2.length > 0) { | + | if (this.children.length > 0) { |
- | var foundNode = this.children2[0].findMin(); | + | var foundNode = this.children[0].findMin(); |
foundNode.push([this, 0]); | foundNode.push([this, 0]); | ||
return foundNode; | return foundNode; | ||
Line 108: | Line 108: | ||
var nodeToRemove = nodeStack[0][0], indexToRemove = nodeStack[0][1]; | var nodeToRemove = nodeStack[0][0], indexToRemove = nodeStack[0][1]; | ||
| | ||
- | if (nodeToRemove.children2.length === 0) { | + | if (nodeToRemove.children.length === 0) { |
nodeToRemove.values.splice(indexToRemove, 1); | nodeToRemove.values.splice(indexToRemove, 1); | ||
nodeStack.shift(); | nodeStack.shift(); | ||
Line 115: | Line 115: | ||
else { | else { | ||
// Find the min value > 'value'. | // Find the min value > 'value'. | ||
- | var minStack = nodeToRemove.children2[indexToRemove+1].findMin(); | + | var minStack = nodeToRemove.children[indexToRemove+1].findMin(); |
var minNode = minStack[0][0]; | var minNode = minStack[0][0]; | ||
// Replace 'value' with the next min value. | // Replace 'value' with the next min value. | ||
Line 137: | Line 137: | ||
var didRotate = false; | var didRotate = false; | ||
if (parentIndex > 0) { | if (parentIndex > 0) { | ||
- | var leftSibling = parent.children2[parentIndex-1]; | + | var leftSibling = parent.children[parentIndex-1]; |
if (leftSibling.values.length > minValues) { | if (leftSibling.values.length > minValues) { | ||
this.values.unshift(parent.values[parentIndex-1]); | this.values.unshift(parent.values[parentIndex-1]); | ||
parent.values[parentIndex-1] = leftSibling.values.pop(); | parent.values[parentIndex-1] = leftSibling.values.pop(); | ||
- | if (leftSibling.children2.length > 0) { | + | if (leftSibling.children.length > 0) { |
- | this.children2.unshift(leftSibling.children2.pop()); | + | this.children.unshift(leftSibling.children.pop()); |
} | } | ||
| | ||
Line 149: | Line 149: | ||
} | } | ||
// Rotate left? | // Rotate left? | ||
- | if (!didRotate && parentIndex < parent.children2.length-1) { | + | if (!didRotate && parentIndex < parent.children.length-1) { |
- | var rightSibling = parent.children2[parentIndex+1]; | + | var rightSibling = parent.children[parentIndex+1]; |
if (rightSibling.values.length > minValues) { | if (rightSibling.values.length > minValues) { | ||
this.values.push(parent.values[parentIndex]); | this.values.push(parent.values[parentIndex]); | ||
parent.values[parentIndex] = rightSibling.values.shift(); | parent.values[parentIndex] = rightSibling.values.shift(); | ||
- | if (rightSibling.children2.length > 0) { | + | if (rightSibling.children.length > 0) { |
- | this.children2.push(rightSibling.children2.shift()); | + | this.children.push(rightSibling.children.shift()); |
} | } | ||
didRotate = true; | didRotate = true; | ||
Line 173: | Line 173: | ||
leftSibling.values.push(parent.values[mergeIndex]); | leftSibling.values.push(parent.values[mergeIndex]); | ||
extendArray(leftSibling.values, rightSibling.values); | extendArray(leftSibling.values, rightSibling.values); | ||
- | extendArray(leftSibling.children2, rightSibling.children2); | + | extendArray(leftSibling.children, rightSibling.children); |
parent.values.splice(mergeIndex, 1); | parent.values.splice(mergeIndex, 1); | ||
- | parent.children2.splice(mergeIndex+1, 1); | + | parent.children.splice(mergeIndex+1, 1); |
nodeStack.shift(); | nodeStack.shift(); | ||
parent.rebalance(nodeStack); | parent.rebalance(nodeStack); | ||
Line 182: | Line 182: | ||
else if (this.values.length === 0 && !parent) { | else if (this.values.length === 0 && !parent) { | ||
// Eliminate an empty root. | // Eliminate an empty root. | ||
- | this.values = this.children2[0].values; | + | this.values = this.children[0].values; |
- | this.children2 = this.children2[0].children2; | + | this.children = this.children[0].children; |
} | } | ||
}; | }; | ||
BTree.prototype.forEach = function (callback) { | BTree.prototype.forEach = function (callback) { | ||
- | var numChildren = this.children2.length; | + | var numChildren = this.children.length; |
if (numChildren > 0) { | if (numChildren > 0) { | ||
for (var i=0; i<numChildren; i++) { | for (var i=0; i<numChildren; i++) { | ||
- | this.children2[i].forEach(callback); | + | this.children[i].forEach(callback); |
if (i<numChildren-1) { | if (i<numChildren-1) { | ||
callback(this.values[i]); | callback(this.values[i]); | ||
Line 219: | Line 219: | ||
var mybtree = new BTree(fixbtree.order); | var mybtree = new BTree(fixbtree.order); | ||
mybtree.values = fixbtree.values; | mybtree.values = fixbtree.values; | ||
- | fixbtree.children2.forEach(function (x) { | + | fixbtree.children.forEach(function (x) { |
- | mybtree.children2.push(fixBTree(x)); | + | mybtree.children.push(fixBTree(x)); |
}); | }); | ||
return mybtree; | return mybtree; | ||
Line 327: | Line 327: | ||
g.new tspan { | g.new tspan { | ||
opacity: 0.5; | opacity: 0.5; | ||
+ | } | ||
+ | g.new .node-dot | ||
+ | { | ||
+ | stroke-dasharray:5,5; | ||
} | } | ||
g.found rect.node-dot { | g.found rect.node-dot { | ||
Line 386: | Line 390: | ||
} | } | ||
| | ||
+ | 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) { | function buildTree(x, btree, duration) { | ||
var current = thisInTopFunction(x, btree.split) || thisInTopFunction(x, btree.insertInternal) || thisInTopFunction(x, btree.insert) || thisInTopFunction(x, btree.find); | var current = thisInTopFunction(x, btree.split) || thisInTopFunction(x, btree.insertInternal) || thisInTopFunction(x, btree.insert) || thisInTopFunction(x, btree.find); | ||
Line 393: | Line 415: | ||
var minNode;// = x.lookupInScope("min") || varInTopFunction(x, "rightMin") || (x.returnedFrom === bst.findMin? x.returnedValue : null); | var minNode;// = x.lookupInScope("min") || varInTopFunction(x, "rightMin") || (x.returnedFrom === bst.findMin? x.returnedValue : null); | ||
var index = x.lookupInScope("i"); | var index = x.lookupInScope("i"); | ||
- | var m_r = x.lookupInScope("m_r"); | + | var m_r = varInTopFunction(x, "m_r"); |
var rightSplit = x.lookupInScope("rightSplit"); | var rightSplit = x.lookupInScope("rightSplit"); | ||
var splitSibling = current; | var splitSibling = current; | ||
Line 404: | Line 426: | ||
splitSibling = m_r.leftSplit; | 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 | // size of the diagram | ||
Line 410: | Line 442: | ||
.nodeSize([60, 40]) | .nodeSize([60, 40]) | ||
.children(function(d) { | .children(function(d) { | ||
- | var children = d.children2; | + | var d3Children = d.node.children.map(d3Node); |
- | var currentChildIndex = children.indexOf(splitSibling); | + | var currentChildIndex = d3Children.indexOf(splitSibling); |
- | if (currentChildIndex !== -1 && rightSplit && children.indexOf(rightSplit) === -1) { | + | if (currentChildIndex !== -1 && rightSplit && d3Children.indexOf(rightSplit) === -1) { |
- | children = children.slice(); | + | d3Children.splice(currentChildIndex+1, 0, rightSplit); |
- | children.splice(currentChildIndex+1, 0, rightSplit); | + | |
} | } | ||
- | return children; | + | return d3Children; |
}) | }) | ||
.separation(function(a, b) { | .separation(function(a, b) { | ||
- | return (a.parent == b.parent ? 1.1 : 1.3); | + | return (a.parent == b.parent ? 1.1 : 1.3); |
}); | }); | ||
- | var nodes = tree.nodes(btree); | + | var nodes = tree.nodes(d3Node(btree)); |
var links = tree.links(nodes); | var links = tree.links(nodes); | ||
Line 435: | Line 466: | ||
linkNodes.transition().duration(duration) | linkNodes.transition().duration(duration) | ||
.attr("d", function(a) {return "M"+a.source.x+","+a.source.y+"L"+a.target.x+","+a.target.y;}); | .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.source===rightSplit || d.target === rightSplit)?"hidden":"visible"}); | + | linkNodes.attr("visibility", function(d){return (d.target===rightSplit)?"hidden":"visible"}); |
// nodes | // nodes | ||
Line 507: | Line 538: | ||
var spans = nodeText.selectAll("tspan") | var spans = nodeText.selectAll("tspan") | ||
.data(function(nodeD) { | .data(function(nodeD) { | ||
- | return zipData(nodeD.values, nodeD); | + | return zipData(nodeD.node.values, nodeD.node); |
}); | }); | ||
spans.enter().append("tspan"); | spans.enter().append("tspan"); | ||
Line 518: | Line 549: | ||
// Centre. | // Centre. | ||
layoutRoot.transition().duration(duration) | layoutRoot.transition().duration(duration) | ||
- | .attr("transform", "translate(" + (348/2-btree.x+0.5) + ",20.5)"); | + | .attr("transform", "translate(" + (348/2-d3Node(btree).x+0.5) + ",20.5)"); |
| | ||
var nodesExit = nodes.exit().transition().duration(duration); | var nodesExit = nodes.exit().transition().duration(duration); |