Published
Edited
Dec 19, 2020
md`# Treaps (incomplete)`
class TreapNode {
constructor (key, priority, left, right) {
Object.assign(this,{key,priority,left,right})
}
}
class Treap {
constructor (node = null) {
this.node = node
}
// Inserts key into the tree. Throws an error if key already present
insert (key) {
this.assistInsertion(key,Math.random())
}
turnRight () {
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];
}
// Removes key from the tree. Throws an error if the key is not in tree
remove (key, tree = true) {
const valid = tree === true ? this : tree;
if (!valid.node) throw 'Key not in the tree';
if (valid.node.key > key) valid.node.left = this.remove(key, valid.node.left);
if (valid.node.key < key) valid.node.right = this.remove(key, valid.node.right);
if (!valid.node.right.node && !valid.node.left.node) valid.node = null;
if (valid.node.right.node && valid.node.left.node) {
if (valid.node.left.node.priority > valid.node.right.node.priority) {
valid.node = this.turnLeft(valid.node);
valid.node.left = this.remove(key, valid.node.left);
}
else {
valid.node = this.turnRight(valid.node);
valid.node.right = this.remove(key, valid.node.right);
}
}
else valid.node = (valid.node.left.node) ? valid.node.left.node : valid.node.right.node;
return valid;
}
turnLeft () {
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];
}
assistInsertion (key,priority) {
if (!this.node)
this.node = new TreapNode(key, priority,new Treap(), new Treap())
else if (this.node.key == key)
throw ("key already exists")
else if (this.node.key < key){
if (!this.node.right.node)
this.node.right.node = new TreapNode(key, priority,new Treap(), new Treap())
else if (this.node.right.node.priority < priority || !this.node.right.node )
this.node.right.weighInsertion(key, priority)
else
this.node.right.assistInsertion(key, priority)
}
else if (this.node.key > key){
if (!this.node.left.node)
this.node.left.node = new TreapNode(key, priority,new Treap(), new Treap())
else if (this.node.left.node.priority < priority || !this.node.right.node )
this.node.left.weighInsertion(key, priority)
else
this.node.left.assistInsertion(key, priority)
}
}
weighInsertion (key, priority) {
if (!this.node)
this.node = new TreapNode(key, priority,new Treap(), new Treap())
else if (this.node.key == key)
throw ("key already exists")
else if (this.node.key < key){
this.node.right.weighInsertion(key, priority)
this.turnLeft()
}
else if (this.node.key > key){
this.node.left.weighInsertion(key, priority)
this.turnRight()
}
}
}
viewof refresh = html`<button>Refresh</button>`
{ 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)}`}`
}
md`## Drawing code`
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.
