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 QuickSortSkipListSplay TreesBinary Heaps2-3-TreesAA TreesAVL TreesBinary Search TreesTreesLinked listsArrays for busy peopleAsymptotic Complexity
Treaps
class TreapNode {
constructor (key, priority, left, right) {
Object.assign(this,{key,priority,left,right})
}
}
{ refresh;
let t = new Treap()
for (let i = 0; i < 10; i++) t.insert(i)
let original = dot`${graphViz(t)}`
let root = t.node.key
t.remove (t.node.key)
return html`Treap with keys from 1 to 10:<br>
${original}<br>
After removing ${root}:<br>
${dot`${graphViz(t)}`}`
}
graphViz = (tree) => {
let result = `digraph{`;
let keys = new Set();
let declare = (tree) => {
let key = tree.node.key;
if (keys.has(key)) return;
let lab = tree.node.key;
result += key + `[shape="record" label="{${lab}|p=${tree.node.priority}}"];\n`;
keys.add(key)
}
let count = 0;
let traverse = (root) => {
if (root.node) {
declare(root);
if (root.node.left.node) {
declare(root.node.left);
result += `${root.node.key} -> ${root.node.left.node.key} ;\n`;
traverse(root.node.left)
}
else {
result += 'null'+(++count)+'[shape = none, label=""];\n';
result += `${root.node.key} -> ${'null'+count} [arrowhead="tee"];\n`;
}
if (root.node.right.node) {
declare(root.node.right);
result += `${root.node.key} -> ${root.node.right.node.key} ;\n`;
traverse(root.node.right);
}
else {
result += 'null'+(++count)+'[shape = none, label=""];\n';
result += `${root.node.key} -> ${'null'+count} [arrowhead="tee"];\n`;
}
}
}
traverse (tree)
return result + "}"
}
dot = require("@observablehq/graphviz")
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.
