Published
Edited
Dec 19, 2020
1 star
Tree = {
class Splitter {
constructor(key, left, right) {
Object.assign(this, { key, left, right });
}
find(key) {
if (key <= this.key) return this.left.find(key);
return this.right.find(key);
}
// Return the node that has to be considered by my father
insert(key, value) {
if (key <= this.key) {
this.left = this.left.insert(key, value);
return this;
} else {
this.right = this.right.insert(key, value);
return this;
}
}
// Like insert, but behaves like an Scapegoat tree insert. Returns
// a pair [node, depth], where node is the subtree where key/value was inserted
// and depth is the depth of the new external node
insertSG(key, value) {
let level;
if (key <= this.key)
{
[this.left, level] = this.left.insertSG(key, value);
}
else
{
[this.right, level] = this.right.insertSG(key, value);
}
return [this, level + 1];
}
// Returns a pair [size,sg] where size is the number of nodes in
// this subtree and sg is the scapegoat node closest to the tree
scapegoat(key) {
if (key <= this.key) {
if (3 * this.left.size() > 2 * this.size())
{
return [this.size(), this];
}
return this.left.scapegoat(key);
}
if (3 * this.right.size() > 2 * this.size())
{
return [this.size(), this];
}
return this.right.scapegoat(key);
}
remove(key) {
if (key <= this.key) {
this.left = this.left.remove(key);
if (this.left == null) return this.right;
} else {
this.right = this.right.remove(key);
if (this.right == null) return this.left;
}
return this;
}
inorder(array) {
this.left.inorder(array);
this.right.inorder(array);
}
// Rebuilds this subtree
rebuild() {
let x = [];
this.inorder(x);
function buildSubtree(i, k) {
if (k == 1)
{
return x[i];
}
let n = k >> 1;
return new Splitter(x[i + n - 1].key, buildSubtree(i, n), buildSubtree(i + n, k - n));
}
let newtree = buildSubtree(0, x.length);
Object.assign(this, newtree);
}
// Returns the number of external nodes in this subtree
size() {
return this.left.size() + this.right.size();
}
}
class External {
constructor(key, value) {
Object.assign(this, { key, value });
}
find(key) {
if (key == this.key) return this.value;
return null;
}
insert(key, value) {
if (key == this.key) throw "Key already in tree";
if (key < this.key) {
return new Splitter(key, new External(key, value), this);
} else {
return new Splitter(this.key, this, new External(key, value));
}
}
// Like insert, but behaves like an Scapegoat tree insert. Returns
// a pair [node, depth], where node is the subtree where key/value was inserted
// and depth is the depth of the new external node
insertSG(key, value) {
let result = this.insert(key, value);
return [result, 1];
}
// Returns a pair [size,sg] where size is the number of nodes in
// this subtree and sg is the scapegoat node closest to the tree
scapegoat(key) {
return [1, null];
}
remove(key) {
if (this.key == key) return null;
throw "Key not found " + key + " here is " + this.key;
}
inorder(array) {
array.push(this);
}
// Returns the number of external nodes in this subtree
size() {
return 1;
}
}
class XBST {
constructor() {
this.root = null;
this.n = this.m = 0;
}
find(key) {
if (this.root == null) return null;
return this.root.find(key);
}
insert(key, value) {
if (this.root == null) {
this.root = new External(key, value);
} else {
this.root = this.root.insert(key, value);
}
}
insertSG(key, value) {
let depth;
if (this.root == null) [this.root, depth] = [new External(key, value), 0];
else [this.root, depth] = this.root.insertSG(key, value);
this.n++;
this.m++;
let limit = Math.log(this.m) / Math.log(1.5);
if (depth > limit) {
let [size, sg] = this.root.scapegoat(key);
sg.rebuild();
}
return [depth, limit];
}
remove(key) {
if (this.root == null) throw "Key does not exist in this tree";
this.root = this.root.remove(key);
}
removeSG(key) {
this.remove(key);
this.n--;
if (this.m > this.n * 2) {
this.rebuild();
this.m = this.n;
}
}
// Returns an array with all External nodes in this tree ordered by key.
inorder() {
if (this.root) {
let result = [];
this.root.inorder(result);
return result;
}
return [];
}
// Rebuilds this tree.
rebuild() {
let A = this.inorder();
function buildSubtree(i, k) {
// (5,3)
if (k == 1) return A[i];
let n = k >> 1; // n = 1
return new Splitter(
A[i + n - 1].key,
buildSubtree(i, n),
buildSubtree(i + n, k - n)
);
//A[5].key, buildSubtree(5,1), buildSubtree(6,2)
}
if (this.root) this.root = buildSubtree(0, A.length);
}
graphviz() {
if (this.root == null) {
return `graph {}`;
}
let count = 0;
let nodeMap = new Map();
let result = "";
let nullNode = () => {
let nodeId = "node" + ++count;
result += `${nodeId} [label="" shape=point width=0];`;
return nodeId;
};
let getNodeId = node => {
if (nodeMap.has(node)) return nodeMap.get(node);
let nodeId = "node" + ++count;
nodeMap.set(node, nodeId);
if (node instanceof External) {
result += `${nodeId} [label="${node.key}|${node.value}" shape=record];`;
} else {
result += `${nodeId} [label="${node.key}"];`;
}
return nodeId;
};
let traverse = node => {
let nodeId = getNodeId(node);
if (node instanceof External) return;
let [left, middle, right] = [
getNodeId(node.left),
nullNode(),
getNodeId(node.right)
];
result += `${nodeId} -- ${left};\n`;
result += `${nodeId} -- ${middle} [style=invis];\n`;
result += `${nodeId} -- ${right};\n`;
traverse(node.left);
traverse(node.right);
};
traverse(this.root);
return `graph{${result}}`;
}
}
return XBST;
}
testXBSTree = {
let tree = new Tree();
let div = html`<div></div>`;
for (let [key,value] of [[10,"a"],[20,"b"],[30,"c"],[40,"d"],[50,"f"],[60,"g"],[5,"x"],[70,"h"],[80,"i"]]) {
tree.insert(key,value);
div.append(html`<br>
Inserted key ${key}, value ${value}
<br>`);
div.append(dot`${tree.graphviz()}`)
}
for (let key of [5,10,20,30,40]) {
tree.remove(key);
div.append(html`<br>
Removed key ${key}
<br>`);
div.append(dot`${tree.graphviz()}`)
}
return div
}
testSGTree = {
let tree = new Tree();
let div = html`<div></div>`;
for (let [key,value] of [[10,"a"],[20,"b"],[30,"c"],[40,"d"],[50,"f"],[60,"g"],[5,"x"],[70,"h"],[80,"i"]]) {
let [depth,limit] = tree.insertSG(key,value);
div.append(html`<br>
Inserted key ${key}, value ${value} at depth ${depth} (limit= ${limit}, n=${tree.n}, m=${tree.m})
<br>`);
div.append(dot`${tree.graphviz()}`)
}
for (let key of [5,10,20,30,40]) {
tree.removeSG(key);
div.append(html`<br>
Removed key ${key} (n=${tree.n}, m=${tree.m})
<br>`);
div.append(dot`${tree.graphviz()}`)
}
return div
}
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.
