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 TreesBinary Search TreesTreesLinked listsArrays for busy peopleAsymptotic Complexity
AVL Trees
import { BinarySearchTree, BinaryTreeNode, Entry } from "@esperanc/binary-search-trees"
class AVLTree extends BinarySearchTree {
constructor (...args) {
super (...args);
this.updateHeight ()
}
// Called by methods that modify the tree. Defines the height attribute
updateHeight () {
this.height = this.node ? Math.max(this.node.left.height, this.node.right.height) + 1 : -1
}
// Returns the balance factor, computed as the difference in height between
// the right and the left branches
get balanceFactor () {
if (this.node) return this.node.right.height - this.node.left.height
return 0
}
// Finds a subtree whose root node has the given key or where one would
// be inserted. Calls the modify function with that tree as an argument
findAndModify (key, modify) {
let result;
if (!this.node || this.node.entry.key == key) {
result = modify (this);
} else if (this.node.entry.key < key) {
result = this.node.right.findAndModify(key, modify);
} else {
result = this.node.left.findAndModify (key, modify);
}
this.rebalance()
}
// Performs rotations to rebalance the tree after modifications
// that may have left it unbalanced
rebalance () {
this.updateHeight ();
let bal = this.balanceFactor;
if (bal < -1) { // Left side too heavy
if (this.node.left.node.left.height < this.node.left.node.right.height)
this.node.left.rotateLeft(); // left-right heavy --> double rotation
this.rotateRight();
}
else if (bal > +1) { // Right side too heavy
if (this.node.right.node.left.height > this.node.right.node.right.height)
this.node.right.rotateRight(); // right-left heavy --> double rotation
this.rotateLeft();
}
}
// AVL right rotation: lifts the node on the left
rotateRight () {
let [d, b, C] = [this.node, this.node.left.node, this.node.left.node.right.node];
[this.node, b.right.node, d.left.node] = [b, d, C];
d.left.updateHeight();
b.right.updateHeight();
this.updateHeight();
}
// AVL left rotation: lifts the node on the right
rotateLeft () {
let [b, d, C] = [this.node, this.node.right.node, this.node.right.node.left.node];
[this.node, d.left.node, b.right.node] = [d, b, C];
b.right.updateHeight();
d.left.updateHeight();
this.updateHeight();
}
// Inserts the given entry. Raises an error on duplicate keys.
insert (entry) {
let insertModifier = (t) => {
if (t.node) throw `This key already in tree: ${entry.key}`;
t.node = new BinaryTreeNode (entry, new AVLTree(), new AVLTree())
return true;
}
return this.findAndModify (entry.key, insertModifier)
}
// Finds a key and deletes it
findAndDelete (key) {
let deleteModifier = (t) => {
t.delete()
}
return this.findAndModify (key, deleteModifier)
}
// Deletes the root
delete () {
super.delete()
this.rebalance()
}
// Returns a shallow copy of this tree
clone() {
if (!this.node) return new AVLTree();
return new AVLTree (new BinaryTreeNode (this.node.entry,
this.node.left.clone(),
this.node.right.clone()))
}
}
function AVL(entries) {
let t = new AVLTree();
for (let [k,v] of entries) t.insert(new Entry(k,v))
return t
}
t = AVL([[10,"A"],[7,"B"],[8,"C"],[1,"D"],[4,"E"],[5,"F"],[9,'x'],[11,'Z']])
draw(t)
{
let q = t.clone();
for (let key of [8,9,11]) q.findAndDelete(key);
return draw(q)
}
{
let avl = AVL([[1],[2],[3],[4],[5],[6],[7],[8],[9],[10]])
let draw1 = draw (avl)
avl.find(6).delete()
return html`${draw1} ${draw (avl)}`
}
draw = (tree) => dot`${graphViz(tree)}`
md`## Libraries`
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.
