nil = {
var nil;
class AANode {
constructor (key, level, left, right) {
[this.key, this.left, this.right, this.level] = [key,left,right,level]
}
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)
}
clone () {
if (this == nil) return nil;
return new AANode (this.key, this.level, this.left.clone(), this.right.clone())
}
skew () {
if (this.left.level == this.level) {
let q = this.left;
this.left = q.right;
q.right = this;
return q;
}
else return this;
}
split () {
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
}
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();
}
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;
}
}
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
}
leftReplacement () {
let p = this.left;
while (p.right != nil) p = p.right;
return p;
}
rightReplacement () {
let p = this.right;
while (p.left != nil) p = p.left;
return p;
}
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)
return nil;
else if (this.left == nil) {
let r = this.rightReplacement();
this.key = r.key;
this.right = this.right.delete(r.key);
}
else {
let r = this.leftReplacement();
this.key = r.key;
this.left = this.left.delete(r.key);
}
}
return this.fixupAfterDelete();
}
}
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 = nil
for (let key of [5,6,1,10,11]) {
aa = aa.insert(key);
div.append(html`<div><span style='vertical-align:top'>${key} inserted</span>${dot`${graphViz(aa)}`}</div>`);
}
return div
}
// Por exemplo, ao deletar o 11 e o 10 passaria a ter um filho a direita nil. Após isso, iríamos aplicar a atualização do level do 10 que passaria a ser 1, já que o filho com o menor level é o nil que por padrão é zero. Assim, o 6 passaria a ser um filho vermelho a esquerda do 6, pois passariam a ter o mesmo level. Por isso,
{
let div = html`<div></div>`;
let aa = AA (5,6,1,10,11);
for (let key of [11]) {
aa = aa.delete(key);
div.append(html`<div><span style='vertical-align:top'>${key} deleted</span>${dot`${graphViz(aa)}`}</div>`);
}
return div
}
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.
