Computer Graphics & Visualization @ufrj.br
Point k-d trees with queriesHash table with open addressing and double hashingHash table with separate chainingPoint k-d treesOmohundro balltree construction algorithmsCounting and radix sortMergeSort and QuickSortSkipListTreapsBinary Heaps2-3-TreesAA TreesAVL TreesBinary Search TreesTreesLinked listsArrays for busy peopleAsymptotic Complexity
Splay Trees
class Node {
constructor(key, left, right, value = null) {
Object.assign(this, { key, left, right, value });
}
}
class SplayTree {
constructor(node = null) {
this.node = node;
}
rotateRight() {
let [d, b, C] = [
this.node,
this.node.left.node,
this.node.left.node.right.node
];
[this.node, b.right.node, d.left.node] = [b, d, C];
}
rotateLeft() {
let [b, d, C] = [
this.node,
this.node.right.node,
this.node.right.node.left.node
];
[this.node, d.left.node, b.right.node] = [d, b, C];
}
splay(key) {
function sp(p, q = null, r = null, path = "") {
let result = 0;
if (p.node && p.node.key != key) {
if (p.node.key > key) {
if (p.node.left.node) result = sp(p.node.left, p, q, path + "L") + 1;
} else {
if (p.node.right.node)
result = sp(p.node.right, p, q, path + "R") + 1;
}
}
if (result % 2 == 0) {
switch (path.slice(-2)) {
case "LL":
r.rotateRight();
r.rotateRight();
break;
case "RR":
r.rotateLeft();
r.rotateLeft();
break;
case "RL":
q.rotateRight();
r.rotateLeft();
break;
case "LR":
q.rotateLeft();
r.rotateRight();
break;
case "R":
q.rotateLeft();
break;
case "L":
q.rotateRight();
break;
}
}
return result;
}
if (this.node) sp(this);
}
insert(key) {
if (this.node == null) {
this.node = new Node(key, new SplayTree(), new SplayTree());
} else {
this.splay(key);
if (this.node.key == key) {
throw `Key ${key} already exists`;
}
if (this.node.key < key) {
let root = new Node(key, new SplayTree(this.node), this.node.right);
this.node.right = new SplayTree();
this.node = root;
} else {
let root = new Node(key, this.node.left, new SplayTree(this.node));
this.node.left = new SplayTree();
this.node = root;
}
}
}
remove(key) {
this.splay(key);
if (this.node == null || this.node.key != key) {
throw `Key ${key} does not exist`;
} else {
if (this.node.left.node == null) {
this.node = this.node.right.node;
} else if (this.node.right.node == null) {
this.node = this.node.left.node;
} else {
this.node.right.splay(key);
this.node.right.node.left.node = this.node.left.node;
this.node = this.node.right.node;
}
}
}
*inorder() {
if (this.node) {
yield* this.node.left.inorder();
yield this;
yield* this.node.right.inorder();
}
}
}
{
refresh;
let t = new SplayTree();
let keys = [0, 1, 2, 3, 4, 5, 6];
let div = html`<div></div>`;
d3.shuffle(keys);
for (let i of keys) {
t.insert(i);
div.append(html`<br>After insert(${i})<br>`);
div.append(draw(t));
}
d3.shuffle(keys);
for (let i of keys) {
div.append(html`<br>After remove(${i})<br>`);
t.remove(i);
div.append(draw(t));
}
return div;
}
function graphViz(tree) {
let count = 0;
let nodeMap = new Map();
let result = "";
let getNodeId = (tree) => {
if (nodeMap.has(tree.node)) return nodeMap.get(tree.node);
let nodeId = "node" + ++count;
if (tree.node == null) {
result += `${nodeId} [label="" shape=point width=0];`;
return nodeId;
}
let label = tree.node.value
? `${tree.node.key}(${tree.node.value})`
: tree.node.key;
result += `${nodeId} [label="${label}"];\n`;
nodeMap.set(tree.node, nodeId);
return nodeId;
};
let nullNode = new SplayTree();
let traverse = (tree) => {
if (tree.node == null) return;
let nodeId = getNodeId(tree);
if (tree.node.left.node == null && tree.node.right.node == null) return;
for (let child of [tree.node.left, nullNode, tree.node.right]) {
let childId = getNodeId(child);
let style = child.node == null ? "[style=invis]" : "";
result += `${nodeId} -- ${childId} ${style};\n`;
traverse(child);
}
};
traverse(tree);
return `graph {graph [ordering="out"];
${result}\n }`;
}
function draw(t) {
return dot`${graphViz(t)}`;
}
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.
