User Tools

Site Tools


Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
algorithm:b-tree [2015/08/06 21:01]
will Index highlighting.
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[0]]; +        this.values = [m_r.median]; 
-        this.children2 ​= [leftSplit, m_r[1]];+        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[0], m_r[1]);+                    return this.insertAndSplit(m_r.median, m_r.rightSplit);
                 }                 }
                 break;                 break;
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 ​[median, 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 324: Line 324:
             fill: rgb(249, 3, 104);             fill: rgb(249, 3, 104);
             stroke: blue;             stroke: blue;
 +        }
 +        g.new tspan {
 +            opacity: 0.5;
 +        }
 +        g.new .node-dot
 +        {
 +            stroke-dasharray:​5,​5;​
         }         }
         g.found rect.node-dot {         g.found rect.node-dot {
Line 383: 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 390: 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 = 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     // size of the diagram
Line 396: Line 442:
         .nodeSize([60,​ 40])         .nodeSize([60,​ 40])
         .children(function(d) {         .children(function(d) {
-            ​return ​d.children2;+            ​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) {     .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 415: 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.target===rightSplit)?"​hidden":"​visible"​});​
  
     // nodes     // nodes
Line 441: Line 493:
     nodes.classed("​current",​ function(d) {return d===current;​});​     nodes.classed("​current",​ function(d) {return d===current;​});​
     nodes.classed("​found",​ function(d) {return d===foundNode;​});​     nodes.classed("​found",​ function(d) {return d===foundNode;​});​
 +    nodes.classed("​new",​ function(d) {return d===rightSplit;​});​
     /​*nodes.classed("​min",​ function(d) {return d===minNode;​});​     /​*nodes.classed("​min",​ function(d) {return d===minNode;​});​
     ​     ​
Line 485: 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 496: 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);​
algorithm/b-tree.1438920090.txt.gz · Last modified: 2015/08/06 21:01 by will