Please enable JavaScript.

Coggle requires JavaScript to display documents.

ÁRVORES DE BUSCA BALANCEADA - Coggle Diagram

- - - - Árvores auto-balanceáveis
      - Diferentes formas de implementação
        
        Ex: Árvore AVL
        
        Fator de equilíbrio
        
        A diferença entre as alturas das sub-árvores esquerda e direita
        
        Definição
        
        É uma árvore binária na qual o fator de equilíbrio de cada nó é ou 0 ou 1 ou -1
        
        A altura de uma árvore vazia é definida como -1
        
        Se a inserção de um nó desbalancear uma árvore AVL, aplica-se uma rotação
        
        A rotação é uma transformação local da sub-árvore cuja raíz é o nó que ficou com o fator de equilíbrio igual a 2 ou -2
        
        4 tipos de rotação
        
        Rotação simples para a direita
        
        Rotacionar a aresta que conecta a raíz e seu filho da esquerda
        
        Feita depois que uma nova chave é inserida na sub-árvore da esquerda do filho da esquerda de uma árvore cuja raíz já tinha o fator de 1
        
        Rotação simples para a esquerda
        
        O espelhamento da rotação simples para a direita
        
        Feita depois que uma nova chave é inserida na sub-árvore da direita do filho da direita de uma árvore cuja raíz já tinha o fator de -1
        
        Rotação esquerda-direita
        
        Combinação da rotação simples para a esquerda e da rotação simples para a direita
        
        A rotação simples para a esquerda é feita na sub-árvore da esquerda da raíz r
        
        A rotação simples para a direita é feita na nova árvore enraizada em r
        
        É feita depois da inserção de uma nova chave na sub-árvore da direita do filho da esquerda de uma árvore cuja raíz tinha o fator de 1
        
        Rotação direita-esquerda
        
        É a versão espelhada da rotação esquerda-direita
        
        É feita depois da inserção de uma nova chave na sub-árvore da esquerda do filho da direita de uma árvore cuja raíz tinha o fator de -1
        
        As rotações podem ser feitas em tempo constante
        
        Se houver vários nós com o fator sendo 2 ou -2
        
        1 more item...
        
        Eficiência
        
        É limitada tanto superiormente quanto inferiormente por funções logarítimicas e depende da altura da árvore
        
        As operações de busca, inserção e exclusão pertencem a \(\Theta(\log n)\)
        
        Desvantagens: a necessidade de manter a árvore equilibrada e as rotações constantes