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 Heaps2-3-TreesAA TreesAVL TreesBinary Search TreesLinked listsArrays for busy peopleAsymptotic Complexity
Trees
class RootedTree {
constructor (data, ...descendants) {
this.data = data;
this.descendants = descendants;
}
*preorder () {
yield this;
for (let d of this.descendants) yield* d.preorder()
}
*postorder () {
for (let d of this.descendants) yield* d.postorder()
yield this;
}
}
RT = function (...args) { return new RootedTree (...args) };
rt1 = RT("A",RT("B",RT("C"),RT("D")),RT("E"),RT("F",RT("G"),RT("H",RT("I"),RT("J"),RT("K"))))
draw(rt1)
[...rt1.preorder()].map(node => node.data)
[...rt1.postorder()].map(node => node.data)
class RootedTreeBinary {
constructor (data,firstChild=null,nextSibling=null) {
[this.data,this.firstChild,this.nextSibling] = [data,firstChild,nextSibling]
}
*preorder () {
yield this;
let child = this.firstChild;
while (child != null) {
yield* child.preorder();
child = child.nextSibling;
}
}
*postorder () {
let child = this.firstChild;
while (child != null) {
yield* child.postorder();
child = child.nextSibling;
}
yield this;
}
}
RTB = (d,f,n) => new RootedTreeBinary (d,f,n)
rtb1 = RTB("A",RTB("B", RTB("C", null, RTB("D")), RTB("E",null,RTB("F",RTB("G",null,RTB("H",RTB("I",null,RTB("J",null,RTB("K")))))))))
[...rt1.postorder()].map(node => node.data)
draw(rtb1)
class BinaryTree {
constructor (entry,left=null,right=null) {
// Alternative to line below: Object.assign(this,{entry,left,right})
[this.entry,this.left,this.right] = [entry,left,right]
}
*inorder () {
if (this.left) yield* this.left.inorder()
yield this;
if (this.right) yield* this.right.inorder()
}
*preorder () {
yield this;
if (this.left) yield* this.left.preorder()
if (this.right) yield* this.right.preorder()
}
*postorder () {
if (this.left) yield* this.left.postorder()
if (this.right) yield* this.right.postorder()
yield this;
}
}
BT = (e,l,r) => new BinaryTree (e,l,r)
bt1 = BT("a",BT("b",BT("d", BT("g"),BT("h"))),BT("c",BT("e",null,BT("i")),BT("f")))
draw(bt1)
[...bt1.inorder()].map(node => node.entry)
[...bt1.preorder()].map(node => node.entry)
[...bt1.postorder()].map(node => node.entry)
class Link {
constructor (to, isThread = false) {
[this.to, this.isThread] = [to, isThread];
}
}
class ThreadedBinaryTree {
constructor (entry, left=null, right=null) {
[this.entry,this.left,this.right] = [entry,left,right]
}
*inorder () {
if (this.left && !this.left.isThread) yield* this.left.to.inorder()
yield this;
if (this.right && !this.right.isThread) yield* this.right.to.inorder()
}
thread () {
let a = [...this.inorder()];
for (let i = 0; i < a.length; i++) {
if (i > 0 && !a[i].left) a[i].left = new Link(a[i-1], true);
if (i+1 < a.length && !a[i].right) a[i].right = new Link(a[i+1], true);
}
return this
}
inorderSuccessor () {
let u = this.right;
if (!u) return null;
if (u.isThread) return u.to;
while (u.to.left && !u.to.left.isThread) {
u = u.to.left
}
if (u) return u.to
return null
}
inorderPredecessor () {
}
}
L = (to) => to ? new Link(to) : null
TBT = (e,l,r) => new ThreadedBinaryTree (e, L(l), L(r))
tbt1 = TBT("a",TBT("b",TBT("d", TBT("g"),TBT("h"))),TBT("c",TBT("e",null,TBT("i")),TBT("f"))).thread()
[...tbt1.inorder()].map(x => x.entry)
tbt1.inorderSuccessor().inorderSuccessor().inorderSuccessor()
draw(tbt1)
class CompleteBinaryTree {
constructor (array, index = 0) {
[this.array,this.index] = [array,index];
}
get left () {
return new CompleteBinaryTree (this.array, this.index*2+1)
}
get right () {
return new CompleteBinaryTree (this.array, this.index*2+2)
}
get parent () {
return new CompleteBinaryTree (this.array, ~~((this.index-1)/2))
}
get entry () {
return this.array[this.index]
}
set entry (value) {
this.array [this.index] = value
}
*inOrder () {
if (this.entry != undefined) {
yield* this.left.inOrder();
yield this;
yield* this.right.inOrder()
}
}
}
cbt1 = new CompleteBinaryTree([0,1,2,3,4,5,6,7]);
[...cbt1.inOrder()].map(x => x.entry)
draw(cbt1)
{
let cbt = new CompleteBinaryTree([0,1,2,3,4,5,6,7]);
cbt.entry="root";
cbt.left.entry = "leftSubtree";
cbt.left.parent.entry="ROOT";
cbt.left.right.parent.entry = "Left";
return [...cbt.inOrder()].map(x => x.entry)
}
md`## Libraries`
md`### GraphViz`
dot = require("@observablehq/graphviz@0.2")
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.
