Computer Graphics & Visualization @ufrj.br
Point k-d trees with queriesHash table with open addressing and double hashingHash table with separate chainingPoint k-d treesOmohundro balltree construction algorithmsCounting and radix sortMergeSort and QuickSortSkipListSplay TreesTreapsBinary HeapsAA TreesAVL TreesBinary Search TreesTreesLinked listsArrays for busy peopleAsymptotic Complexity
2-3-Trees
//
// Class representing a 2-3 tree
//
class Node23 {
constructor (parent=null) {
[this.parent,this.links,this.keys] = [parent,[],[]]
}
// Return number of keys
keyCount () {
return this.keys.length
}
// Returns true iff node is leaf
isLeaf () {
return this.links.length == 0
}
// Returns true iff node is root
isRoot () {
return this.parent == null
}
// Returns the index i where key == keys[i] or
// where key should be inserted
locateKey (key) {
let i = 0;
while (i < this.keys.length && this.keys[i] < key) i++;
return i;
}
// Finds the node where key is or the leaf node where it should be inserted
find (key) {
if (this.isLeaf()) return this;
let i = this.locateKey(key);
if (i < this.keyCount() && this.keys[i] == key) return this;
let son = this.links[i];
if (son.parent != this) { // Debug!
console.log(son, " parent link is not ", this);
}
return son.find(key)
}
// Splits this node
split() {
if (this.isRoot()) {
// Split root node
let [bNode,dKey,fNode] = [new Node23(this),this.keys[1],new Node23(this)];
[bNode.keys,fNode.keys] = [this.keys.slice(0,1),this.keys.slice(2,3)];
if (!this.isLeaf()) {
let [A,C,E,G] = this.links;
[bNode.links, fNode.links] = [[A,C],[E,G]];
for (let child of bNode.links) child.parent = bNode;
for (let child of fNode.links) child.parent = fNode;
}
this.keys = [dKey];
this.links = [bNode,fNode]
} else {
// Split non-root node
let [bNode,dKey,fNode] = [this,this.keys[1],new Node23(this.parent)];
[bNode.keys,fNode.keys] = [bNode.keys.slice(0,1),bNode.keys.slice(2,3)];
if (!this.isLeaf()) {
let [A,C,E,G] = this.links;
[bNode.links, fNode.links] = [[A,C],[E,G]];
for (let child of bNode.links) child.parent = bNode;
for (let child of fNode.links) child.parent = fNode;
}
this.parent.insert (dKey,fNode)
}
}
// Inserts a new key into this node.
insert (key,rightLink = null) {
let i = this.locateKey(key);
if (i < this.keyCount() && this.keys[i] == key) throw key+": key already in tree";
if (this.isLeaf() || rightLink) {
this.keys = this.keys.slice (0,i).concat([key]).concat(this.keys.slice(i));
if (rightLink) { // inserting in a non-leaf node
this.links = this.links.slice (0,i+1)
.concat([rightLink])
.concat(this.links.slice(i+1))
}
if (this.keyCount() > 2) this.split()
}
else {
this.links[i].insert(key,rightLink)
}
}
// Returns a copy of the tree rooted at this node
clone() {
let copy = new Node23();
copy.keys = this.keys.slice(0);
if (!this.isLeaf()) {
copy.links = this.links.map (l => {
let c = l.clone();
c.parent = copy;
return c
});
}
return copy;
}
// Returns the smallest key to the right of key i in the current node.
// Assumes this node is internal.
rightReplacement (i) {
let p = this.links[i+1];
while (!p.isLeaf()) p = p.links[0];
return p.keys[0]
}
// Returns the next sibling node to the right of this one if it exists. Otherwise returns null
rightSibling() {
if (this.isRoot()) return null;
let i = this.parent.links.indexOf (this);
if (i < 0 || i == this.parent.links.length-1) return null;
return this.parent.links[i+1]
}
// Returns the next sibling node to the left this one if it exists. Otherwise returns null
leftSibling() {
if (this.isRoot()) return null;
let i = this.parent.links.indexOf (this);
if (i < 0 || i == 0) return null;
return this.parent.links[i-1]
}
// Tries to fix an empty node by adopting from the left or right sibling
// Returns true iff adoption is successful
adopt () {
let sibling = this.leftSibling();
if (sibling && sibling.keyCount() > 1) {
let i = this.parent.links.indexOf (this);
let lkey = sibling.keys.pop();
this.keys.push (this.parent.keys[i-1]);
this.parent.keys[i-1] = lkey;
if (!this.isLeaf()) {
let llink = sibling.links.pop();
this.links.unshift (llink)
llink.parent = this
}
return true
}
sibling = this.rightSibling();
if (sibling && sibling.keyCount() > 1) {
let i = this.parent.links.indexOf (this);
let rkey = sibling.keys.shift();
this.keys.push (this.parent.keys[i]);
this.parent.keys[i] = rkey;
if (!this.isLeaf()) {
let rlink = sibling.links.shift();
this.links.push(rlink)
rlink.parent = this
}
return true;
}
return false
}
// Deletes the ikey'th key of this node and its two neighboring links, replacing
// them with the given link. Returns the key value that was removed
delKey (ikey, link) {
let key = this.keys.splice(ikey,1);
this.links.splice (ikey,2,link)
return key[0]
}
// Tries to merge with sibling from left or from right
// Returns true if successful
merge() {
let sibling = this.leftSibling()
if (sibling) { // Merge with sibling to the left
console.assert (sibling.keys.length == 1); // Sibling must be a 2-node
let i = this.parent.links.indexOf(this); // Index of the link that points to this node
let pkey = this.parent.delKey(i-1,sibling)
sibling.keys.push (pkey)
if (!this.isLeaf()) {
sibling.links.push (this.links[0])
this.links[0].parent = sibling
}
return true
}
sibling = this.rightSibling();
if (sibling) { // Merge with sibling to the right
console.assert (sibling.keys.length == 1); // Sibling must be a 2-node
let i = this.parent.links.indexOf(this); // Index of the link that points to this node
let pkey = this.parent.delKey(i,sibling)
sibling.keys.unshift(pkey)
if (!this.isLeaf()) {
sibling.links.unshift(this.links[0])
this.links[0].parent = sibling
}
return true
}
return false
}
// Called whenever a node has 0 keys
underflow() {
if (this.isRoot()) {
if (!this.isLeaf()) {
let son = this.links[0];
this.keys = son.keys
this.links = son.links;
for (let grandson of son.links) {
grandson.parent = this
}
}
}
else {
if (!this.adopt()) {
if (this.merge()) {
if (this.parent.keys.length == 0) {
this.parent.underflow()
}
}
else throw "Neither merge or adopt worked!"
}
}
}
// Deletes the key from the tree
delete (key) {
let i = this.locateKey(key);
if (i >= this.keyCount() || this.keys[i] != key) {
if (this.isLeaf()) throw key+": key not in tree";
else this.links[i].delete(key)
}
else {
// found key
if (!this.isLeaf()) {
let r = this.rightReplacement(i);
this.keys[i] = r;
this.links[i+1].delete(r)
}
else {
this.keys.splice(i,1);
if (this.keys.length == 0) {
// underflow
this.underflow()
}
}
}
}
}
{
let div = html`<div></div>`;
let t = new Node23();
div.append(dot`${graphViz(t)}`);
for (let key of [10, 8, 7, 11, 6, 2, 12, 14, 15]) {
div.append(htl.html`<br><b>After inserting ${key}</b><br>`);
t.insert(key);
div.append(dot`${graphViz(t)}`);
}
return div;
}
{
let div = html`<div></div>`;
let t = new Node23();
for (let key of [1, 4, 6, 7, 10, 9, 11, 8, 2, 3, 5]) t.insert(key);
div.append(dot`${graphViz(t)}`);
for (let key of [1, 4, 6, 7, 10, 9, 11, 8, 2, 3, 5]) {
t.delete(key);
div.append(html`<br><b>After deleting ${key}</b><br>`);
div.append(dot`${graphViz(t)}`);
}
return div;
}
function graphViz (node) {
let count = 0;
let nodeMap = new Map();
let result = "";
let getNodeId = (node) => {
if (nodeMap.has(node)) return nodeMap.get(node);
let nodeId = "node"+(++count);
let label = node.keyCount() ? node.keys.join(" | ") : "-" ;
result += `${nodeId} [label="${label}"];\n`;
nodeMap.set (node,nodeId);
return nodeId
}
let traverse = (node) => {
let nodeId = getNodeId (node);
for (let child of node.links) {
let childId = getNodeId(child);
result += `${nodeId} -> ${childId};\n`;
traverse(child);
}
}
traverse(node)
return `digraph { node [shape=record style=rounded]\n${result} }`;
}
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.
