Please enable JavaScript.

Coggle requires JavaScript to display documents.

Mapa Mental 8, a (Raiz) - Coggle Diagram

- - - - Essa é a representação mais comum, e preferível, de árvores em ciência da computação
      - Aplicações:
        
        Implementação de hierarquias
        
        Implementação de dicionários
        
        Codificação de dados
        
        As chamadas state-space trees são usadas em dois tipos de design de algoritmos, backtracking e brach-and-bound
      - Dado um certo vértice v, podemos fazer algumas classicações para outros vértices relacionados a ele, na árvore:
        
        Ancestrais reais: de u1 até a raiz
        
        Ancestrais: de v até a raiz
        
        Pai: u1
        
        Filhos: w1 e w2
        
        Descendentes: de v para baixo
        
        Descendentes reais: de w1 e w2 para baixo
        
        Irmão: v0
        
        Folha: essa classificação não é relacionada a v, são vértices que não possui filhos, exemplo são v0 e u2
        
        Parental: vértice com pelo menos um filho
        
        Subárvore: Basicamente uma árvore dentro da árvore maior (T), com raiz em v, com seus galhos sendo seus descendentes
        
        Profundidade de v: será o tamanho de o caminho mais curto da raiz (a) até v
        
        Altura: A altura de uma árvore T será o tamanho do caminho mais comprido da raiz(a) para uma folha
      - Árvores Ordenadas
        
        São árvores enraizadas em que os filhos de cada vértice são ordenados (geralmente da esquerda para a direita)
        
        Árvores Binárias
        
        Uma árvore ordenada em que cada vértice tem, no máximo, dois filhos
        
        Um é chamado de filho esquerdo, e é geralmente atribuído um valor menor que o do pai na ordenação
        
        Quando esse tipo de atribuição é feita, chamamos a árvore de árvore de busca binária
        
        Sua eficiência é dependente de sua altura
        
        Pode ser feita no mesmo estilo que se faz lista ligadas, uma estrutura (nó) com um valor e até dois ponteiros apontando para outros nós
        
        Procura e inserção de elementos
        
        4 more items...
        
        Enquanto outro é chamado de filho direito, e é geralmente um valor maior que o do pai na ordenação
        
        Um exemplo de árvore binária é a árvore amarela à esquerda
        
        Travessia de árvores binárias
        
        Como árvores binárias podem ser tecnicamente vistas como uma composição de duas sub-árvores, e assim sucessivamente, suas funções de travessias são recursivas e seu tempo de execução é atrelado diretamente à sua altura
        
        Exemplo:
        
        Para calcular altura de uma árvore binária, é só ir comparando a maior altura entre a subárvore da esquerda e a da direita, que para isso, essa comparação é feita sucessivamente em ambas as subárvores, e assim por diante (e adicionar +1 no final, já que o algoritmo acaba não contando com a raiz)
        
        2 more items...
        
        Tipos de travessias em algoritmos dividir-e-conquistar:
        
        Travessia preorder: Comparações são feitas na ordem; raiz, sub-árvore esquerda, sub-árvore direita
        
        Travessia inorder: Comparações são feitas na ordem; sub-árvore esquerda, raiz, sub-árvore direita
        
        Travessia postorder: Comparações são feitas na ordem; sub-árvore esquerda, sub-árvore direita, raiz
      - São na verdade uma representação de uma árvore qualquer, com um vértice definido como sua raiz
- - - - v
        
        w2
        
        x3
        
        ..........................................
        
        .................
        
        x4
        
        .........................................
        
        .....................
        
        w1
        
        x2
        
        ............................................................
        
        ..........................
        
        x1
        
        .......................
        
        ....................................
      - v0