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/02 14:51]
will Rewrite
algorithm:b-tree [2015/08/09 15:30] (current)
will improve insert viz
Line 11: Line 11:
  
 BTree.prototype.insert = function (value) { BTree.prototype.insert = function (value) {
-    var lMR = this.insert2(value);+    var m_r = this.insertInternal(value);
     // Handle root split case.     // Handle root split case.
-    if (typeof ​lMR === "​object"​) {+    if (typeof ​m_r === "​object"​) { 
 +        // If the root(this) split into root,​median,​right copy this into 
 +        // into a new `leftSplit` child, and make this into: 
 +        // leftSplit <- [median] -> rightSplit
         var leftSplit = new BTree(this.order);​         var leftSplit = new BTree(this.order);​
         leftSplit.values = this.values;​         leftSplit.values = this.values;​
         leftSplit.children = this.children;​         leftSplit.children = this.children;​
-        this.values = [lMR[1]]; +        this.values = [m_r.median]; 
-        this.children = [lMR[0]lMR[2]];+        this.children = [leftSplitm_r.rightSplit];
     }     }
 }; };
  
-BTree.prototype.insert2 ​= function (value) {+BTree.prototype.insertInternal ​= function (value) {
  // Is a leaf node?  // Is a leaf node?
     if (this.children.length === 0) {     if (this.children.length === 0) {
Line 31: 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 lMR = this.children[i].insert2(value); +                var m_r = this.children[i].insertInternal(value); 
-                if (typeof ​lMR === "​object"​) { +                if (typeof ​m_r === "​object"​) { 
-                    return this.insertAndSplit(lMR[1]lMR[2]);+                    return this.insertAndSplit(m_r.medianm_r.rightSplit);
                 }                 }
                 break;                 break;
Line 44: Line 47:
 BTree.prototype.insertAndSplit = function (value, newRight) { BTree.prototype.insertAndSplit = function (value, newRight) {
     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]) {
             this.values.splice(i,​ 0, value);             this.values.splice(i,​ 0, value);
             if (this.children.length !== 0) {             if (this.children.length !== 0) {
-                this.children.splice(i,​ 0, newRight);+                this.children.splice(i+1, 0, newRight);
             }             }
             break;             break;
Line 60: Line 63:
  
 BTree.prototype.split = function () { BTree.prototype.split = function () {
-    ​var leftSplit = this;+    ​// Splits a node into three: a this, a median value and a right node.
     var rightSplit = new BTree(this.order);​     var rightSplit = new BTree(this.order);​
-    ​rightSplit.values ​this.values.splice(0, ​Math.ceil(this.values.length / 2));+    ​var splitIndex ​= Math.ceil(this.values.length / 2)
 +    rightSplit.values = this.values.splice(splitIndex);
     var median = this.values.pop();​     var median = this.values.pop();​
 +    rightSplit.children = this.children.splice(splitIndex);​
  
-    ​rightSplit.children = this.children.splice(Math.floor(this.children.length / 2)); +    ​return {leftSplit:this, median:​median, ​rightSplit:rightSplit}
-    /*rightSplit.children.forEach(function(c) { +};
-        c.parent = rightSplit;​ +
-    };*/+
  
-    ​/*if (this.parent) { +// Returns the BTree node and index containing `value` or null if not found. 
-        ​rightSplit.parent ​= this.parent; +// currently hacked for deletion... 
-        //this.parent.insertAndSplit(median);+BTree.prototype.find = function ​(value, asStack) { 
 +    for (var i=0, c=this.values.length;​ i<=c; i++) { 
 +        ​if (i ==c || value < this.values[i]) { 
 +            // Recurse and search the ordered child for `value`. 
 +            var foundNode = this.children[i].find(value, asStack); 
 +            if (asStack && foundNode) foundNode.push([this,​ i]); 
 +            return foundNode;​ 
 +        } 
 +        else if (value === this.values[i]) { 
 +            if (asStack) return [[this, i]]; 
 +            return [this, i]; 
 +        }
     }     }
-    ​/*else { +    return ​null;
-        var leftSplit = new BTree(this.order);​ +
-        leftSplit.values = this.values;​ +
-        leftSplit.children = this.children;​ +
-         +
-        this.values = [median]; +
-        this.children = [leftSplit, rightSplit];​ +
-        leftSplit.parent = this; +
-        rightSplit.parent = this; +
-    }*/ +
-     +
-    ​return ​[leftSplit, median, rightSplit];+
 }; };
  
- +BTree.prototype.findMin ​= function () { 
- +    if (this.children.length > 0{ 
-BTree.prototype.insert3 ​= function (value) { +        var foundNode ​= this.children[0].findMin(); 
-  var destination = this.pickChild(value); +        ​foundNode.push([this, 0]); 
-  if (typeof destination ​=== "​number"​) { +        ​return foundNode
-    this.insert.call(this.children[destination], value); +    ​
-  } else { +    else 
-    this.values.push(value); +        ​return [[this, 0]];
-    ​this.sortNode()+
-    ​if (this.isOverloaded()) ​+
-      this.split();+
     }     }
-  } 
 }; };
  
-BTree.prototype.sortNode ​= function () { +BTree.prototype.remove ​= function (value) { 
-  this.values.sort(function ​(ab) {return a - b; });+    var nodeStack = this.find(value, true); 
 +     
 +    if (!nodeStack) return; 
 +    var nodeToRemove = nodeStack[0][0]indexToRemove = nodeStack[0][1];​ 
 +     
 +    if (nodeToRemove.children.length === 0) { 
 +        nodeToRemove.values.splice(indexToRemove,​ 1); 
 +        nodeStack.shift();​ 
 +        nodeToRemove.rebalance(nodeStack);​ 
 +    ​} 
 +    else { 
 +        // Find the min value > '​value'​. 
 +        var minStack = nodeToRemove.children[indexToRemove+1].findMin(); 
 +        var minNode = minStack[0][0];​ 
 +        // Replace '​value'​ with the next min value. 
 +        nodeToRemove.values[indexToRemove] = minNode.values.shift();​ 
 +        // Rebalance the tree from the node the min value came from. 
 +        nodeStack[0][1]++;​ 
 +        extendArray(minStack,​ nodeStack);​ 
 +        minStack.shift();​ 
 +        minNode.rebalance(minStack);​ 
 +    }
 }; };
  
-BTree.prototype.isOverloaded ​= function () { +BTree.prototype.rebalance ​= function (nodeStack) { 
-  ​return ​this.values.length === this.order;+    var parent, parentIndex;​ 
 +    if (nodeStack.length > 0) { 
 +        parent = nodeStack[0][0],​ parentIndex = nodeStack[0][1];​ 
 +    } 
 +    var minValues = Math.floor(this.order/​2);​ 
 +    if (this.values.length ​< minValues && parent) { 
 +        // Rotate right? 
 +        var didRotate ​false; 
 +        if (parentIndex > 0) { 
 +            var leftSibling ​parent.children[parentIndex-1];​ 
 +            if (leftSibling.values.length > minValues) { 
 +                this.values.unshift(parent.values[parentIndex-1]);​ 
 +                parent.values[parentIndex-1] ​leftSibling.values.pop();​ 
 +                if (leftSibling.children.length > 0) { 
 +                    ​this.children.unshift(leftSibling.children.pop()); 
 +                } 
 +                 
 +                didRotate = true; 
 +            } 
 +        } 
 +        // Rotate left? 
 +        if (!didRotate && parentIndex < parent.children.length-1) { 
 +            var rightSibling = parent.children[parentIndex+1];​ 
 +            if (rightSibling.values.length > minValues) { 
 +                this.values.push(parent.values[parentIndex]);​ 
 +                parent.values[parentIndex] = rightSibling.values.shift();​ 
 +                if (rightSibling.children.length > 0) { 
 +                    this.children.push(rightSibling.children.shift());​ 
 +                } 
 +                didRotate = true; 
 +            } 
 +        } 
 +        // Merge siblings? 
 +        if (!didRotate) { 
 +            var mergeIndex;​ 
 +            if (leftSibling) { 
 +                rightSibling = this; 
 +                mergeIndex = parentIndex-1;​ 
 +            } 
 +            else { 
 +                leftSibling = this; 
 +                mergeIndex = parentIndex;​ 
 +            } 
 +            leftSibling.values.push(parent.values[mergeIndex]);​ 
 +            extendArray(leftSibling.values,​ rightSibling.values);​ 
 +            extendArray(leftSibling.children,​ rightSibling.children);​ 
 +            parent.values.splice(mergeIndex,​ 1); 
 +            parent.children.splice(mergeIndex+1,​ 1); 
 +            nodeStack.shift();​ 
 +            parent.rebalance(nodeStack);​ 
 +        } 
 +    } 
 +    else if (this.values.length === 0 && !parent) { 
 +        // Eliminate an empty root. 
 +        this.values = this.children[0].values;​ 
 +        this.children = this.children[0].children;​ 
 +    }
 }; };
  
-BTree.prototype.split2 ​= function () { +BTree.prototype.forEach ​= function (callback) { 
-  var leftSplit ​new BTree(this.order); +    var numChildren ​= this.children.length; 
-  var rightSplit = new BTree(this.order);​ +    ​if ​(numChildren > 0) { 
- +        for (var i=0; i<numChildren; i++) { 
-  leftSplit.values = this.values.splice(0,​ Math.ceil(this.values.length ​/ 2) - 1)+            this.children[i].forEach(callback)
-  var median = this.values.splice(0, 1)[0]; +            if (i<​numChildren-1) ​
-  ​rightSplit.values = this.values.splice(0);​ +                ​callback(this.values[i]); 
- +            } 
-  ​for (var i = 0; i < this.children.length; i++) { +        }
-    if (i + 1 <= this.children.length / 2) { +
-      ​this.children[i].parent = leftSplit+
-    } else +
-      this.children[i].parent = rightSplit;+
     }     }
-  } +    else { 
-  ​leftSplit.children ​= this.children.splice(0this.children.length / 2); //TODO +        // No children ​casejust pass all the values to `callback`
-  ​rightSplit.children = this.children.splice(0);+        this.values.forEach(callback); 
 +    } 
 +};</​syntax>​
  
-  if (this.parent) { +======= ​Support ======
-    var parent ​this.parent;​ +<syntax js> 
-    leftSplit.parent ​parent; +var btree = new BTree(3);
-    rightSplit.parent ​parent; +
-    var destination ​parent.pickChild(leftSplit.values[0]);​ +
-    parent.children.splice(destination,​ 1, leftSplit, rightSplit);​ +
-    parent.insert(median);​ +
-  } else { +
-    this.values[0] ​median; +
-    this.children ​[leftSplit, rightSplit];​ +
-    leftSplit.parent ​this; +
-    rightSplit.parent ​this; +
-  } +
-};+
  
-BTree.prototype.pickChild = function (value) { +function ​setup() { 
-  var hasOpenSlots = ((this.children.length - 1) - this.values.length) > 0; +    // Make sure we don't add '​i'​ to the environment
-  if (this.children.length !== 0 && !hasOpenSlots) { +    for (var i=0;i<10;i++) { 
-    for (var destination ​= 0; destination ​this.values.lengthdestination++) { +        ​btree.insert(Math.floor(Math.random()*100));
-      ​if ​(value < this.values[destination]+
-        break; +
-      }+
     }     }
-    return destination;​ +
-  ​+setup();
-  ​return null; +
-};+
  
-BTree.prototype.contains = function (value) { +function ​fixBTree(fixbtree) { 
-  var found = false; +    ​if ​(fixbtree && !(fixbtree instanceof BTree)) { 
-  this.traverse(function ​(node) { +        var mybtree ​new BTree(fixbtree.order); 
-    for (var 0i < node.values.lengthi++){ +        mybtree.values ​= fixbtree.values; 
-      found = found || value === node.values[i];+        fixbtree.children.forEach(function (x) { 
 +            ​mybtree.children.push(fixBTree(x));​ 
 +        }); 
 +        return mybtree;
     }     }
-  }); +    ​return ​fixbtree;
-  ​return ​found;+
 } }
  
-BTree.prototype.traverse = function (callback) { +function ​preRun() { 
-  ​callback(this);​ +    ​btree ​fixBTree(btree); 
-  for (var i 0; i < this.children.length;​ i++) { +}
-    this.traverse.call(this.children[i],​ callback); +
-  } +
-};</​syntax>​+
  
-======= Support ======= +function extendArray(a, b) { 
-<syntax js> +    ​Array.prototype.push.apply(a, b); 
-var btree = new BTree(3); +}</​syntax>​
-btree.insert(23);​ +
-btree.insert(44);​ +
-btree.insert(56);​ +
-/*for (var i=0;​i<​10;​i++) { +
-    ​btree.insert(Math.floor(Math.random()*100)); +
-}*/</​syntax>​+
  
 ======= Tests ======= ======= Tests =======
 <syntax js> <syntax js>
-/Unit tests… +function insertTest(order,​ count) { 
-function ​testA() { +    var btree = new BTree(order);​ 
-    if (!ok) { + var inserted = []; 
-        ​throw "Not ok."+ var result = []; 
 +     
 +    for (var i=0;​i<​count;​i++) { 
 +        var x = Math.floor(Math.random()*100); 
 +        ​inserted.push(x);​ 
 +        btree.insert(x);​ 
 +    } 
 +     
 +    btree.forEach(function(x){result.push(x);​});​ 
 +    ​ 
 +    inserted.sort(function(a,​b){return a-b;}); 
 +     
 +    assertEqual(result.length,​ inserted.length);​ 
 +    for (var i=0; i<​result.length;​ i++) { 
 +        assertEqual(result[i],​ inserted[i]);​ 
 +    } 
 +
 + 
 +function testBasic() { 
 +    insertTest(3,​ 10); 
 +
 + 
 +function testHigherOrder() { 
 +    insertTest(7,​ 100); 
 +
 + 
 +function testDeletion() { 
 +    var btree = new BTree(3); 
 + var inserted = []; 
 + var toDelete = []; 
 + var result = []; 
 +     
 +    for (var i=0;​i<​20;​i++) { 
 +        var x = Math.floor(Math.random()*100);​ 
 +        ​if (Math.random()>​0.5) toDelete.push(x);​ 
 +        else inserted.push(x);​ 
 +        btree.insert(x);​ 
 +    } 
 +    for (var i=0;​i<​toDelete.length;​i++) { 
 +        ​btree.remove(toDelete[i]);​ 
 +    } 
 +     
 +    btree.forEach(function(x){result.push(x);​});​ 
 +    inserted.sort(function(a,​b){return a-b;}); 
 +     
 +    assertEqual(result.length,​ inserted.length);​ 
 +    for (var i=0; i<​result.length;​ i++) { 
 +        assertEqual(result[i],​ inserted[i]);​
     }     }
 } }
-*/ 
 </​syntax>​ </​syntax>​
  
Line 200: Line 297:
     "​title":"​B-tree",​     "​title":"​B-tree",​
     "​preRunSource":​ true,     "​preRunSource":​ true,
-    "​height":"​500px"​+    "​height":"​500px"​
 +    "​persistentGlobals":​ ["​btree"​]
 } }
 </​syntax>​ </​syntax>​
Line 226: 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 239: Line 344:
             stroke: black;             stroke: black;
   marker-end:​ url(#​arrow);​   marker-end:​ url(#​arrow);​
 +        }
 +        tspan.index {
 +            fill: red;
         }         }
         input {         input {
Line 244: Line 352:
         }         }
     </​style>​     </​style>​
-<script src="http://​d3js.org/​d3.v3.min.js"></​script>​+<script src="algorithms-lib/​d3.v3.min.js"></​script>​
 </​head>​ </​head>​
  
 <​body>​ <​body>​
   <div style="​padding:​2px"​ id="​buttons">​   <div style="​padding:​2px"​ id="​buttons">​
-    <button onclick="​random()">​Random</​button>​ <button onclick="​insert()">​Insert</​button>​ <button onclick="​bstRemove()">​Remove</​button>​ <button onclick="​find()">​Find</​button>​ <input id="​input"​ value="​26">​+    <button onclick="​random()">​Random</​button>​ <button onclick="​insert()">​Insert</​button>​ <button onclick="​btreeRemove()">​Remove</​button>​ <button onclick="​find()">​Find</​button>​ <input id="​input"​ value="​26">​
   </​div>​   </​div>​
 <div id="​visualisation"></​div>​ <div id="​visualisation"></​div>​
Line 282: Line 390:
 } }
     ​     ​
-function ​buildTree(currentminNodefoundNodetreeData, duration) { +function ​d3Node(node) { 
-//    var height ​Math.min(50020*(1+treeDepth(treeData)));+    if (!node) return node; 
 +    if (!node._d3Node) { 
 +        node._d3Node = {node:​node};​ 
 +    } 
 +    return node._d3Node;​ 
 +
 + 
 +function inTree(treenode) { 
 +    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(xbtree, duration) { 
 +    var current = thisInTopFunction(x,​ btree.split) || thisInTopFunction(x,​ btree.insertInternal) || thisInTopFunction(x,​ btree.insert) || thisInTopFunction(x,​ btree.find);​ 
 +    var foundNode = varInTopFunction(x,​ "​foundNode"​) || (x.returnedFrom === btree.find? x.returnedValue : null); 
 +    if (foundNode && foundNode.length === 2 && foundNode[0].length === 2) foundNode = foundNode[0][0];​ 
 +    else if (foundNode && foundNode.length === 2) foundNode = foundNode[0];​ 
 +    var minNode;// = x.lookupInScope("​min"​) || varInTopFunction(x,​ "​rightMin"​) || (x.returnedFrom === bst.findMin?​ x.returnedValue : null); 
 +    ​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 290: Line 442:
         .nodeSize([60,​ 40])         .nodeSize([60,​ 40])
         .children(function(d) {         .children(function(d) {
-            ​// Add dummy nodes to ensure a binary looking tree+            ​var d3Children = d.node.children.map(d3Node);​ 
-            ​//if (d.left || d.right) { +            var currentChildIndex = d3Children.indexOf(splitSibling);​ 
-            //​ return [d.left? d.left : {}d.right? d.right : {}]+            if (currentChildIndex !== -1 && rightSplit && d3Children.indexOf(rightSplit) === -1) { 
-            ​//+                ​d3Children.splice(currentChildIndex+10, rightSplit)
-            return ​d.children;+            } 
 +            return ​d3Children;
         })         })
     .separation(function(a,​ b) {     .separation(function(a,​ b) {
-          ​return (a.parent == b.parent ? 1 : 1.5);+            ​return (a.parent == b.parent ? 1.1 : 1.3);
         });         });
  
-    var nodes = tree.nodes(treeData);+    var nodes = tree.nodes(d3Node(btree));
     var links = tree.links(nodes);​     var links = tree.links(nodes);​
-    ​ 
-    // Filter to remove dummy nodes. 
-    //nodes = nodes.filter(function(d) {return d.hasOwnProperty("​data"​) && d.data !== undefined;​});​ 
-    //links = links.filter(function(d) {return d.target.hasOwnProperty("​data"​);​});​ 
  
     // Edges between nodes as a <path class="​link"​ />     // Edges between nodes as a <path class="​link"​ />
Line 317: 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 341: Line 491:
     ​     ​
     var nodesUpdate = nodes.transition().duration(duration);​     var nodesUpdate = nodes.transition().duration(duration);​
-    ​/*nodes.classed("​current",​ function(d) {return d===current;}); +    nodes.classed("​current",​ function(d) {return d===current;​});​
-    nodes.classed("​min",​ function(d) {return d===minNode;});+
     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;​});​
     ​     ​
     // Animate setting of current data from minNode.     // Animate setting of current data from minNode.
Line 375: Line 526:
      .attr("​transform",​ "​translate(-30,​-15)"​);​      .attr("​transform",​ "​translate(-30,​-15)"​);​
     ​     ​
-    ​nodes.select("​text"​+    ​function zipData(values, node{ 
-        .text(function(d) { +        ​var z = []; 
-            ​return d.values? d.values.join(",": "?"​;+        values.forEach(function(x){ 
 +            ​z.push([x,node]);
         });         });
 +        return z;
 +    }
 +    ​
 +    // Create the text for each node out of '​tspans'​.
 +    var nodeText = nodes.select("​text"​);​
 +    var spans = nodeText.selectAll("​tspan"​)
 +    .data(function(nodeD) {
 +        return zipData(nodeD.node.values,​ nodeD.node);​
 +          });
 +    spans.enter().append("​tspan"​);​
 +    spans.text(function(d,​ i) {
 +            return d[0] + (d[1].values.length>​i+1?​ ","​ : ""​);​
 +          });
 +    spans.classed("​index",​ function(d, i) {return d[1]===current && i===index;​});​
 +   ​ spans.exit().remove();​
     ​     ​
     // Centre.     // Centre.
     layoutRoot.transition().duration(duration)     layoutRoot.transition().duration(duration)
-    .attr("​transform",​ "​translate("​ + (400/2-treeData.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);​
Line 402: Line 569:
 } }
     ​     ​
-function ​bstRemove() {+function ​btreeRemove() {
     var data = document.getElementById('​input'​).value;​     var data = document.getElementById('​input'​).value;​
     data = parseInt(data);​     data = parseInt(data);​
Line 415: Line 582:
     var data = document.getElementById('​input'​).value;​     var data = document.getElementById('​input'​).value;​
     data = parseInt(data);​     data = parseInt(data);​
-    runScript("​foundNode = bst.find("​+ data +"​)"​);​+    runScript("​foundNode = btree.find("​+ data +"​)"​);​
 } }
  
Line 446: Line 613:
     if (x) {     if (x) {
         var btree = x.lookupInScope("​btree"​);​         var btree = x.lookupInScope("​btree"​);​
-        ​var insertNode;//​ = thisInTopFunction(x, bst.insert|| /​*thisInTopFunction(x,​ bst.remove) ||*/ thisInTopFunction(x,​ bst.find); +        ​if (btree{ 
-        var foundNode;//​ = varInTopFunction(x, "​foundNode"​) || (x.returnedFrom === bst.find? x.returnedValue : null) +            ​buildTree(x, btreeduration); 
-        var minNode;// = x.lookupInScope("​min"​) || varInTopFunction(x"​rightMin"​) || (x.returnedFrom === bst.findMin?​ x.returnedValue : null); +        ​}
-        ​buildTree(insertNode,​ minNode, foundNode, btree, duration);+
     }     }
     ​     ​
algorithm/b-tree.1438552294.txt.gz · Last modified: 2015/08/02 14:51 by will