Please enable JavaScript.

Coggle requires JavaScript to display documents.

Trees - Coggle Diagram

- - - - 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 corresponderem, um elemento desejado será encontrado e a pesquisa poderá 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).
    - - a árvore está severamente distorcida. Isto acontece, em particular, se uma árvore for construída por inserções sucessivas de uma sequência crescente ou decrescente de chaves.
      - Eficiência cai para (n)
- - - - [log2 n] ≤ h ≤ n − 1.
        
        h -> altura; n -> qtd. nós
- - - - Uma árvore enraizada é geralmente representada colocando sua raiz no topo (nível 0 da árvore), os vértices adjacentes à raiz abaixo dela (nível 1), os vértices duas arestas de distância da raiz ainda abaixo (nível 2) e breve.
      - Aplicações
        
        descrição de hierarquias, desde diretórios de arquivos até organogramas de empresas
        
        implementação de dicionários
        
        acesso eficiente a conjuntos de dados muito grandes
        
        codificação de dados
      - Para qualquer vértice v em uma árvore T, todos os vértices no caminho simples da raiz até aquele vértice são chamados de ancestrais de v. O próprio vértice é geralmente considerado seu próprio ancestral.
        
        o conjunto de ancestrais que exclui o próprio vértice é denominado conjunto de ancestrais próprios.
        
        Se (u, v) é a última aresta do caminho simples da raiz ao vértice v (e u = v), u é considerado o pai de v e v é chamado de filho de u;
        
        vértices que têm o mesmo pai são chamados irmãos.
        
        Um vértice sem filhos é chamado de folha;
        
        um vértice com pelo menos um filho é denominado parental.
        
        A profundidade de um vértice v é o comprimento do caminho simples da raiz até v.
      - A altura de uma árvore é o comprimento do caminho simples mais longo da raiz até a folha.