Please enable JavaScript.

Coggle requires JavaScript to display documents.

M7 (Levitin) - Coggle Diagram

- - - - Em árvores enraizadas, algumas nomenclaturas especiais são:
        
        "Ancestrais de um vértice v" que são os vértices presentes no caminho simples entre v e a raiz
        
        "Pai" de um vértice v" é o ancestral de v no nível imediatamente acima, ou seja, é o último vértice do caminho entre a raiz e v
        
        Nesse caso, v é "filho" desse vértice pai
        
        Um vértice sem filho é chamado de "folha"
        
        Um vértice com pelo menos um filho é chamado de "parental."
        
        Vértices com o mesmo pai são chamados de "irmãos"
        
        Todos os vértices que têm v como ancestral são "descendentes" de v
        
        "Profundidade" ou "Posto" é o tamanho do caminho simples da raiz até v.
        
        "Altura" é o tamanho do maior caminho único da raiz ao vértice folha
      - "Árvores Ordenadas" são árvores em que todos os vértices filhos estão ordenados
        
        "Árvore Binárias" são árvores ordenadas em que cada vértice tem no máximo 2 filhos, sendo cada um designado como o "filho à esquerda" ou o "filho à direita" em relação ao pai
        
        Uma "sub-árvore à esquerda (ou à direita)" é a sub-árvore enraizada no respectivo filho à esquerda ou à direita
        
        "Árvores de Busca Binária" são árvores binárias ordenadas de maneira que o filho à esquerda de um vértice possui sempre um valor menor que o de seu pai, enquanto o filho à direita possui sempre um valor maior.
        Como o nome indica, são úteis para a busca de elementos em uma dada sequência
        
        Para uma árvore binária de n vértices, a sua altura h respeita a desigualdade:
        ceil( log(n)_(2) ) <= h <= n-1
        
        Uma ADT para uma árvore ordenada qualquer pode ser esquematizada como um conjunto de vértices em que cada vértice é um nó possuindo ponteiros para seus filhos
        
        No entanto, esse método se torna inconveniente caso haja uma grande variedade de números de filhos que cada nó possa ter.
        Uma alternativa é a representação first child-next sibling em que cada vértice possui um ponteiro para seu "primeiro" filho (o primeiro na ordenação escolhida) e um ponteiro para seu próprio irmão "sucessor" (ordenado logo em seguida)
- - - - Ex.: A altura da árvore pode ser encontrada analisando recursivamente a altura de cada uma de suas sub-árvores à esquerda e à direita. Desse modo, sendo H(T) a altura de uma árvore T, a recursão será
        H(T) = max( H(T_esquerda),H(T_direita) ) + 1
        H(T) = -1 se T é uma árvore vazia
        
        Como H(T) executa sempre uma função de comparação e uma de soma, a recorrência para o número de comparações é semelhante à recorrência para o número de somas:
        A(n(T)) = A(n(T_esquerda)) + A(n(T_direita)) + 1
        A(0) = 0
        em que A é o número de somas ou comparações e n(T) é o número de nós em uma árvore T
        
        Uma vez que a verificação se T é uma árvore vazia sempre ocorre, então essa deve ser a operação básica do algoritmo
        
        Para encontrar o número de verificações, é útil representar as sub-árvores vazias como folhas especiais, chamadas "nós externos" em contraste com os nó "verdadeiros", os "nós internos"
        
        Se x o número de nós externos e n o de internos, então o total de nós é x+n.
        Ao mesmo tempo, sabe-se que cada nó interno tem sempre dois filhos. Dessa forma, qualquer nó, exceto a raiz, pode ser expresso como filho de um nó interno. Assim, o total de nós também é 2n+1 = x+n => x = n+1
      - Importantes algoritmos de Dividir e Conquistar para árvores binárias são os percursos clássicos:
        
        Preorder traversal, no qual é visitado, de maneira recursiva, primeiramente a raiz, depois a sub-árvore à esquerda e por último a sub-árvore à direita
        
        Inorder traversal, no qual é visitado, de maneira recursiva, primeiramente a árvore à esquerda, depois a raiz e por último a sub-árvore à direita
        
        Postorder traversal, no qual é visitado, de maneira recursiva, primeiramente a sub-árvore à esquerda, depois a sub-árvore à direita e por último a raiz
- - - - No pior caso, o número de buscas é θ(n), pois em uma árvore não ramificada para encontrar o elemento da folha é necessário percorrer todos n os vértices
      - No caso médio, o número de buscas é aproximadamente 2 ln(n) ~= 1,39 log(n)_(2), o que está em θ( log(n) )
      - Como para inserir é necessário identificar a sua posição adequada na árvore, é necessário fazer um procedimento de busca para em seguida adicionar diretamente o elemento. Dessa forma, a eficiência de inserção é praticamente idêntica aos casos de busca