Árvore Scapegoat

Na ciência da computação, uma árvore scapegoat é uma árvore de busca binária autobalanceada inventada por Arne Andersson ^[1] em 1989 e novamente por Igal Galperin e Ronald L. Rivest em 1993. ^[2] A árvore scapegoat fornece o pior caso de ${\displaystyle {\color {Blue}O(\log n)}}$ para tempo de pesquisa (com ${\displaystyle n}$ como o número de entradas) e ${\displaystyle O(\log n)}$ para tempo de inserção e exclusão amortizado.

Ao contrário da maioria das outras árvores de pesquisa binárias autobalanceadas que também fornecem o pior caso ${\displaystyle O(\log n)}$ no momento da consulta, as árvores scapegoat não têm sobrecarga de memória adicional por nó em comparação a uma árvore de pesquisa binária comum: além da chave e do valor, um nó armazena apenas dois ponteiros para os nós filhos. Isso torna as árvores de bodes expiatórios mais fáceis de implementar e, devido ao alinhamento da estrutura de dados, pode reduzir a sobrecarga do nó em até um terço.

Em vez das pequenas operações de rebalanceamento incremental usadas pela maioria dos algoritmos de árvore balanceada, as árvores scapegoat raramente, mas com alto custo, designam um nó "bode expiatório". Este nó representa a raíz de uma subárvore, e com o bode expiatório designado, o algoritmo reconstrói toda a subárvore em uma árvore binária completa. Assim, as árvores scapegoat têm ${\displaystyle O(n)}$ pior desempenho de atualização.

Diz-se que uma árvore de pesquisa binária é balanceada em termos de peso se metade dos nós estiver à esquerda da raiz e a outra metade à direita. Um nó balanceado por peso α é definido como atendendo a um critério de equilíbrio de peso relaxado:

size(left) ≤ α*size(node)
size(right) ≤ α*size(node)

Onde o tamanho pode ser definido recursivamente como:

function size(node) is
    if node = nil then
        return 0
    else
        return size(node->left) + size(node->right) + 1
    end if
end function

Mesmo uma árvore degenerada (lista encadeada) satisfaz essa condição se α=1, enquanto que um α=0,5 corresponderia apenas a árvores binárias quase completas.

Uma árvore de pesquisa binária que é balanceada por peso α também deve ser balanceada por altura α, ou seja

height(tree) ≤ floor(log1/α(size(tree)))

Por contraposição, uma árvore que não é balanceada em α-altura não é balanceada em α-peso.

Não há garantia de que as árvores scapegoat mantenham o equilíbrio de peso α em todos os momentos, mas sempre são frouxamente equilibradas em altura α nesse caso.

height(scapegoat tree) ≤ floor(log1/α(size(tree))) + 1.

Violações dessa condição de equilíbrio de altura podem ser detectadas no momento da inserção e implicam que deve haver uma violação da condição de equilíbrio de peso.

Isso torna as árvores scapegoat semelhantes às árvores rubro-negras, pois ambas têm restrições quanto à altura. Eles diferem muito, no entanto, em suas implementações para determinar onde as rotações (ou, no caso de árvores scapegoat, rebalanceamentos) ocorrem. Enquanto as árvores rubro-negra armazenam informações adicionais de "cor" em cada nó para determinar a localização, as árvores scapegoat encontram um bode expiatório que não está balanceado em peso α para executar a operação de rebalanceamento. Isso é vagamente semelhante às árvores AVL, no sentido de que as rotações reais dependem dos "equilíbrios" dos nós, mas os meios de determinar o equilíbrio diferem muito. Como as árvores AVL verificam o valor do saldo em cada inserção/exclusão, ele normalmente é armazenado em cada nó; as árvores de bode expiatório conseguem calculá-lo somente quando necessário, ou seja, somente quando um bode expiatório precisa ser encontrado.

Diferente da maioria das outras árvores de busca autobalanceadas, as árvores scapegoat são totalmente flexíveis quanto ao seu balanceamento. Eles suportam qualquer α tal que 0,5 < α < 1. Um valor alto de α resulta em menos saldos, tornando a inserção mais rápida, mas as pesquisas e exclusões mais lentas, e vice-versa para um valor baixo de α. Portanto, em aplicações práticas, um α pode ser escolhido dependendo da frequência com que essas ações devem ser executadas.

A busca não é modificada a partir de uma árvore de pesquisa binária padrão e tem um tempo de pior caso de ${\displaystyle O(\log n)}$. Isto contrasta com as árvores splay que têm o pior tempo de ${\displaystyle O(n)}$. A redução da sobrecarga de memória do nó, em comparação com outras árvores de pesquisa binária autobalanceadas, pode melhorar ainda mais a localidade de referência e o armazenamento em cache.

A inserção é implementada com as mesmas ideias básicas de uma árvore de busca binária não balanceada, porém com algumas mudanças significativas.

Ao encontrar o ponto de inserção, a profundidade do novo nó também deve ser registrada. Isso é implementado por meio de um contador simples que é incrementado durante cada iteração da pesquisa, contando efetivamente o número de arestas entre a raiz e o nó inserido. Se este nó violar a propriedade α-height-balance (definida acima), um rebalanceamento será necessário.

Para reequilibrar, uma subárvore inteira cujo nó raíz é um bode expiatório passa por uma operação de balanceamento. O bode expiatório é definido como sendo um ancestral do nó inserido que não é balanceado em peso α. Sempre haverá pelo menos um ancestral assim. Rebalancear qualquer um deles restaurará a propriedade de equilíbrio de altura α.

Uma maneira de encontrar um bode expiatório é subir do novo nó de volta até a raiz e selecionar o primeiro nó que não está balanceado em peso α.

Subir de volta à raiz requer ${\displaystyle O(\log n)}$ espaço de armazenamento, geralmente alocado na pilha, ou ponteiros pais. Na verdade, isso pode ser evitado apontando cada filho para o pai/mãe enquanto se desce, reparando na volta.

Para determinar se um nó potencial é um bode expiatório viável, precisamos verificar sua propriedade de balanceamento de peso α. Para fazer isso, podemos voltar à definição:

size(left) ≤ α*size(node)
size(right) ≤ α*size(node)

No entanto, uma grande otimização pode ser feita ao perceber que já conhecemos dois dos três tamanhos, deixando apenas o terceiro para ser calculado.

Considere o exemplo a seguir para demonstrar isso. Supondo que estamos subindo de volta à raiz:

size(parent) = size(node) + size(sibling) + 1

Mas como:

size(inserted node) = 1.

O caso é trivializado para:

size[x+1] = size[x] + size(sibling) + 1

Onde x = este nó, x + 1 = pai e size(sibling) é a única chamada de função realmente necessária.

Uma vez encontrado o bode expiatório, a subárvore enraizada no bode expiatório é completamente reconstruída para ficar perfeitamente equilibrada. ^[2] Isso pode ser feito em ${\displaystyle O(n)}$ tempo percorrendo os nós da subárvore para encontrar seus valores em ordem classificada e escolhendo recursivamente a mediana como a raiz da subárvore.

À medida que as operações de reequilíbrio ocorrem ${\displaystyle O(n)}$ tempo (dependente do número de nós da subárvore), a inserção tem um desempenho de pior caso de ${\displaystyle O(n)}$ tempo. No entanto, como esses cenários de pior caso estão espalhados, a inserção ocorre ${\displaystyle O(\log n)}$ tempo amortizado.

Defina o desequilíbrio de um nó v como o valor absoluto da diferença de tamanho entre o nó esquerdo e o nó direito menos 1 ou 0, o que for maior. Em outras palavras:

${\displaystyle I(v)=\operatorname {max} (|\operatorname {left} (v)-\operatorname {right} (v)|-1,0)}$

Imediatamente após reconstruir uma subárvore com raiz em v, I( v ) = 0.

Lema: Imediatamente antes de reconstruir a subárvore com raiz em v, ${\displaystyle I(v)\in \Omega (|v|)}$ ( ${\displaystyle \Omega }$ é a notação Big Omega .)

Prova do lema:

Deixe ${\displaystyle v_{0}}$ ser a raiz de uma subárvore imediatamente após a reconstrução . ${\displaystyle h(v_{0})=\log(|v_{0}|+1)}$ . Se houver ${\displaystyle \Omega (|v_{0}|)}$ inserções degeneradas (ou seja, onde cada nó inserido aumenta a altura em 1), então ${\displaystyle I(v)\in \Omega (|v_{0}|)}$, ${\displaystyle h(v)=h(v_{0})+\Omega (|v_{0}|)}$ e ${\displaystyle \log(|v|)\leq \log(|v_{0}|+1)+1}$ .

Dado que ${\displaystyle I(v)\in \Omega (|v|)}$ antes da reconstrução, havia ${\displaystyle \Omega (|v|)}$ inserções na subárvore enraizada em ${\displaystyle v}$ que não resultaram em reconstrução. Cada uma dessas inserções pode ser realizada em ${\displaystyle O(\log n)}$ tempo. A inserção final que causa custos de reconstrução ${\displaystyle O(|v|)}$. Usando a análise amortizada, fica claro que o custo amortizado de uma inserção é ${\displaystyle O(\log n)}$ :

${\displaystyle {\Omega (|v|)O(\log n)+O(|v|) \over \Omega (|v|)}=O(\log n)}$

Árvores scapegoat são incomuns porque a exclusão é mais fácil do que a inserção. Para permitir a exclusão, as árvores scapegoat precisam armazenar um valor adicional com a estrutura de dados da árvore. Esta propriedade, que chamaremos de MaxNodeCount, representa simplesmente o maior NodeCount alcançado. Ele é definido como NodeCount sempre que a árvore inteira é rebalanceada e, após a inserção, é definido como max(MaxNodeCount, NodeCount).

Para realizar uma exclusão, simplesmente removemos o nó como faríamos em uma árvore de pesquisa binária simples, mas se

NodeCount ≤ α*MaxNodeCount

Então rebalanceamos toda a árvore em torno da raiz, lembrando de definir MaxNodeCount como NodeCount.

Isso dá à exclusão o pior desempenho possível ${\displaystyle O(n)}$ tempo, enquanto o tempo amortizado é ${\displaystyle O(\log n)}$ .

Suponha que a árvore scapegoat tenha ${\displaystyle n}$ elementos e foi reconstruída recentemente (em outras palavras, é uma árvore binária completa). No máximo ${\displaystyle n/2-1}$ exclusões podem ser executadas antes que a árvore precise ser reconstruída. Cada uma dessas exclusões leva ${\displaystyle O(\log n)}$ tempo (a quantidade de tempo para procurar o elemento e sinalizá-lo como excluído). O ${\displaystyle n/2}$ a exclusão faz com que a árvore seja reconstruída e assuma ${\displaystyle O(\log n)+O(n)}$ (ou apenas ${\displaystyle O(n)}$ ) tempo. Usando a análise agregada, fica claro que o custo amortizado de uma exclusão é ${\displaystyle O(\log n)}$ :

${\displaystyle {\sum _{1}^{n/2}O(\log n)+O(n) \over n/2}={{n \over 2}O(\log n)+O(n) \over n/2}=O(\log n)\ }$

O nome Árvore scapegoat (árvore do bode expiatório) "[...] é baseado na sabedoria popular de que, quando algo dá errado, a primeira coisa que as pessoas tendem a fazer é encontrar alguém para culpar (o bode expiatório)." ^[3] Na Bíblia, um bode expiatório é um animal que é ritualmente sobrecarregado com os pecados dos outros e depois expulso.

• Árvore splay
• Árvores
• Rotação de árvores
• Árvore AVL
• Árvore B
• Árvore em T

• Galpern, Igal. On Consulting a Set of Experts and Searching (PDF) (Ph.D. thesis) 
• Morin, Pat. «Chapter 8 - Scapegoat Trees». Open Data Structures (in pseudocode) 0.1G β ed. [S.l.: s.n.] Consultado em 16 de setembro de 2017