Please enable JavaScript.

Coggle requires JavaScript to display documents.

M8 (Mapa Mental 8) - Coggle Diagram

- - - - Uma árvore enraizada em que todos os filhos de cada vértice são ordenados. É conveniente assumir que no diagrama os filhos são ordenados da esquerda a direita
        
        Árvore de Busca Binária
        
        Árvore de Busca Multiway
        
        Busca
        
        Buscando v, fazemos recursivamente
        
        Se a árvore for vazia, termina falhando.
        
        Se não vazia, comparamos v com a raiz K(r).
        
        Se não são o mesmo, continuamos a busca na sub-árvore esquerda da raiz se v < K(r), e direita se v > K(r)
        
        3 more items...
        
        Se são o mesmo, a busca teve sucesso e terminamos aqui.
        
        Árvores em que o número para cada vértice parental é maior que todos números da sub-árvore esquerda e maiores que todos números da sub-árvore direita
        
        Árvore Binária
        
        Travessia de Árvores Binárias
        
        Muitos problemas relacionados à árvore binária podem ser resolvidos pelo divide-and-conquer
        
        Isso, claro, porque por natureza esse tipo de árvore já se mostra "dividida"
        
        Podemos por exemplo computar a altura da árvore como o máximo de alturas da sub-árvore esquerda e direita da raiz.
        
        Os três mais importantes algoritmos divide-and-conquer para árvores binárias são as três clássicas travessias
        
        Travessia entre-ordem
        
        1 more item...
        
        Travessia pós-ordem
        
        1 more item...
        
        Travessia pre-ordem
        
        1 more item...
        
        Uma árvore ordenada em que toda vértice tem não mais que dois filhos, o esquerdo e o direito.
        
        Pode também ser vazia
        
        A árvore binária com raiz na filha esquerda ou direita de uma vértice de uma árvore binária chama-se a sub-árvore esquerda ou sub-árvore direita
        
        Como as sub-árvores também são binárias, árvores binárias podem ser definidas recursivamente.
        
        Sua eficiência depende de sua altura.
        
        Uma possível representação de computador para uma árvore ordenada arbitrariamente pode ser feita simplesmente tendo uma vértice parente com o número de pointers igual ao número de filhos
        
        Isso pode soar inconsistente se o número de filhos varia muito entre nodes
        
        Evitamos isso usando um node com apenas dois pointers. Aqui, o esquerdo aponta pro primeiro filho, e o direito o próximo
        
        First child-next sibling representation
    - - Podemos então selecionar um vértice arbitrário e considerar como a raiz
        
        Colocamos a raiz no topo (nível zero) e as vértices adiantes em baixo.
        
        Árvores enraizadas tem papel crítico na ciência da computação; mais do que raiz livres. Dessa forma simplesmente a chamamos de "árvores", na maioria dos casos.
        
        Aplicações
        
        Dicionários
        
        Data sets grandes
        
        Hierarquias
        
        Encoding de data
        
        Análise de algoritmos recursivos
        
        Árvores State-Space
        
        Backtracking e branch-and-bound
        
        Para qualquer vértice v, as vértices entre ele e o caminho simples até a raiz são seus ancestrais.
        
        O vértice é seu próprio ancestral. Um set de ancestrais em que ele não é o de "Ancestrais Adequados"
        
        A vértice diretamente antes de v é seu parente, e v é seu filho. Vértices igualmente filhas de um mesmo pai são irmãs.
        
        Uma vértice sem filhos é uma folha
        
        Todo vértice para qual v é um ancestral é seu descendente
        
        Os "Descendentes Adequados" excluem o vértice v em si
        
        Todos os descendentes de v com todos seus edges conectando-os formam o sub-árvore de T enraizada em tal vértice
        
        Um vértice com no mínimo um filho é dito parental
        
        A profundidade de um vértice v é o comprimento do caminho simples dele até a raiz.
        
        A altura de uma árvore é o comprimento do mais longo caminho simples da raiz até uma folha.
  - - - O número de arestas é sempre um menos do que o número de vértices