nil = {

var nil;

class AANode {

// Todo o objeto será formado pelos quatro campos abaixo (chave, filho da esquerda, filho da direita e level. Também poderíamos incluir um valor para esse nó

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

// O algoritmo de busca é exatamente igual aos outros, basicamente:

// Se this == nil, retornamos null porque não encontramos nada

// Se this.key == key, retornamos o próprio nó

// Se this.key < key (a chave é maior), descemos para a direita de forma recursiva

// Se this.key > key (a chave é menor), descemos para a esquerda de forma recursiva

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

// Esse é o método que vai retornar uma cópia da árvore passada

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

// Só ocorre se quando se o nó é preto e tem um filho a esquerda vermelho, isto é, se o level do filho a esquerda é igual ao do nó atual (os nós vermelhos tem um mesmo level que o pai)

// Para a rotação: basicamente, o filho a esquerda (q) passa a ser pai do nó atual (p) que se torna o filho a direita de q. Além disso, a subárvore a direita de (q) passa a ser filho de a esquerda de (p)

// Ao final retorna o pai para continuarmos restruturando a árvore pelo caminho até a raiz, ou seja, no caso de rotação, retorna "q" e no caso que não ocorre rotação, retorna "p"

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

// Só ocorre se quando se temos dois nós vermelhos consecutivos a direita do nó atual, isto é, se o level do neto a direita tem o mesmo level do nó atual (os nós vermelhos tem um mesmo level que o pai) significa que os três tem o mesmo level, então o filho e o neto a direita são vermelhos. Também verifica se o nó atual não é igual a nil porque não pode dar um split em um nó do tipo nil

// Para o split: basicamente, o filho a direita (q) é promovido e passa a ser pai do nó atual (p) que se torna o filho a esquerda e continua sendo pai do neto a direita do nó atual. Além disso, o filho a esquerda de (q) passa a ser filho a direita de (p). Por fim, atualizamos o level de q em 1

// Ao final retorna o pai para continuarmos restruturando a árvore pelo caminho até a raiz, ou seja, no caso de split, retorna "q" e no caso que não ocorre split, retorna "p"

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

// O algoritmo de inserção, basicamente:

// Se this == nil, é o lugar onde devemos inserir, então definimos ele como um novo nó do tipo AANode com chave igual aquela dada e dois filhos nil (com level 1 porque será uma folha). Nesse caso, se vamos inserir um filho a esquerda, terá o mesmo level do pai que já tinha level 1 porque era uma folha, assim, teremos que aplicar o skew, por exemplo.

// Se this.key > key (a chave é menor), inserimos na esquerda de forma recursiva

// Se this.key < key (a chave é maior), inserimos na direita de forma recursiva

// Se this.key == key, encontramos a chave e retornamos um erro informando que essa chave já existe na árvore e não poderá ser inserida

// É importante reparar que essa recursividade de "p.right.insert(key)" por exemplo que fará com que restruturemos toda a árvore no caminho até a raíz

// Por fim, fazemos o skew de "p" e do resultado, faremos o split

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

// Essa função é importante porque na deleção, podemos violar as regras da AA. Assim, essa função servirá para definir o ideal level de acordo com os filhos do nó atual, isto é, pegará o mínimo entre o level do seu filho a esquerda e da direita e somará 1 e se o nó atual tem um level maior do que o ideal level, ajusta para o ideal level, assim como, ajustamos o level do filho a direita se ele for vermelho (é o que significa perguntar "this.right.level > idealLevel"). Por exemplo, ao deletar uma folha, o nó pai passará a apontar para nil que por definição tem altura igual a 0, assim, como pega o level mínimo entre seus filhos, o ideal level desse nó pai passará a ser (0 + 1) e precisaremos atualizar ele para level 1

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

// Basicamente, essa função também será essencial para a deleção, visto que teremos mais casos do que na inserção para consertar. Ou seja, após a deleção de um nó, ajustamos a altura do mesmo e tentamos realizar:

// 3 Skews: dele mesmo, do filho a direita e do neto a direita

// Depois 2 splits: dele mesmo e do filho a direita

// Após isso, aplicaremos esses métodos de forma recursiva para restruturar todo o caminho até a raíz

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

// Esse é o método que nos auxiliará na deleção, basicamente, retorna o descendente mais a esquerda, isto é, a chave imediatamente menor

leftReplacement () {

let p = this.left;

while (p.right != nil) p = p.right;

return p;

}

// Returns the descendant node containing the immediately bigger key

// Esse é o método que nos auxiliará na deleção, basicamente, retorna o descendente mais a direita, isto é, a chave imediatamente maior

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

// E esse é o método para a deleção que será aplicado de forma recursiva, basicamente:

// Se this == nil, não encontramos o nó a ser deletado e devemos retornar um erro informando que a chave não foi encontrada

// Se this.key > key (a chave é menor), inserimos na esquerda de forma recursiva

// Se this.key < key (a chave é maior), inserimos na direita de forma recursiva

// Se this.key == key, encontramos a chave e devemos realizar a deleção:

// Se o filho a esquerda e direita forem nil (nó folha), simplesmente retornamos nil para a chamada anterior, isto é, executamos o unlink desse nó para o pai

// Se não for folha e não tiver filho a esquerda, pegaremos o sucessor inorder como o replacement node executando, copiamos o seu conteúdo para o nó atual a ser deletado e deletamos recursivamente o replacement node

// Se não for folha e não tiver filho a direita, pegaremos o sucessor inorder como o replacement node executando, copiamos o seu conteúdo para o nó atual a ser deletado e deletamos recursivamente o replacement node

// Por fim, sempre após deletar um nó e continuar a chamada recursiva, executamos o método fixAfterDelete que atualiza a altura e tenta executar os3 skews e 2 splits

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

}

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

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