λ Binary search tree

======= Algorithm ======= <syntax js> function BinarySearchTree(data, parent) { this.data = data; this.parent = parent; } BinarySearchTree.prototype = { insert: function(data) { // Inserts 'data' into the binary search tree. // Recurse until there is an empty space to insert the new data into. if (typeof this.data === "undefined") { this.data = data; } else if (data < this.data) { if (this.left) { // If we have a left node recurse and insert into that. this.left.insert(data); } else { // Otherwise add a new node as the left child. this.left = new BinarySearchTree(data, this); } } else if (data > this.data) { if (this.right) { // If we have a right node recurse and insert into that. this.right.insert(data); } else { // Otherwise add a new node as the right child. this.right = new BinarySearchTree(data, this); } } }, findMin: function() { // Find the minimum node in this tree, by finding the leftmost node. var min = this; while (min.left) { min = min.left; } return min; }, replaceInParent: function(newNode) { if (this.parent) { // Replace whichever child this node is of its parent with 'newNode'. if (this.parent.left === this) { this.parent.left = newNode; } else if (this.parent.right === this) { this.parent.right = newNode; } } else { // This is the root node, replace ourselves with 'newNode'. this.data = newNode? newNode.data : undefined; this.right = newNode? newNode.right : undefined; this.left = newNode? newNode.left : undefined; } // Set the parent of the newNode correctly. if (newNode) { newNode.parent = this.parent; } }, find: function(data) { // Finds 'data' in the tree and returns the node that contains data, // or 'undefined' if data doesn't exist. var foundNode = undefined; if (data < this.data && this.left) { foundNode = this.left.find(data); } else if (data > this.data && this.right) { foundNode = this.right.find(data); } else if (data === this.data) { foundNode = this; } return foundNode; }, remove: function(data) { // Removes 'data' from the tree. var foundNode = this.find(data); if (foundNode) { if (foundNode.left && foundNode.right) { // If 'foundNode' has both left and right children. // Find the minimum value on the right. // ie. the minimum value greater than 'foundNode'. var rightMin = foundNode.right.findMin(); // Replace 'foundNode' data with the 'rightMin' data. foundNode.data = rightMin.data; // Replace 'rightMin' with its right child (or 'undefined'). // Guaranteed no left child as 'rightMin' is a minimum. rightMin.replaceInParent(rightMin.right); } else { // Replace 'foundNode' by whichever child it has, left or right. // Or 'undefined' if 'foundNode' has no children. foundNode.replaceInParent(foundNode.left || foundNode.right); } } } } </syntax> ======= Support ======= <syntax js> var bst = new BinarySearchTree(); // A random roughly balanced tree. var n = Math.random()*5+4; for (var i=0; i<n; i++) { var variance = 30+i/9*19; bst.insert(50+Math.floor(Math.random()*(2*variance)-variance)); } function fixBST(fixbst) { if (fixbst && !(fixbst instanceof BinarySearchTree)) { var mybst = new BinarySearchTree(fixbst.data); mybst.left = fixBST(fixbst.left); if (mybst.left) mybst.left.parent = mybst; mybst.right = fixBST(fixbst.right); if (mybst.right) mybst.right.parent = mybst; return mybst; } return fixbst; } function preRun() { bst = fixBST(bst); } </syntax> ======= Tests ======= <syntax js> </syntax> ======= Options ======= <syntax js> { "title": "Binary search tree", "height": "480px", "preRunSource": true, "persistentGlobals": ["bst"] } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <style> g.node { font-family: Helvetica, sans-serif; font-size: 13px; font-weight: bold; } circle.node-dot { fill: white; stroke: red; stroke-width: 1px; } g.current circle.node-dot { fill: rgb(3, 166, 249); stroke: blue; } g.min circle.node-dot { fill: rgb(249, 3, 104); stroke: blue; } g.found circle.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); } input { width: 50px; } </style> <script src="http://d3js.org/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="bstRemove()">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 buildTree(current, minNode, foundNode, treeData, duration) { // var height = Math.min(500, 20*(1+treeDepth(treeData))); // size of the diagram var tree = d3.layout.tree() .sort(null) .nodeSize([40, 40]) .children(function(d) { // Add dummy nodes to ensure a binary looking tree. if (d.left || d.right) { return [d.left? d.left : {}, d.right? d.right : {}]; } return null; }); var nodes = tree.nodes(treeData); 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" /> 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;}); // 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("circle") .attr("class", "node-dot") .attr("r", 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("min", function(d) {return d===minNode;}); nodes.classed("found", function(d) {return d===foundNode;}); // 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("circle") .attr("r", 15); nodes.select("text") .text(function(d) { d.text = d.data; // Save what we show. return d.data? d.data : "?"; }); // Centre. layoutRoot.transition().duration(duration) .attr("transform", "translate(" + (400/2-treeData.x) + ",20)"); 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() { // Clear out 'foundNode' global. return {"foundNode":undefined}; } function insert() { var data = document.getElementById('input').value; data = parseInt(data); runScript("bst.insert("+ data +")"); } function bstRemove() { var data = document.getElementById('input').value; data = parseInt(data); runScript("bst.remove("+ data +")"); } function random() { reset(); } function find() { var data = document.getElementById('input').value; data = parseInt(data); runScript("foundNode = bst.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) { if (duration < 0) { return; // State-less visualisation. } if (x) { var bst = x.lookupInScope("bst"); var insertNode = thisInTopFunction(x, bst.insert) || /*thisInTopFunction(x, bst.remove) ||*/ thisInTopFunction(x, bst.find); var foundNode = varInTopFunction(x, "foundNode") || (x.returnedFrom === bst.find? x.returnedValue : null) var minNode = x.lookupInScope("min") || varInTopFunction(x, "rightMin") || (x.returnedFrom === bst.findMin? x.returnedValue : null); buildTree(insertNode, minNode, foundNode, bst, duration); } // Disable buttons while running. d3.selectAll("#buttons *").attr('disabled', isRunning? 1 : null); } </script> </body> </html> </syntax>