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 QuickSortSplay TreesTreapsBinary Heaps2-3-TreesAA TreesAVL TreesBinary Search TreesTreesLinked listsArrays for busy peopleAsymptotic Complexity
SkipList
class SkipList {
constructor (max_level=10, p=0.5) {
this.level = 1;
this.maxLevel = max_level;
this.p = p; // Growth probability
this.header = new Node(-Infinity, null, this.maxLevel); // Node(key, val, level)
}
Insert (key, val) {
/* Insertion
*/
let update = newArray(this.maxLevel, NIL);
let x = this.header;
// Search
for (let i = this.level - 1; i >= 0; i--) {
while (x.forward[i].key < key) {
x = x.forward[i];
}
update[i] = x;
}
x = x.forward[0]
if (x.key == key) {
x.val = val;
}
else {
let new_level = this.randomLevel();
if (new_level > this.level) {
for (let i = this.level; i < new_level; i++) {
update[i] = this.header;
}
this.level = new_level;
}
// Create node to insert
x = new Node(key, val, new_level);
for (let i=0; i<new_level; i++) {
x.forward[i] = update[i].forward[i];
update[i].forward[i] = x;
}
}
}
/* Search
** The search is done by going forward on the topmost level possible.
*/
Search (key) {
let x = this.header;
for (let i = this.level - 1; i >= 0; i--) {
while (x.forward[i].key < key) {
x = x.forward[i];
}
}
x = x.forward[0];
if (x.key == key) {
return x.val;
} else {
return undefined;
}
}
Delete (key) {
/* Deletion
*/
let update = newArray(this.maxLevel, NIL);
let x = this.header;
// Search
for (let i=this.level - 1; i >= 0; i--) {
while (x.forward[i].key < key) {
x = x.forward[i];
}
update[i] = x;
}
x = x.forward[0];
if (x.key === key) {
for (let i = 0; i < this.level; i++) {
if (update[i].forward[i] != x) {
break;
}
else {
update[i].forward[i] = x.forward[i];
}
}
while (this.level > 0 && this.header.forward[this.level] === NIL) {
this.level--;
}
} else {
throw `Key Error: key '${key}' not found.`;
}
}
toString() {
let s = "header";
let x = this.header;
while (x.forward[0] != NIL) {
x = x.forward[0]
s = s + ` -> [${x.key}|${x.val}]`;
}
return s + " -> NIL";
}
randomLevel () {
let level = 1;
while (Math.random() < this.p) { // biased coin toss
level++;
}
return level
}
};
sl = {
refresh;
let L = new SkipList()
for (let [key,value] of [[2,'two'],[4,'four'],[10,'ten'],[7,'seven'],[3,'three'],[1,'one'],[9,'nine']]) {
L.Insert (key,value);
}
return L
}
dot`${graphViz(sl)}`
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.
