class Node {
constructor (key, left, right) {
Object.assign(this,{key,left,right})
}
}
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)) {
// Zig Zig left-left
case "LL" : r.rotateRight(); r.rotateRight(); break;
// Zig Zig right-right
case "RR" : r.rotateLeft(); r.rotateLeft(); break;
// Zig Zag right-left
case "RL" : q.rotateRight(); r.rotateLeft(); break;
// Zig Zag left-right
case "LR" : q.rotateLeft(); r.rotateRight(); break;
// Zig right
case "R" : q.rotateLeft(); break;
// Zig left
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
}
}
}
}
viewof refresh = html`<button>Refresh</button>`
{
refresh;
let t = new SplayTree()
let keys = [0,1,2,3,4,5,6];
let div= html`<div></div>`;
shuffle(keys)
for (let i of keys) {
t.insert(i);
div.append(html`<br>After insert(${i})<br>`);
div.append(dot`${graphViz(t)}`);
}
shuffle(keys)
for (let i of keys ) {
div.append(html`<br>After remove(${i})<br>`);
t.remove(i)
div.append(dot`${graphViz(t)}`)
}
return div
}
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.
