Please enable JavaScript.

Coggle requires JavaScript to display documents.

ÁRVORES - Coggle Diagram

- - - - Muito importante para a ciência da computação
      - Árvore Binária de Busca
        
        Pior caso é quando os elementos são inseridos em ordem estritamente crescente ou decrescente
        
        Todas as operações passam a custar Θ(n)
        
        Operação de busca
        
        Operação de Inserção
        
        No caso geral têm custo Θ(log n)
        
        Implementadas de forma recursiva
      - Todo vértice não tem mais que dois filhos
      - Implementada por conjunto de nódulos, cada um contendo um elemento, um ponteiro para o filho da esquerda e um ponteiro para o filho da direita
      - Operações geralmente implementadas de forma recursiva
        
        Percurso
        
        Pré-ordem
        
        raiz -> sub-árvore da esquerda -> sub-árvore da direita
        
        Intra-ordem
        
        sub-árvore da esquerda -> raiz -> sub-árvore da direita
        
        Pós-ordem
        
        sub-árvore da esquerda -> sub-árvore da direita -> raiz
        
        Altura
        
        Se o nódulo é vazio, retorna -1
        
        Se o nódulo não é vazio, retorna max(altura da sub-árvore esquerda, altura da sub-árvore direita
        
        Análise é auxiliada pela transformação da árvore binária em árvore binária completa por meio da adição de nódulos imaginários chamados de externos
        
        Número de nódulos externos = Número de nódulos internos +1