Software engineer and visualization enthusiast. Lives in Cambridge, Massachusetts, with no dogs.
Public
Edited
Nov 3, 2023
Paused
2 stars
visualize = (tree, title) => {
const root = tree.stratify();
const descendants = root.descendants();
const paths = descendants.map((node) =>
node
.ancestors()
.reverse()
.map((d) => d.id)
.join("/")
);
return Plot.tree(paths, {
fx: "tree",
text: (d) => "",
stroke: "#ccc",
fill: "node:name",
title: "node:name",
curve: "step-before",
tip: true
}).plot({
color,
title,
subtitle: `Height = ${root.height + 1}`,
width: width / 2,
height: 600,
axis: null,
margin: 50
});
}
allQueries = Array.from({ length: maxQueries }, rand)
queries = allQueries.slice(0, numQueries)
allValues = (reset, Float64Array.from({ length: maxNumNodes }, Math.random))
treeBeforeQueries = {
const tree = new ShuffleTree({ seed: 0 });
const values = allValues.slice(0, numNodes);
if (sortBeforeConstruction.length) values.sort();
for (const value of values) {
tree.insert(value);
}
return tree;
}
maxNumNodes = 500
treeAfterQueries = {
const tree = treeBeforeQueries.clone();
for (const query of queries) {
tree.locate(query);
}
return tree;
}
maxQueries = 1e5
rand = d3.randomBeta(10 * skew, 10 * (1 - skew))
comma = d3.format(",")
color = ({
type: "linear",
scheme: "PiYG",
domain: [0, 1]
})
class ShuffleTree {
constructor({
size = 0,
superRoot = { left: undefined, right: undefined, key: undefined },
seed = Math.random()
} = {}) {
this.size = size;
this.superRoot = superRoot;
this.rand = d3.randomUniform.source(d3.randomLcg(seed))();
}
// The root node is defined to be right child of the super root.
get root() {
return this.superRoot.right;
}
set root(value) {
this.superRoot.right = value;
}
// The core tree functions are oriented around a "location" abstraction containing a child and its parent.
// This could alternately be thought of as a LeftChild(parent) | RightChild(parent) construct.
rootLocation() {
return loc(this.root, this.superRoot);
}
// Insert i into the tree, unless it's already there.
// Adapted from "An implementation of top-down splaying", by Daniel Sleator, 1992.
insert(key) {
if (this.root === undefined) {
this.size = 1;
this.root = { left: undefined, right: undefined, key };
return this.root;
}
const { child, parent } = this.locateCore(this.rootLocation(), key);
if (key < child.key) {
const newNode = { left: child.left, right: child, key };
child.left = undefined;
this.size++;
return replaceChild(parent, child, newNode);
} else if (child.key < key) {
const newNode = { left: child, right: child.right, key };
child.right = undefined;
this.size++;
return replaceChild(parent, child, newNode);
} else {
// we get here if it's already in the tree; don't add it again.
// todo: we may want to disallow adding duplicate nodes
return child;
}
}
// Removes `key` from the tree if it's there.
// Adapted from "An implementation of top-down splaying", by Daniel Sleator, 1992.
remove(key) {
if (this.root === undefined) return;
const t = this.locateCore(this.rootLocation(), key);
if (key == t.child.key) {
// found it
if (t.child.left === undefined) {
// If the node to be deleted has no left child, we can replace it with its right child.
replaceChild(t.parent, t.child, t.child.right);
} else {
// We want to move the left child up to replace the deleted node, but we need a place to put the previous right child. So we look for an insertion spot for the right child, which we know to be greater than every value in the left subtree.
replaceChild(t.parent, t.child, t.child.left);
const x = this.locateCore(loc(t.child.left, t.child), key, false);
x.child.right = t.child.right;
}
this.size--;
}
}
// Higher-level API for the common `locate` case of searching over a tree and
// needing only the child node rather than the full (child, parent) location.
locate(key, rotate) {
return this.locateCore(this.rootLocation(), key, rotate).child;
}
// Return the node with the specified key if we find it, or the node that would be its parent if not.
// Adapted from the 'splay' function in 'An implementation of top-down splaying' by Daniel Sleator, 1992.
// The optional `rotate` argument controls whether we allow the possibility for rotations during this locate operation.
locateCore(location, key, rotate = true) {
let counter = rotate ? Math.floor(this.rand() * (this.size + 1)) : -1;
let { child, parent } = location;
let grandparent = undefined;
while (child) {
grandparent = parent;
parent = child;
if (key < child.key) {
child = child.left;
if (counter === 0 && child) {
rotateRight(parent, grandparent);
parent = grandparent;
}
} else if (child.key < key) {
child = child.right;
if (counter === 0 && child) {
rotateLeft(parent, grandparent);
parent = grandparent;
}
} else {
break;
}
counter = Math.floor((counter - 1) / 2);
}
return loc(parent, grandparent);
}
extent() {
const leftmost = this.locate(-Infinity, false);
const rightmost = this.locate(Infinity, false);
return [leftmost?.key, rightmost?.key];
}
links() {
if (this.size === 0) return [];
const stack = [this.root];
const links = [{ id: this.root.key, parentId: this.superRoot.key }]; // array of { id, parentId }
while (stack.length) {
const node = stack.pop();
if (node.left) {
links.push({ id: node.left.key, parentId: node.key });
stack.push(node.left);
}
if (node.right) {
links.push({ id: node.right.key, parentId: node.key });
stack.push(node.right);
}
}
return links;
}
stratify() {
return d3.stratify()(this.links());
}
// To do: Be attentive to reproducibility wrt. not just the the random numbers included
// in the tree or used for queries, but also those used by the tree locate operation itself.
//
// Note: Cloning the tree does not clone RNG state – the clone has a new RNG, currently seeded
// with default seed of zero, regardless of what the seed for the original tree was, since this
// at least means that multiple clones of the same tree will align with each other in terms of
// their future trajectories...
clone() {
const { size, superRoot } = JSON.parse(JSON.stringify(this));
// 🌶️ this does not propagate the rng state since there is no way to clone a d3.randomLcg state.
// but we at least make it deterministic
return new ShuffleTree({ size, superRoot, seed: 0 });
}
}
// Represents a child, with reference to its parent to allow for tree manipulations
// involving the repositioning the child within the tree or removal of the child from the tree.
function loc(child, parent) {
return { child, parent };
}
// Perform a right rotation, which elevates the child's left subtree above the child.
// See 'Shuffe Tree: A Randomized Self-Adjusting Binary Search Tree', Fig. 1
// Mapping this code to the diagram, child = x, next = y, and parent = parent(x), b = next.right
function rotateRight(child, parent) {
const next = child.left;
child.left = next.right;
next.right = child;
replaceChild(parent, child, next);
}
// Perform a left rotation, which elevates the child's right subtree above the child.
// See 'Shuffe Tree: A Randomized Self-Adjusting Binary Search Tree', Fig. 1
// Mapping this code to the diagram, child = y, next = x, and parent = parent(y), b = next.left
function rotateLeft(child, parent) {
const next = child.right;
child.right = next.left;
next.left = child;
replaceChild(parent, child, next);
}
// Replace `child`, which is a child of `parent`, with `newChild`, and return `newChild`.
function replaceChild(parent, child, newChild) {
assert(
parent.left === child || parent.right === child,
"cannot replace nonexistent child"
);
if (parent.left === child) parent.left = newChild;
else parent.right = newChild;
return newChild;
}
function assert(cond, msg) {
if (!cond) throw new Error("assertion violation");
}
log = console.log.bind(console)
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
