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/09 15:11]
will children2 -> children
algorithm:b-tree [2015/08/09 15:30]
will improve insert viz
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 393: Line 397:
     return node._d3Node;​     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 401: 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 = d3Node(current);+    var splitSibling = current;
     if (!rightSplit && x.returnedValue) {     if (!rightSplit && x.returnedValue) {
         rightSplit = x.returnedValue.rightSplit;​         rightSplit = x.returnedValue.rightSplit;​
Line 411: Line 425:
         rightSplit = m_r.rightSplit;​         rightSplit = m_r.rightSplit;​
         splitSibling = m_r.leftSplit;​         splitSibling = m_r.leftSplit;​
 +    }
 +    if (inTree(btree,​ rightSplit)) {
 +        rightSplit = null;
     }     }
     ​     ​
Line 418: Line 435:
     splitSibling = d3Node(splitSibling);​     splitSibling = d3Node(splitSibling);​
     current = d3Node(current);​     current = d3Node(current);​
 +    ​
     ​     ​
     // size of the diagram     // size of the diagram
Line 432: Line 450:
         })         })
     .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);
         });         });
  
Line 448: 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
algorithm/b-tree.txt · Last modified: 2015/08/09 15:30 by will