Please enable JavaScript.

Coggle requires JavaScript to display documents.

Árvores - Coggle Diagram

- - - - Observe que um número atribuído a cada vértice parental é maior do que todos os números em sua subárvore esquerda e menores do que todos os números em sua subárvore direita.
        Essas árvores são chamadas de árvores binárias de pesquisa. Árvores binárias e árvores binárias de pesquisa têm uma ampla variedade de aplicações em ciência da computação;
      - A eficiência dos algoritmos mais importantes para árvores de pesquisa binárias e suas extensões depende da altura da árvore. Portanto, as seguintes desigualdades para a altura h de uma árvore binária com n nós são especialmente importantes para a análise de tais algoritmos.
      - Busca
        
        Quando precisamos pesquisar um elemento de um determinado valor v em tal árvore, fazemos isso recursivamente da seguinte maneira. Se a árvore estiver vazia, a busca termina em fracasso. Se a árvore não estiver vazia, comparamos v com a raiz da árvore K (r). Se eles corresponderem, um elemento desejado será encontrado e a pesquisa pode ser interrompida; se não coincidirem, continuamos com a busca na subárvore esquerda da raiz se v <K (r) e na subárvore direita se v> K (r). Assim, a cada iteração do algoritmo, o problema de pesquisa em uma árvore de pesquisa binária é reduzido a pesquisar em uma árvore de pesquisa binária menor. A medida mais sensata do tamanho de uma árvore de busca é sua altura; obviamente, a diminuição na altura de uma árvore normalmente muda de uma iteração para outra da pesquisa da árvore binária - dando-nos, assim, um excelente exemplo de um algoritmo de diminuição de tamanho variável.
        
        No pior caso da pesquisa por árvore binária, a árvore é severamente distorcida. Isso acontece, em particular, se uma árvore é construída por inserções sucessivas de uma sequência crescente ou decrescente de chaves
        
        Obviamente, a busca por um n − 1 em tal árvore requer n comparações, fazendo com que a eficiência de pior caso da operação de busca caia em Theta(n). Felizmente, a eficiência de caso médio acaba sendo em Theta (log n).
      - Inserção
        
        Desde a inserção de uma nova chave em uma árvore de pesquisa binária é quase idêntica àquela da busca, ela também exemplifica a técnica de redução de tamanho variável e tem as mesmas características de eficiência da operação de busca
    - - Uma árvore binária T é definida como um conjunto finito de nós que está vazio ou consiste em uma raiz e duas árvores binárias disjuntas TL e TR chamadas, respectivamente, as subárvores esquerda e direita da raiz. Normalmente pensamos em uma árvore binária como um caso especial de uma árvore ordenada
      - Algortimo para achar a altura de uma árvore
        
        Como a própria definição divide uma árvore binária em duas estruturas menores do mesmo tipo, a subárvore esquerda e a subárvore direita, muitos problemas sobre árvores binárias podem ser resolvidos aplicando-se a técnica de dividir e conquistar. Como exemplo, vamos considerar um algoritmo recursivo para calcular a altura de uma árvore binária.
        Lembre-se de que a altura é definida como o comprimento do caminho mais longo da raiz até uma folha. Portanto, pode ser calculado como o máximo das alturas das subárvores esquerda e direita da raiz mais 1. (Temos que adicionar 1 para contabilizar o nível extra da raiz.) Observe também que é conveniente definir a altura de a árvore vazia como -1.
        É fácil ver que o algoritmo de altura faz exatamente uma adição para cada nó interno da árvore estendida e faz uma comparação para verificar se a árvore está vazia para cada nó interno e externo. Portanto, para verificar a eficiência do algoritmo, precisamos saber quantos nós externos uma árvore binária estendida com n nós internos pode ter.
      - Travessias clássicas
        
        Os algoritmos de divisão e conquista mais importantes para árvores binárias são as três travessias clássicas: preorder, inorder, and postorder. Todos os três percursos visitam nós de uma árvore binária recursivamente, ou seja, visitando a raiz da árvore e suas subárvores esquerda e direita. Eles diferem apenas pelo momento da visita da raiz
        
        No percurso da preorder, a raiz é visitada antes das subárvores esquerda e direita são visitados (nessa ordem). Na travessia da inorder, a raiz é visitada depois de visitar sua subárvore esquerda, mas antes de visitar a subárvore certa.Na travessia de postorder, a raiz é visitada depois de visitar o lado esquerdo e direito subárvores (nessa ordem). Quanto à sua análise de eficiência, é idêntica à análise do algoritmo de Altura porque uma chamada recursiva é feita para cada nó de uma árvore binária estendida
        
        Nem todas as perguntas sobre árvores binárias requerem travessias das subárvores esquerda e direita. Por exemplo, as operações de pesquisa e inserção para uma árvore de pesquisa binária requerem o processamento de apenas uma das duas subárvores