Please enable JavaScript.

Coggle requires JavaScript to display documents.

Árvores, a (b, c), b (d, e) - Coggle Diagram

- - - - Nele, o vértice "a" cumpre o papel de raiz
  - - - Os vértices que fazem parte do caminho de um vértice para a raiz, são chamados de "ancestrais"
        
        Assim, os vértices "a", "b" e "d" são ancestrais de "d"
        
        Nota-se que um vértice é ancestral de si mesmo
        
        Os ancestrais de um vértices não incluindo o próprio vértice são chamados "ancestrais próprios" do vértice
        
        No exemplo, "a" e "b" são os ancestrais próprios tanto de "d" quanto de "e"
        
        Todos os vértices para os quais um vértice v é ancestral são chamados "descendentes" de v
        
        Assim como os ancestrais, os descendentes de um vértice incluem o próprio vértice. Os descendentes de um vértice diferentes de si são os "descendentes próprios" do vértice
        
        O primeiro ancestral próprio no caminho de um vértice à raiz é chamado o "pai" (parent) do vértice, e o vértice é chamado "filho" do pai
        
        Os filhos de um mesmo pai são "irmãos"
        
        2 more items...
        
        No exemplo, "b" é pai de "d" e "e", e "d" e "e" são filhos de b
        
        "b", "c", "d" e "e" são os descendentes próprios de "a"
        
        Assim, "a", "b", "c", "d" e "e" são todos descendentes de "a"
    - - Uma árvore ordenada é uma árvore onde todos os filhos de um vértice estão ordenados
        
        Convenciona-se considerar que os filhos são ordenados da esquerda para a direita
      - Ávores Binárias
        
        Árvore binária é um tipo especial de árvore ordenada na qual todo vértice tem dois filhos no máximo
        
        Esses filhos são chamados filhos esquerdo e direito
        
        A árvore do exemplo é uma árvore binária
        
        Como toda subárvore de uma árvore binária também é uma árvore binária, pode-se observar uma recursão
        
        Na computação. elas são implementadas com nódulos
        
        Cada nódulo teria informações correspondentes aos vértices, como um valor de um tipo de dado, e referências para os dois filhos, o primeiro apontando para o filho esquerdo e o segundo, para o direito
        
        Essa representação, no entanto, não é prática para árvores de com números variáveis de filhos
        
        Árvores de Busca Binárias
        
        Estas são árvores binárias nas quais os filhos esquerdos tem valores menores que seus pais, e os direitos, valores maiores
        
        Elas também podem ser generalizadas para criar "multiway search trees", usadas para acessar grandes agrupamentos de dados de forma eficient
        
        Graças a essa organização, realizar uma busca em uma árvore binária é uma operação simples e de eficiência da classe logarítmica
        
        Começamos a busca verificando se a árvore está vazia. Se estiver, a busca falhou
        
        Se não estiver, verificamos o valor em sua raiz
        
        3 more items...
        
        Atravessando Árvores Binárias
        
        Para facilitar a visualização e cáluclo de eficiência de algoritmos que percorrem uma árvore, pode-se considerar as subárvores vazias (filhos faltantes) de uma árvore como nódulos especiais
        
        Estes nódulos são chamados externos, e os nódulos regulares da árvore, internos
        
        Com isso em mente, podemos avaliar o algoritmo que determina a altura de uma árvore
        
        1 more item...
        
        No algoritmo de busca na árvore binária, não era preciso verificar as duas subárvores de cada árvore, mas em um algoritmo como o para determinar a altura da árvore, isso é necessário
        
        Em algoritmos com essa necessidade, as subárvores podem ser percorridas de três formas
        
        Preordem
        
        2 more items...
- - - - Ex.: Seu número de pontas é sempre igual ao número total de vértices menos 1
        
        Para cada dois vértices de uma árvore, sempre existe um caminho simples que os ligue