Skip to content

Instantly share code, notes, and snippets.

@benlhy
Last active April 19, 2020 09:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save benlhy/7258f0772a41f07636739a7a942c20aa to your computer and use it in GitHub Desktop.
Save benlhy/7258f0772a41f07636739a7a942c20aa to your computer and use it in GitHub Desktop.
animated binary tree - fix duplicates
license: mit
<!DOCTYPE html>
<head>
<meta charset="utf-8">
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src=https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.min.js></script>
<style>
body { margin:0;position:fixed;top:0;right:0;bottom:0;left:0; }
svg {width:100%;height:100%}
</style>
</head>
<body>
<button type="button" onclick="addRandomToTree()">Add node</button>
<button type="button" onclick="resetTree()">Reset</button>
<script>
// Feel free to change or delete any of the code you see in this editor!
var width = 600;
var height = 600;
var margin = { top: 20, bottom: 20, left: 40, right: 20 };
class Tree {
constructor() {
this.root = null;
}
toObject() {
return this.root;
}
add(num) {
if (!this.root) {
this.root = new Node(num);
} else {
let node = this.root;
this.clearVisited()
while (true) {
node.visited = true
if (num < node.value) {
if (node.left) {
node = node.left;
} else {
node.left = new Node(num);
return;
}
} else {
if (node.right) {
node = node.right;
} else {
node.right = new Node(num);
return;
}
}
}
}
}
clearVisited() {
preorderTraverse_clear(this.root,[])
}
}
class Node {
constructor(value, left = null, right = null,visited=true) {
this.left = left;
this.right = right;
this.value = value;
this.visited = visited;
}
}
const preorderTraverse_clear = (node, array) => {
if (!node) return array;
node.visited = false
array = preorderTraverse_clear(node.left, array);
array = preorderTraverse_clear(node.right, array);
return array;
};
const preorderTraverse = (node, array, y, x, sign) => {
if (!node) return array;
if (y === 0) {
array.push({ value: node.value, y: 0, x: 0 ,visited:node.visited});
} else {
x = x + (sign * 2) / Math.pow(2, y);
array.push({ value: node.value, y: y, x: x, visited:node.visited });
}
y = y + 1;
array = preorderTraverse(node.left, array, y, x, -1);
array = preorderTraverse(node.right, array, y, x, 1);
return array;
};
const preorderTraverse_link = (node, linkarray, y, x, sign) => {
if (!node) return linkarray;
var prev_x = x;
var prev_y = y - 1;
if (y === 0) {
} else {
x = x + (sign * 2) / Math.pow(2, y);
linkarray.push({ source: [prev_x, prev_y], target: [x, y] });
}
y = y + 1;
linkarray = preorderTraverse_link(node.left, linkarray, y, x, -1);
linkarray = preorderTraverse_link(node.right, linkarray, y, x, 1);
return linkarray;
};
var topMargin = 50;
const convertToXY = (item) => {
var node = {};
node.value = item.value;
node.y = item.y * 50 + topMargin;
node.x = item.x * 200 + 400;
node.visited = item.visited;
return node;
};
const convertLinkToXY = (item) => {
var node = { source: [], target: [] };
node.source[0] = item.source[0] * 200 + 400;
node.source[1] = item.source[1] * 50 + topMargin;
node.target[0] = item.target[0] * 200 + 400;
node.target[1] = item.target[1] * 50 + topMargin;
return node;
};
let tree = new Tree();
tree.add(50);
/*
tree.add(4);
tree.add(3);
tree.add(8);
tree.add(2);
tree.add(1);
tree.add(9);
tree.add(7);
*/
var treeArray = preorderTraverse(tree.root, [], 0, 0, 1);
//var treelinkArray = preorderTraverse_link(tree.root, [], 0, 0, 1);
treeArray = treeArray.map(convertToXY);
//treelinkArray = treelinkArray.map(convertLinkToXY);
// Feel free to change or delete any of the code you see in this editor!
var svg = d3
.select("body")
.append("svg");
/*
svg.selectAll("path")
.data(treelinkArray)
.enter()
.append("path")
.attr("d", linkGen)
.attr("fill", "none")
.attr("stroke", "black");
*/
var link_sel = svg.append("g")
var node_sel = svg.append("g")
var keyFunc = function(d, i) { return d.value }
var visitedFunc = function(d,i) {return d.visited}
var nodes = node_sel
.selectAll("g")
.data(treeArray)
.enter()
// Add one g element for each data node here.
.append("g")
// Position the g element like the circle element used to be.
.attr("transform",d => "translate(" + d.x + "," + d.y + ")");
nodes.append("circle")
.attr("fill" , "white")
.attr("stroke" , "black")
.attr("r", 20);
// Add a text element to the previously added g element.
nodes.append("text")
.attr("text-anchor", "middle")
.attr("y", ".3em")
.text(d => d.value);
var linkGen = d3.linkVertical();
var prevLink=[]
function resetTree() {
tree = new Tree();
tree.add(50);
var treeArray = preorderTraverse(tree.root, [], 0, 0, 1);
var treelinkArray = preorderTraverse_link(tree.root, [], 0, 0, 1);
treeArray = treeArray.map(convertToXY);
var treelinkArrayBef = treelinkArray.map(convertLinkToXY);
var treelinkArrayAft = treelinkArray.map(convertLinkToXY);
updateTree(treeArray,treelinkArrayBef,treelinkArrayAft);
prevLink = [];
}
var newValue = 0
var lastNumbers = []
function addRandomToTree() {
tree.clearVisited();
while(true){
var randInt = Math.floor(Math.random() * 100);
if (!lastNumbers.includes(randInt)){
newValue = randInt;
tree.add(randInt);
lastNumbers.push(randInt)
break;
}
}
//tree.clearVisited();
var treeArray = preorderTraverse(tree.root, [], 0, 0, 1);
var treelinkArray = preorderTraverse_link(tree.root, [], 0, 0, 1);
treeArray = treeArray.map(convertToXY);
var treelinkArrayAft = treelinkArray.map(convertLinkToXY);
var treelinkArrayBef = treelinkArray.map(convertLinkToXY);
//var treelinkArrayBef = treelinkArrayAft;
console.log("Before:")
console.log(treelinkArrayBef)
console.log("Aft")
console.log(treelinkArrayAft)
var mydiff = _.cloneDeep(_.differenceWith(treelinkArrayBef,prevLink,_.isEqual))
//console.log(mydiff)
prevLink = _.cloneDeep(treelinkArrayBef)
for (let i = 0;i<prevLink.length;i++){
if(_.isEqual(prevLink[i].source,mydiff[0].source) && _.isEqual(prevLink[i].target,mydiff[0].target) )
prevLink[i].target = prevLink[i].source
}
//prevLink = [{"source":[400,50],"target":[400,50]}]
updateTree(treeArray,prevLink,treelinkArrayBef);
prevLink = _.cloneDeep(treelinkArrayBef);
}
function updateTree(treeArray,treelinkArrayBef,treelinkArrayAft){
var t = d3.transition()
.duration(750)
var links = link_sel.selectAll("path")
.data(treelinkArrayBef);
var enter_links = links.enter().append("path")
.attr("fill", "none")
.attr("stroke", "black")
;
links = enter_links.merge(links)
.attr("d", linkGen);
links = svg.selectAll("path")
.data(treelinkArrayAft);
links.exit().remove();
enter_links = links.enter().append("path")
.attr("fill", "none")
.attr("stroke", "black");
links = enter_links.merge(links)
.transition()
.attr("d", linkGen);
/*
var nodes = node_sel.selectAll("g")
.data(treeArray,keyFunc);
nodes.exit().remove()
var enter = nodes.enter().append('g')
.attr("transform",d => "translate(" + d.x + "," + d.y + ")");
enter.append("circle")
.attr("fill" , d => !d.visited ? "grey" : d.value<newValue ? "#aec6cf" : d.value===newValue ? "white" : "#ff7560")
.attr("stroke" , "black")
.attr("r",0)
.transition()
.attr("r", 20)
enter.append("text")
.attr("text-anchor", "middle")
.attr("y", ".3em")
.text(d => d.value);
nodes = enter.merge(nodes);
*/
var nodes = node_sel.selectAll("g")
.data(treeArray,d=>d);
nodes.exit().remove()
var enter = nodes.enter().append('g')
.attr("transform",d => "translate(" + d.x + "," + d.y + ")");
enter.append("circle")
.attr("fill" , d => !d.visited ? "grey" : d.value<newValue ? "#aec6cf" : d.value===newValue ? "white" : "#ff7560")
.attr("stroke" , "black")
.attr("r", d => {
if(d.value==newValue){
return 0
}
else {
return 20
}
}).transition()
.attr("r",20)
enter.append("text")
.attr("text-anchor", "middle")
.attr("y", ".3em")
.text(d => d.value);
nodes = enter.merge(nodes);
/*
nodes = node_sel
.selectAll("g")
.data(treeArray,d=>d.value)
nodes = nodes.enter().append()
console.log(nodes.nodes())
var updated_nodes = nodes.selectAll("circle")
.attr("fill" , (d,i) => !d.visited ? "grey" : d.value<newValue ? "#aec6cf" : d.value===newValue ? "white" : "#ff7560");
console.log(updated_nodes.nodes())
*/
}
</script>
</body>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment