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-TreesAVL TreesBinary Search TreesTreesLinked listsArrays for busy peopleAsymptotic Complexity
AA Trees
//
// Nil is an empty AA tree. A new tree can be created by calling nil.insert()
//
nil = {
var nil;
class AANode {
constructor (key, level, left, right) {
[this.key, this.left, this.right, this.level] = [key,left,right,level]
}
// Basic BST find algorithm.
// Returns the node with the sought key or null if not found
find (key) {
if (this == nil) return null;
if (this.key == key) return this;
if (this.key < key) return this.right.find(key);
return this.left.find(key)
}
// Returns a copy of this tree
clone () {
if (this == nil) return nil;
return new AANode (this.key, this.level, this.left.clone(), this.right.clone())
}
// Rotates if red node to the left of a black node
// Returns the new root of this subtree
skew () {
if (this.left.level == this.level) {
let q = this.left;
this.left = q.right;
q.right = this;
return q;
}
else return this;
}
// Rearranges a black node with two red nodes in cascade to the right.
// Returns the new root of this subtree
split () {
// Note: must not split the nil node
if (this != nil && this.right.right.level == this.level) {
let q = this.right;
this.right = q.left;
q.left = this;
q.level += 1;
return q;
}
else return this
}
// Inserts key into the tree rooted at this node.
// Returns the inserted node
insert (key) {
let p = this;
if (p == nil)
p = new AANode(key, 1, nil, nil);
else if (key < p.key)
p.left = p.left.insert(key);
else if (key > p.key)
p.right = p.right.insert(key);
else
throw "Duplicate Key: "+key;
return p.skew().split();
}
// Makes sure the level of this node respects the AA level invariant,
// i.e., that is, 1 plus the level of its black children
updateLevel() {
let idealLevel = 1 + Math.min(this.left.level, this.right.level);
if (this.level > idealLevel) {
this.level = idealLevel;
if (this.right.level > idealLevel)
this.right.level = idealLevel;
}
}
// Fixes up the tree after a node is deleted making sure it still
// obeys the AA tree invariant by performing appropriate skews and splits.
// Returns the updated node
fixupAfterDelete() {
this.updateLevel();
let p = this.skew();
p.right = p.right.skew();
p.right.right = p.right.right.skew();
p = p.split();
p.right = p.right.split();
return p
}
// Returns the descendant node containing the immediately smaller key
leftReplacement () {
let p = this.left;
while (p.right != nil) p = p.right;
return p;
}
// Returns the descendant node containing the immediately bigger key
rightReplacement () {
let p = this.right;
while (p.left != nil) p = p.left;
return p;
}
// Returns this node after deleting key from the tree rooted at it
delete (key) {
if (this == nil) throw "not found: "+key;
if (key < this.key)
this.left = this.left.delete(key);
else if (key > this.key)
this.right = this.right.delete(key);
else {
if (this.left == nil && this.right == nil) // leaf node?
return nil; // just unlink the node
else if (this.left == nil) { // no left child?
let r = this.rightReplacement(); // get replacement from right
this.key = r.key; // copy replacement contents here
this.right = this.right.delete(r.key);// delete replacement
}
else { // no right child?
let r = this.leftReplacement(); // get replacement from left
this.key = r.key; // copy replacement contents here
this.left = this.left.delete(r.key); // delete replacement
}
}
return this.fixupAfterDelete(); // fix structure after deletion
}
}
nil = new AANode ('nil',0);
nil.left = nil.right = nil;
return nil
}
function AA (...keys) {
let t = nil;
for (let k of keys) t = t.insert(k)
return t
}
{
let div = html`<div></div>`;
let aa = AA (5,6,1,10,11,2,4,3,7,9,8);
for (let key of [2,3,4,5,6]) {
aa = aa.delete(key);
div.append(html`<div><span style='vertical-align:top'>${key} deleted</span>${dot`${graphViz(aa)}`}</div>`);
}
return div
}
md`## Drawing code`
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.
