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 TreesTreesLinked listsArrays for busy peopleAsymptotic Complexity
Binary Search Trees
class BinaryTree {
constructor(node = null) {
this.node = node;
}
*preorder() {
if (this.node) {
yield this;
yield* this.node.left.preorder();
yield* this.node.right.preorder();
}
}
*inorder() {
if (this.node) {
yield* this.node.left.inorder();
yield this;
yield* this.node.right.inorder();
}
}
*postorder() {
if (this.node) {
yield* this.node.left.postorder();
yield* this.node.right.postorder();
yield this;
}
}
toString() {
if (this.node) return this.node.toString();
return "-";
}
}
class BinaryTreeNode {
constructor (entry,left,right) {
[this.entry,this.left,this.right] = [entry,left,right]
}
toString() {
if (this.entry instanceof String) return this.entry;
return this.entry.toString()
}
}
function BT (...args) {
if (args.length == 0) return new BinaryTree ()
return new BinaryTree(new BinaryTreeNode(...args))
}
bt = BT("A",BT("B",BT(),BT()),BT("C",BT(),BT()))
draw(bt)
[...bt.inorder()].map(tree => tree.node.entry)
[...bt.preorder()].map(tree => tree.node.entry)
[...bt.postorder()].map(tree => tree.node.entry)
class Entry {
constructor (key,value = null) {
[this.key,this.value] = [key,value]
}
toString () {
if (this.value) return `${this.key} (${this.value})`
return `${this.key}`
}
}
class BinarySearchTree extends BinaryTree {
constructor (...args) {
super(...args);
}
// Finds a subtree whose root node has the given key.
// If not found, returns the tree where one such node would be inserted.
find (key) {
if (!this.node) return this;
if (this.node.entry.key == key) return this;
if (this.node.entry.key < key) return this.node.right.find(key);
return this.node.left.find(key)
}
// Inserts the given entry. Raises an error on duplicate keys.
insert (entry) {
let t = this.find (entry.key);
if (t.node) throw `This key already in tree: ${entry.key}`;
t.node = new BinaryTreeNode (entry, new BinarySearchTree(),
new BinarySearchTree())
return t
}
// Returns the lefmost leaf node of this tree, which must
// be non-empty
leftmost () {
if (!this.node) throw "Tree has no nodes";
if (!this.node.left.node) return this;
return this.node.left.leftmost();
}
// Deletes the entry in the root of this tree
delete() {
if (!this.node) throw "Tree has no nodes";
if (!this.node.left.node) {
this.node = this.node.right.node
}
else if (!this.node.right.node) {
this.node = this.node.left.node
}
else {
let l = this.node.right.leftmost();
this.node.entry = l.node.entry;
l.delete()
}
}
// Returns a shallow copy of this tree
clone() {
if (!this.node) return new BinarySearchTree();
return new BinarySearchTree (new BinaryTreeNode (this.node.entry,
this.node.left.clone(),
this.node.right.clone()))
}
}
function BST(entries) {
let t = new BinarySearchTree();
for (let [k,v] of entries) t.insert(new Entry(k,v))
return t
}
t = BST([[9,"A"],[7,"B"],[8,"C"],[1,"D"],[4,"E"],[5,"F"],[11,"X"]])
draw(t)
[...t.inorder()].map(tree => tree.node.entry.toString())
q = {
let q = t.clone();
q.find(9).delete()
return q
}
draw(q)
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.
