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); | ||