Please enable JavaScript.

Coggle requires JavaScript to display documents.

Árvores, Árvore Binária de Busca - Coggle Diagram

- - - - 1 filho direito
      - 1 filho esquerdo
    - - Conjunto de nós finitos vazio ou é uma raiz e duas árvores
        
        Subárvore esquerda
        
        Subárvore direita
    - - Calcular altura de árvore binária através de algoritmo recursivo
        
        Medido através do número de nós
        
        h(x)=1+max(h(x1)+h(x2))
        
        h(x)
        
        Altura da árvore
        
        h(x1)
        
        Altura da subárvore da esquerda
        
        h(x2)
        
        Altura da subárvore da direita
        
        Árvore vazia a altura é -1
        
        Operação mais executada
        
        Verificar se a árvore não está vazia
        
        Substituição da árvore vazia por nós especiais
        
        Nós originais
        
        Internos
        
        Extensão da árvore binária vazia
        
        Único nó externo
        
        Nós extras
        
        Externos
        
        O algoritmo faz uma adição para cada nó interno e uma comparação para verificar se a árvore está vazia para cada nó interno e externo
        
        Nós extenos= Nós internos+1
        
        Verificar a eficiência do algoritmo
        
        Saber quantos nós externos uma árvore com n nós internos pode ter
        
        Número de comparações para saber se a árvore está vazia
        
        C(n)=n+x=2n+1
        
        n = quantida de nós internos
        
        x = quantida de nós externos
        
        Número de adições
        
        A(n)=n
        
        Travessias
        
        Ordem
        
        Raiz
        
        Direita
        
        Esquerda
        
        Pós-ordem
        
        Direita
        
        Raiz
        
        Esquerda
        
        Pré-Ordem
        
        Esquerda
        
        Direita
        
        Raiz
        
        Visita nós de uma árvore recursivamente
        
        Nem todos os problemas requerem travessias de subárvores da esquerda e da direita
        
        Pesquisa e Inserção
        
        Requer processamento de apenas uma das subárvores
        
        Eficiência parecida com algoritmo de altura
        
        Chamada recursiva para cada nó
- - - - First Child
    - - Next Sibling
- - - - Se não for tem-se 2 possibilidades
        
        Se o elemento procurado for menor que a raiz
        
        Pesquisa na subárvore da direita
        
        Pesquisa na subárvore da esquerda
        
        Se o elemento procurado for maior que a raiz
      - Se a raiz for o elemento procurado, interrompe-se a busca
    - - Algoritmo de redução de tamanho variável
        
        Variação da altura
    - - Pior caso
        
        Θ(n)
        
        n comparações
        
        Sequência crescente ou decrescente
      - Caso médio
        
        Θ(log n)