Árvore Scapegoat
Na ciência da computação, uma árvore scapegoat é uma árvore de busca binária autobalanceada inventada por Arne Andersson em 1989 e novamente por Igal Galperin e Ronald L. Rivest em 1993. A árvore scapegoat fornece o pior caso de para tempo de pesquisa e para tempo de inserção e exclusão amortizado.
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: Onde o tamanho pode ser definido recursivamente como: 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 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. 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.
Busca
A busca não é modificada a partir de uma árvore de pesquisa binária padrão e tem um tempo de pior caso de O ( log n ) {\displaystyle O(\log n)} . Isto contrasta com as árvores splay que têm o pior tempo de O ( n ) {\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.
Inserção
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 α.
Remoção
Á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 Então rebalanceamos toda a árvore em torno da raiz, lembrando de definir MaxNodeCount como NodeCount.
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)." Na Bíblia, um bode expiatório é um animal que é ritualmente sobrecarregado com os pecados dos outros e depois expulso.
