Please enable JavaScript.

Coggle requires JavaScript to display documents.

M8 (Levitin) - Coggle Diagram

- - - - Árvores de Busca Balanceadas
        
        Duas abordagens para esse conceito são:
        
        Árvores com Auto-Balanceamento (Self-Balancing), uma variedade de "simplificação da situação" (instance-simplification) na qual são alteradas as posições dos nós para que as árvores estejam sempre balanceadas.
        
        Dependendo da definição de "balanceamento", podem ser estruturadas de diferentes formas, como por exemplo:
        
        Árvores AVL
        
        São árvores cujo balanceamento é alcançado quando a diferença de altura entre as sub-árvores da direita e da esquerda em relação a um nó nunca excede 1
        
        1 more item...
        
        As rotações são realizadas sobre sub-árvores enraizadas em um nó cujo fator de equilíbrio seja +2 ou -2. Caso haja mais de um nó desse tipo, será selecionado aquele mais próximo da folha que foi inserida ou removida. Existem 2 tipo de rotação:
        
        2 more items...
        
        A altura h de qualquer Árvore AVL respeita a desigualdade:
        floor(log(n) (2)) <= h < 1,4405 log(n+2) (2) -
        1,3277
        Consequentemente, as operações de inserção e busca, no pior caso, possuem eficiência em θ(log(n))
        
        1 more item...
        
        Dentre as desvantagens das Árvores AVL, estão as constantes rotações e a necessidade de manter sempre o balanceamento para todos os nós
        
        Árvores Rubro-Negras (Red-Black Trees)
        
        São árvores cujo é balanceamento é alcançado quando uma sub-árvore de um nó tiver no máximo o dobro da altura da outra sub-árvore do mesmo nó.
        
        Sempre que uma operação de inserção ou remoção desbalanceia a árvore, ela será re-balanceada, através de uma transformação chamada rotação que pode ser aplicada de diferentes formas
        
        Uma variedade de "modificação da representação" (representation-change) na qual são permitidos mais de um elemento sendo armazenados em um mesmo nó de um árvore.
        
        A depender da quantidade de elementos admitidos em um mesmo nó, podem ser estruturados de diferentes formas, como Árvores 2-3, Árvores 2-3-4 e Árvores-B, por exemplo.