Please enable JavaScript.

Coggle requires JavaScript to display documents.

Árvores - Coggle Diagram

- - - - Por isso, podemos escolher um vértice arbitrariamente e chamá-lo de raiz, que vai ser o nosso nível "zero" da árvore
        
        Vértices sem filhos são chamados de folhas
    - - Para cada vértice v em uma árvore, temos que os vértices passados desde a raiz até chegar naquele vértice v são ditos seus ancestrais
        
        O ancestral mais próximo de v é dito pai de v, enquanto v seria o filho desse pai. Vértices que possuem o mesmo pai são irmãos.
        
        Todos os vértices para qual um vértice v é um ancestral são chamados de descendentes de v.
        
        Todos os descendentes de v com todas as arestas os conectado formam uma subárvore com raiz em v.
- - - - Uma árvore binária em que o número designado para cada vértice pai é maior que todos os números na sua subárvore filha esquerda e menor que todos os números na sua subárvore filha direita.
        
        Busca e Inserção em uma ABB
        
        Para buscar um elemento em uma ABB, podemos buscá-lo recursivamente, de modo que se a árvore está fazia, então a busca falha; Se não, comparamos o valor com a raiz da árvore, se for menor, procuramos na subárvore da esquerda, enquanto se for maior, procuramos na subárvore da direita. Quando o elemento for igual, então a busca acaba, achamos o elemento.
        
        O pior caso é O(N) sendo N o número de comparações para um elemento An-1, mas o tempo em média é O(log n).
        
        A inserção é quase igual a busca.
      - Geralmente é implementada para fins computacionais como uma coleção de nodes que correspondem aos vértices da árvore
        
        Cada nó tem uma informação associada com um vértice e dois ponteiros para os nós que representam o filho esquerdo e o filho direito
        
        O ponteiro esquerdo aponta para o primeiro filho do vértice enquanto o ponteiro direito aponta para seu próximo irmão
        
        Tal representação é dita first child-next sibling representation
        
        Portanto, todos os irmãos de um vértice são conectados pelos ponteiros da direita em uma lista unicamente ligada, com o primeiro elemento da lista apontando para o ponteiro esquerdo de seu pai.
- - - - A raiz é visitada, depois a subárvore esquerda, depois a subárvore direita.
    - - Primeiro a subárvore direita é visitada, depois a subárvore esquerda, depois a raiz.
    - - A subárvore esquerda é visitada primeiro, depois a direita, depois a raiz.