User Tools

Site Tools


Differences

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

Link to this comparison view

Next revision
Previous revision
algorithm:b-tree [2015/08/01 01:01]
will created
algorithm:b-tree [2015/08/09 15:30] (current)
will improve insert viz
Line 4: Line 4:
 ======= Algorithm ======= ======= Algorithm =======
 <syntax js> <syntax js>
-// https://​github.com/​dsernst/​data-structures/​blob/​master/​sprint-two/​src/​bTree.js +function ​BTree(order) { 
-var BTree = function ​(order) { +    this.order = order; 
-  this.order = order; +    this.values = []; 
-  this.values = []; +    this.children = [];
-  this.children = [];+
 }; };
  
 BTree.prototype.insert = function (value) { BTree.prototype.insert = function (value) {
-  ​var destination ​= this.pickChild(value); +    ​var m_r = this.insertInternal(value); 
-  if (typeof ​destination ​=== "number") { +    // Handle root split case. 
-    ​this.insert.call(this.children[destination], value); +    ​if (typeof ​m_r === "object") { 
-  } else { +        // If the root(this) split into root,​median,​right copy this into 
-    this.values.push(value)+        // into a new `leftSplit` child, and make this into: 
-    this.sortNode()+        // leftSplit <- [median-> rightSplit 
-    if (this.isOverloaded()) { +        var leftSplit = new BTree(this.order); 
-      this.split();+        ​leftSplit.values ​= this.values
 +        ​leftSplit.children = this.children
 +        this.values = [m_r.median];​ 
 +        this.children = [leftSplit, m_r.rightSplit];
     }     }
-  } 
 }; };
  
-BTree.prototype.sortNode ​= function () { +BTree.prototype.insertInternal ​= function (value) { 
-  this.values.sort(function ​(a, b) {return ​a - b; });+ // Is a leaf node? 
 +    if (this.children.length === 0) { 
 +        return this.insertAndSplit(value); 
 +    } 
 +    else { 
 +        // Pick child to insert into. 
 +        for (var i=0c=this.values.length;​ i<=c; i++) { 
 +            if (i === c || value < this.values[i]) { 
 +                var m_r = this.children[i].insertInternal(value);​ 
 +                if (typeof m_r === "​object"​) { 
 +                    ​return ​this.insertAndSplit(m_r.median,​ m_r.rightSplit); 
 +                ​} 
 +                break; 
 +            } 
 +        } 
 +    } 
 +    return false;
 }; };
  
-BTree.prototype.isOverloaded ​= function () { +BTree.prototype.insertAndSplit ​= function (value, newRight) { 
-  ​return ​this.values.length === this.order;+    for (var i=0, c=this.values.length; i<=c; i++) { 
 +        if (i === c || value < this.values[i]) { 
 +            this.values.splice(i,​ 0, value); 
 +            if (this.children.length !== 0) { 
 +                this.children.splice(i+1,​ 0, newRight);​ 
 +            } 
 +            break; 
 +        } 
 +    } 
 +     
 +    if (this.values.length >= this.order) { 
 +        return this.split();​ 
 +    } 
 +    return false;
 }; };
  
 BTree.prototype.split = function () { BTree.prototype.split = function () {
-  ​var leftSplit ​= new BTree(this.order);​ +    // 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);​ 
 +    var splitIndex = Math.ceil(this.values.length / 2); 
 +    ​rightSplit.values ​this.values.splice(splitIndex);​ 
 +    var median = this.values.pop();​ 
 +    rightSplit.children = this.children.splice(splitIndex);
  
-  ​leftSplit.values = this.values.splice(0Math.ceil(this.values.length / 2) - 1); +    return {leftSplit:this, median:medianrightSplit:​rightSplit}
-  var median ​= this.values.splice(01)[0]+};
-  ​rightSplit.values = this.values.splice(0);+
  
-  ​for (var i = 0; i < this.children.length; i++) { +// Returns the BTree node and index containing `value` or null if not found. 
-    if (i + 1 <= this.children.length / 2) { +// currently hacked for deletion... 
-      this.children[i].parent = leftSplit+BTree.prototype.find = function (value, asStack) { 
-    } else { +    ​for (var i=0, c=this.values.length; i<=c; i++) { 
-      this.children[i].parent = rightSplit;+        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]; 
 +        }
     }     }
-  } +    return null
-  leftSplit.children = this.children.splice(0,​ this.children.length / 2)//TODO +};
-  ​rightSplit.children = this.children.splice(0);+
  
-  if (this.parent) { +BTree.prototype.findMin = function () { 
-    ​var parent = this.parent; +    ​if (this.children.length > 0) { 
-    leftSplit.parent = parent; +        var foundNode ​this.children[0].findMin(); 
-    ​rightSplit.parent = parent; +        ​foundNode.push([this0]); 
-    ​var destination ​parent.pickChild(leftSplit.values[0]); +        ​return foundNode
-    ​parent.children.splice(destination1, leftSplit, rightSplit); +    } 
-    ​parent.insert(median)+    ​else { 
-  } else { +        ​return [[this, ​0]]; 
-    ​this.values[0] = median; +    }
-    ​this.children = [leftSplitrightSplit]; +
-    ​leftSplit.parent = this; +
-    rightSplit.parent = this; +
-  ​}+
 }; };
  
-BTree.prototype.pickChild ​= function (value) { +BTree.prototype.remove ​= function (value) { 
-  var hasOpenSlots ​((this.children.length - 1- this.values.length0; +    var nodeStack ​= this.find(value, true)
-  if (this.children.length ​!== 0 && !hasOpenSlots) { +     
-    ​for (var destination ​= 0; destination < this.values.length; destination++{ +    if (!nodeStackreturn; 
-      if (value < this.values[destination]) { +    var nodeToRemove = nodeStack[0][0], indexToRemove = nodeStack[0][1]
-        ​break+     
-      }+    ​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);​
     }     }
-    return destination;​ 
-  } 
-  return null; 
 }; };
  
-BTree.prototype.contains ​= function (value) { +BTree.prototype.rebalance ​= function (nodeStack) { 
-  var found = false; +    var parent, parentIndex
-  this.traverse(function (node) { +    ​if (nodeStack.length ​> 0) { 
-    ​for (var i = 0; i < node.values.length; i++){ +        ​parent ​nodeStack[0][0],​ parentIndex ​nodeStack[0][1];
-      ​found ​found || value === node.values[i];+
     }     }
-  ​}); +    var minValues = Math.floor(this.order/​2);​ 
-  ​return found+    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.traverse ​= function (callback) { +BTree.prototype.forEach ​= function (callback) { 
-  ​callback(this)+    var numChildren = this.children.length
-  for (var i = 0; i < this.children.length; i++) { +    if (numChildren > 0) { 
-    this.traverse.call(this.children[i], callback);​ +        ​for (var i=0; i<numChildren; i++) { 
-  }+            this.children[i].forEach(callback);​ 
 +            if (i<​numChildren-1) { 
 +                callback(this.values[i]); 
 +            } 
 +        } 
 +    } 
 +    else { 
 +        // No children casejust pass all the values to `callback`. 
 +        this.values.forEach(callback);​ 
 +    }
 };</​syntax>​ };</​syntax>​
  
 ======= Support ======= ======= Support =======
 <syntax js> <syntax js>
-var btree = new BTree(); +var btree = new BTree(3); 
-for (var i=0;​i<​10;​i++) { + 
-    btree.insert(Math.floor(Math.random()*100));​+function setup() { 
 +    // Make sure we don't add '​i'​ to the environment. 
 +    ​for (var i=0;​i<​10;​i++) { 
 +        btree.insert(Math.floor(Math.random()*100)); 
 +    } 
 +
 +setup(); 
 + 
 +function fixBTree(fixbtree) { 
 +    if (fixbtree && !(fixbtree instanceof BTree)) { 
 +        var mybtree = new BTree(fixbtree.order);​ 
 +        mybtree.values = fixbtree.values;​ 
 +        fixbtree.children.forEach(function (x) { 
 +            mybtree.children.push(fixBTree(x));​ 
 +        }); 
 +        return mybtree; 
 +    } 
 +    return fixbtree; 
 +
 + 
 +function preRun() { 
 +    btree = fixBTree(btree);​ 
 +
 + 
 +function extendArray(a,​ b) { 
 +    Array.prototype.push.apply(a,​ b);
 }</​syntax>​ }</​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 117: Line 296:
 { {
     "​title":"​B-tree",​     "​title":"​B-tree",​
-    "​height":"​500px"​+    ​"​preRunSource":​ true, 
 +    ​"​height":"​500px"​
 +    "​persistentGlobals":​ ["​btree"​]
 } }
 </​syntax>​ </​syntax>​
Line 125: Line 306:
 <​html>​ <​html>​
 <​head>​ <​head>​
-<​script>​ +    <​style>​ 
-/* Optional functions+        g.node { 
 +            font-family:​ Helvetica, sans-serif;​ 
 +            font-size: 13px; 
 +            font-weight:​ bold; 
 +        } 
 +        rect.node-dot { 
 +            fill: white; 
 +            stroke: red; 
 +            stroke-width:​ 1px; 
 +        } 
 +        g.current rect.node-dot { 
 +            fill: rgb(3, 166, 249); 
 +            stroke: blue; 
 +        } 
 +        g.min rect.node-dot { 
 +            fill: rgb(249, 3, 104); 
 +            stroke: blue; 
 +        } 
 +        g.new tspan { 
 +            opacity: 0.5; 
 +        } 
 +        g.new .node-dot 
 +        { 
 +            stroke-dasharray:​5,​5;​ 
 +        } 
 +        g.found rect.node-dot { 
 +            fill: rgb(249, 197, 3); 
 +            stroke: rgb(255, 143, 0); 
 +        } 
 +        path.link { 
 +            fill: none; 
 +            stroke: gray; 
 +        } 
 +        path.move-data { 
 +            fill: none; 
 +            stroke: black; 
 +  marker-end:​ url(#​arrow);​ 
 +        } 
 +        tspan.index { 
 +            fill: red; 
 +        } 
 +        input { 
 +            width: 50px; 
 +        } 
 +    </​style>​ 
 +<script src="​algorithms-lib/​d3.v3.min.js"></​script>​ 
 +</head>
  
 +<​body>​
 +  <div style="​padding:​2px"​ id="​buttons">​
 +    <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 id="​visualisation"></​div>​
 +
 +<script type="​text/​javascript">​
 +var layoutRoot = d3.select("#​visualisation"​)
 +    .append("​svg"​).attr("​width",​ 400).attr("​height",​ 400)
 +    .append("​g"​)
 +    .attr("​class",​ "​container"​)
 +    .attr("​transform",​ "​translate(20,​20)"​);​
 +    ​
 +layoutRoot.append("​svg:​defs"​).append("​svg:​marker"​)
 +    .attr("​id",​ "​arrow"​)
 +    .attr("​viewBox",​ "0 0 10 10")
 +    .attr("​refX",​ 0)
 +    .attr("​refY",​ 5)
 +    .attr("​markerWidth",​ 6)
 +    .attr("​markerHeight",​ 6)
 +    .attr("​orient",​ "​auto"​)
 +    .append("​svg:​path"​)
 +    .attr("​d",​ "M0,0 L10,5 L0,10 z");
 +
 +function treeDepth(tree) {
 +    if (!tree) return 0;
 + return 1+Math.max(treeDepth(tree.left),​ treeDepth(tree.right));​
 +}
 +
 +var idCount = 0;
 +function id(obj) {
 + if (!obj.hasOwnProperty("​id"​)) obj.id = idCount++;
 +    return obj.id;
 +}
 +    ​
 +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) {
 +    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
 +    var tree = d3.layout.tree()
 +        .sort(null)
 +        .nodeSize([60,​ 40])
 +        .children(function(d) {
 +            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) {
 +            return (a.parent == b.parent ? 1.1 : 1.3);
 +        });
 +
 +    var nodes = tree.nodes(d3Node(btree));​
 +    var links = tree.links(nodes);​
 +
 +    // Edges between nodes as a <path class="​link"​ />
 +    var linkNodes = layoutRoot.selectAll("​path.link"​)
 +        .data(links,​ function(d) {return id(d.target);​});​
 +    ​
 +    linkNodes.enter()
 +        .insert("​path",​ "​g"​)
 +        .attr("​class",​ "​link"​);​
 +    ​
 +    linkNodes.transition().duration(duration)
 +    .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
 +    var nodes = layoutRoot.selectAll("​g.node"​)
 +        .data(nodes,​ function(d) {return id(d);});
 +    var newNodes = nodes.enter()
 +        .append("​g"​)
 +        .attr("​class",​ "​node"​)
 +        .attr("​transform",​ function(d) {
 +            return "​translate("​ + d.x + ","​ + d.y + "​)";​
 +        })
 +        .style("​opacity",​ 0);
 +
 +    newNodes.append("​rect"​)
 +        .attr("​class",​ "​node-dot"​)
 +        .attr("​rx",​ 5)
 +        .attr("​ry",​ 5)
 +        .attr("​width",​ 0)
 +        .attr("​height",​ 0); // Start small.
 +
 +    newNodes.append("​text"​)
 +        .attr("​dy",​ 4)
 +        .attr("​text-anchor",​ "​middle"​);​
 +    ​
 +    var nodesUpdate = nodes.transition().duration(duration);​
 +    nodes.classed("​current",​ function(d) {return d===current;​});​
 +    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.
 +    if (foundNode && minNode && foundNode.text !== foundNode.data && foundNode.data === minNode.data) {
 +        var dx = foundNode.x-minNode.x;​
 +        var dy = foundNode.y-minNode.y;​
 +        var len = Math.sqrt(dx*dx+dy*dy);​
 +        ​
 +        layoutRoot.append("​path"​)
 +        .attr("​class",​ "​move-data"​)
 +            .attr("​stroke-width",​ 2)
 +            .attr("​opacity",​ 1)
 +        .attr("​d",​ "​M"​+ (minNode.x+dx/​len*10)+","​+(minNode.y+dy/​len*10)+"​L"​+(minNode.x+dx/​len*10)+","​+(minNode.y+dy/​len*10))
 +        .transition().duration(duration)
 +        .attr("​d",​ "​M"​+ (minNode.x+dx/​len*10)+","​+(minNode.y+dy/​len*10)+"​L"​+(foundNode.x-dx/​len*20)+","​+(foundNode.y-dy/​len*20));​
 +    }
 +    else {
 +        layoutRoot.select("​path.move-data"​)
 +        .transition().duration(duration)
 +        .attr("​opacity",​ 0)
 +        .remove();
 +    }*/
 +    ​
 +    nodesUpdate.attr("​transform",​ function(d) {
 +            return "​translate("​ + d.x + ","​ + d.y + "​)";​
 +        })
 +        .style("​opacity",​ 1);
 +    nodesUpdate.select("​rect"​)
 +     .attr("​width",​ 60)
 +     .attr("​height",​ 30)
 +     .attr("​transform",​ "​translate(-30,​-15)"​);​
 +    ​
 +    function zipData(values,​ node) {
 +        var z = [];
 +        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.
 +    layoutRoot.transition().duration(duration)
 +    .attr("​transform",​ "​translate("​ + (348/​2-d3Node(btree).x+0.5) + ",​20.5)"​);​
 +    ​
 +    var nodesExit = nodes.exit().transition().duration(duration);​
 +    nodesExit.remove();​
 +    nodesExit.select("​circle"​).attr("​r",​ 0);
 +    nodesExit.select("​text"​).attr("​fill-opacity",​ 0);
 +    linkNodes.exit().remove();​
 +}
 +    ​
 function globals() { function globals() {
-    return {};+    ​// Clear out '​foundNode'​ global. 
 +    ​return {"​foundNode":​undefined};
 } }
-function ​args() { +     
-    ​return null;+function ​insert() { 
 +    ​var data = document.getElementById('​input'​).value;​ 
 +    data = parseInt(data);​ 
 +    runScript("​btree.insert("​+ data +"​)"​);​ 
 +
 +     
 +function btreeRemove() { 
 +    var data = document.getElementById('​input'​).value;​ 
 +    data = parseInt(data);​ 
 +    runScript("​btree.remove("​+ data +"​)"​);
 } }
-*/ 
  
 +function random() {
 + reset();
 +}
 +
 +function find() {
 +    var data = document.getElementById('​input'​).value;​
 +    data = parseInt(data);​
 +    runScript("​foundNode = btree.find("​+ data +"​)"​);​
 +}
 +
 +function thisInTopFunction(x,​ fn) {
 + var fnThis = null;
 +    for (var i=x.stack.length-1;​ i>=0; i--) {
 +        if (x.stack[i].function === fn) {
 +            fnThis = x.stack[i].thisObject;​
 +            break;
 +        }
 +    }
 +    return fnThis;
 +}
 +
 +function varInTopFunction(x,​ v) {
 + var fnVar = null;
 +    for (var i=x.stack.length-1;​ i>=0; i--) {
 +        fnVar = x.stack[i].lookupInScope(v);​
 +        if (fnVar) {
 +            break;
 +        }
 +    }
 +    return fnVar;
 +}
 +    ​
 function update(n, x, isRunning, duration, prev) { function update(n, x, isRunning, duration, prev) {
     if (duration < 0) {     if (duration < 0) {
         return; // State-less visualisation.         return; // State-less visualisation.
     }     }
-    var out = x.lookupInScope("​out"); +    ​if (x) { 
-    ​document.body.innerHTML = "out = "+JSON.stringify(out);+        ​var btree = x.lookupInScope("​btree"); 
 +        if (btree) { 
 +            buildTree(x,​ btree, duration);​ 
 +        } 
 +    ​
 +     
 +    // Disable buttons while running. 
 +    d3.selectAll("#buttons *").attr('​disabled',​ isRunning? 1 : null);
 } }
 </​script>​ </​script>​
-</​head>​ 
-<​body>​ 
 </​body>​ </​body>​
-</​html>​ +</​html></​syntax>​
-</​syntax>​+
 </​nowiki>​ </​nowiki>​
algorithm/b-tree.1438416086.txt.gz · Last modified: 2015/08/01 01:01 by will