30:T729,class Treap { 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]; } insert(key) { if (this.node == null) { this.node = new TreapNode(key, Math.random(), new Treap(), new Treap()); } else if (this.node.key == key) { throw `Key ${key} already exists`; } else if (this.node.key > key) { this.node.left.insert(key); if (this.node.left.node.priority < this.node.priority) this.rotateRight(); } else if (this.node.key < key) { this.node.right.insert(key); if (this.node.right.node.priority < this.node.priority) this.rotateLeft(); } } sinkdown() { if (this.node.left.node && this.node.right.node) { if (this.node.left.node.priority < this.node.right.node.priority) { this.rotateRight(); return this.node.right.sinkdown(); } else { this.rotateLeft(); return this.node.left.sinkdown(); } } else { if (this.node.left.node) { this.rotateRight(); return this.node.right.sinkdown(); } else if (this.node.right.node) { this.rotateLeft(); return this.node.left.sinkdown(); } return this; } } remove(key) { if (this.node == null) { throw `Key ${key} does not exist`; } else if (this.node.key == key) { this.sinkdown().node = null; } else if (this.node.key > key) { this.node.left.remove(key); } else { this.node.right.remove(key); } } }31:T469,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 + "}" }32:[] 2e:{"title":"Treaps","cells":[{"id":0,"value":"md`# Treaps`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"class TreapNode {\n \n constructor (key, priority, left, right) {\n Object.assign(this,{key,priority,left,right})\n }\n \n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":6,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":32,"value":"md`## Demo`","pinned":false,"hidden":false,"mode":"ojs"},{"id":36,"value":"viewof refresh = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":12,"value":"{ refresh;\n let t = new Treap()\n for (let i = 0; i < 10; i++) t.insert(i)\n let original = dot`${graphViz(t)}`\n let root = t.node.key\n t.remove (t.node.key)\n return html`Treap with keys from 1 to 10:
\n ${original}
\n After removing ${root}:
\n ${dot`${graphViz(t)}`}`\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":29,"value":"md`## Drawing code`","pinned":false,"hidden":false,"mode":"ojs"},{"id":11,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":15,"value":"dot = require(\"@observablehq/graphviz\")","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}