Computer Graphics & Visualization @ufrj.br
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")
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.