Computer Engineering student at UFRJ.
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) {
if (key <= this.key) {
let [leftnode,depth] = this.left.insertSG(key,value);
this.left = leftnode;
return [this, depth+1];
}
else {
let [rightnode,depth] = this.right.insertSG(key,value);
this.right = rightnode;
return [this, depth+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((this.left.size()/this.size())>2/3){
return [this.size(), this];
}
else{
return this.left.scapegoat(key);
}
}
else{
if((this.right.size()/this.size())>2/3){
return [this.size(), this];
}
else{
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 A = [];
this.inorder(A);
function buildSubtree (i, k){
if(k === 1) return A[i];
let n = Math.ceil(k/2);
return new Splitter(A[i+n-1].key, buildSubtree(i, n), buildSubtree(i+n, k-n))
}
const {key, left, right} = buildSubtree(0, A.length);
Object.assign(this,{key,left,right});
}
// 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)
}
const {key, left, right} = buildSubtree(0, A.length);
Object.assign(this,{key,left,right});
}
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.
