viewof reroll = button({ title: "randomize values", value: "GO 🎉!" })
root = randoms.reduce((acc, v) => insert(v, acc), NIL)
function insert(X, T) {
if (nil(T)) return node(X);
if (X < T.value) T.left = insert(X, T.left);
else if (X > T.value) T.right = insert(X, T.right);
else return T;
T = skew(T);
T = split(T);
return T;
}
function remove(X, T) {
if (nil(T)) return T;
if (X < T.value) {
T.left = remove(X, T.left);
} else if (X > T.value) {
T.right = remove(X, T.right);
} else {
if (leaf(T)) return NIL;
if (nil(T.left)) {
const L = successor(T);
T.value = L.value;
T.right = remove(L.value, T.right);
} else {
const L = predecessor(T);
T.value = L.value;
T.left = remove(L.value, T.left);
}
}
T = skew(decrease_level(T));
T.right = skew(T.right);
if (!nil(T.right)) {
T.right.right = skew(T.right.right);
}
T = split(T);
T.right = split(T.right);
return T;
}
function split(T) {
// if (nil(T)) return NIL; if (nil(T.right) || nil(T.right.right)) return T;
if (nil(T) || nil(T.right) || nil(T.right.right)) return T;
if (T.level === T.right.right.level) {
const R = T.right;
T.right = R.left;
R.left = T;
R.level += 1;
return R;
}
return T;
}
function skew(T) {
// if (nil(T)) return NIL; if (nil(T.left)) return T;
if (nil(T) || nil(T.left)) return T;
const L = T.left;
if (L.level === T.level) {
T.left = L.right;
L.right = T;
return L;
}
return T;
}
function decrease_level(T) {
const should_be = 1 + Math.min(T.left.level, T.right.level);
if (should_be < T.level) {
T.level = should_be;
if (should_be < T.right.level) {
T.right.level = should_be;
}
}
return T;
}
function successor(T) {
let next = T.right;
while (!nil(next.left)) next = next.left;
return next;
}
function predecessor(T) {
let prev = T.left;
while (!nil(prev.right)) prev = prev.right;
return prev;
}
function leaf(node) {
return nil(node.left) && nil(node.right);
}
nil = function(node) {
return node === NIL;
}
node = value => new Node(value, 1, NIL, NIL)
class Node {
constructor(value, level, left, right) {
this.level = level;
this.value = value;
this.left = left;
this.right = right;
}
}
data = convert(root)
import { chart, viewof options, style } with {
data
} from "@stardisblue/vertical-tree"
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.
