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
algorithm:b-tree [2015/08/09 15:12]
will
algorithm:b-tree [2015/08/09 15:30] (current)
will improve insert viz
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