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/03 20:51]
will Attempt at persistence.
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 14: Line 14:
     // Handle root split case.     // Handle root split case.
     if (typeof m_r === "​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.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 24: 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 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 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 46: 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 65: 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};
 }; };
  
-// Returns the BTree node that contains 'value' ​or null if '​value'​ is not found +// Returns the BTree node and index containing `valueor null if not found
-BTree.prototype.find = function (value) {+// currently hacked for deletion... 
 +BTree.prototype.find = function (value, asStack) {
     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]) {
-            // Recurse and search the ordered child for 'value'+            // Recurse and search the ordered child for `value`
-            ​return ​this.children2[i].find(value);​+            ​var foundNode = this.children[i].find(value, asStack)
 +            if (asStack && foundNode) foundNode.push([this,​ i]); 
 +            return foundNode;
         }         }
         else if (value === this.values[i]) {         else if (value === this.values[i]) {
-            return this;+            ​if (asStack) ​return ​[[this, i]]; 
 +            return [this, i];
         }         }
     }     }
     return null;     return null;
 +};
 +
 +BTree.prototype.findMin = function () {
 +    if (this.children.length > 0) {
 +        var foundNode = this.children[0].findMin();​
 +        foundNode.push([this,​ 0]);
 +        return foundNode;
 +    }
 +    else {
 +        return [[this, 0]];
 +    }
 +};
 +
 +BTree.prototype.remove = function (value) {
 +    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.rebalance = function (nodeStack) {
 +    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.forEach = function (callback) { BTree.prototype.forEach = function (callback) {
-    ​callback(this)+    ​var numChildren = this.children.length
-    for (var i=0, c=this.children.length; i<c; i++) { +    ​if (numChildren > 0) { 
-        this.children[i].forEach(callback);​+        ​for (var i=0; i<numChildren; i++) { 
 +            this.children[i].forEach(callback);​ 
 +            if (i<​numChildren-1) { 
 +                callback(this.values[i]);​ 
 +            } 
 +        } 
 +    } 
 +    else { 
 +        // No children case, just pass all the values to `callback`. 
 +        this.values.forEach(callback);​
     }     }
 };</​syntax>​ };</​syntax>​
Line 95: Line 207:
 var btree = new BTree(3); var btree = new BTree(3);
  
-for (var i=0;​i<​10;​i++) { +function setup() { 
-    btree.insert(Math.floor(Math.random()*100));​+    // 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) { function fixBTree(fixbtree) {
Line 103: 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 113: Line 229:
 function preRun() { function preRun() {
     btree = fixBTree(btree);​     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 158: 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 171: Line 344:
             stroke: black;             stroke: black;
   marker-end:​ url(#​arrow);​   marker-end:​ url(#​arrow);​
 +        }
 +        tspan.index {
 +            fill: red;
         }         }
         input {         input {
Line 181: Line 357:
 <​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 214: 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 222: 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(treeData);+    var nodes = tree.nodes(d3Node(btree));
     var links = tree.links(nodes);​     var links = tree.links(nodes);​
  
Line 241: 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 267: 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 299: 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("​ + (348/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 326: 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 370: Line 613:
     if (x) {     if (x) {
         var btree = x.lookupInScope("​btree"​);​         var btree = x.lookupInScope("​btree"​);​
-        ​var insertNode = thisInTopFunction(x, btree.split|| thisInTopFunction(x,​ btree.insertInternal) || thisInTopFunction(x,​ btree.insert) || thisInTopFunction(x,​ btree.find);​ +        ​if (btree) ​{ 
-        var foundNode = varInTopFunction(x, "​foundNode"​) || (x.returnedFrom === btree.find? x.returnedValue : null) +            ​buildTree(x, btree, ​duration); 
-        var minNode;// = x.lookupInScope("​min"​) || varInTopFunction(x"​rightMin"​) || (x.returnedFrom === bst.findMin?​ x.returnedValue : null); +        ​}
-        ​if(btree)buildTree(insertNode,​ minNode, foundNode, btree, duration);+
     }     }
     ​     ​
algorithm/b-tree.1438660286.txt.gz · Last modified: 2015/08/03 20:51 by will