Please enable JavaScript.

Coggle requires JavaScript to display documents.

M9 (Mapa Mental 9) - Coggle Diagram

- - - - Duas Soluções
        
        Mudança-Representação
        
        Possibilitam mais de um elemento em um nó de uma árvore de busca.
        
        Árvores 2-3-4
        
        Árvores B
        
        O mais geral e mais importante
        
        Árvores 2-3
        
        Diferem entre si no número de elementos admissíveis em um único nó, mas todos são perfeitamente balanceados.
        
        Árvore binária de busca balanceada
        
        Árvore Rubro-negra
        
        Tolera a altura de uma sub-árvore ser o dobro do tamanho das outras sub-árvores no nó.
        
        Se a inserção ou deleção de um novo nó cria uma árvore que quebra o balanço de requerimento da ordem, a árvore é reestruturada por uma família de transformações especiais.
        
        Rotações
        
        1 more item...
        
        Árvore AVL
        
        Rotação
        
        R-Rotação
        
        Também chamada de rotação de direita singular. Feita após inserir a nova chave na sub-árvore esquerda da filha da árvore cuja raiz tem balanço +1 antes da inserção.
        
        L-Rotação
        
        Também chamada de rotação de esquerda singular. Feita após inserir a nova chave na sub-árvore direita da filha da árvore cuja raiz tem balanço -1 antes da inserção.
        
        LR-Rotação
        
        Uma combinação de duas rotações: uma L-Rotação da sub-árvore esquerda da raiz r, seguido por uma R-Rotação da nova árvore enraizada em r. É feita quando a nova chave é inserida na sub-árvore direita da filha esquerda da árvore cuja raiz tinha balanço +1 antes da inserção.
        
        RL-Rotação
        
        Uma combinação de duas rotações: uma R-Rotação da sub-árvore direita da raiz r, seguido por uma L-Rotação da nova árvore enraizada em r. É feita quando a nova chave é inserida na sub-árvore esquerda da filha direita da árvore cuja raiz tinha balanço -1 antes da inserção.
        
        Uma transformação local feita se a inserção de um novo nó deixa a árvore AVL desbalanceada.
        
        É feita na sub-árvore enraizada no nó cujo balanço está em +2 ou -2. Se tem mais de um desses nós, rotacionamos a árvore enraizada no nó desbalanceado que está mais próximo da nova folha,
        
        Note que as rotações não são transformações triviais. Felizmente, podem ser feitas em tempo constante.
        
        Balance Factor
        
        A diferença entre as alturas da sub-árvore esquerda e direita do nó. Na árvore AVL é ou 0, ou +1 ou -1.
        
        A altura de uma árvore vazia é -1.
        
        Eficiência
        
        Como com qualquer árvore de busca, a característica crítica é a altura. Tanto acima quanto abaixo, ela é limitado por funções logaritmicas.
        
        Na worst-case, busca e inserção são Θ(log)n
        
        1 more item...
        
        Deleção de chaves na AVL é significamente mais difícil que inserção, mas tem a mesma classe de eficiência que inserção; logaritmica.
        
        1 more item...