M7 (Levitin)
Cap.1
"Árvore" (ou mais precisamente "árvore livre") é um grafo conexo acíclico
Um conjunto desconexo de árvores é um grafo denominado "Floresta"
Uma de suas propriedade é que o número de arestas é igual ao número de vértices menos 1.
Árvores Enraizadas são árvores que possuem um vértice especial chamado "raíz, que define um nível inicial (topo, geralmente de valor 0) para o tamanho ou posto da árvore
Outra propriedade é que entre dois vértices quaisquer há sempre um único caminho simples
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
Vértices com o mesmo pai são chamados de "irmãos"
Um vértice sem filho é chamado de "folha"
Um vértice com pelo menos um filho é chamado de "parental."
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)
Cap.5
Cap.4
.5
Analisando as operações de busca e inserção em uma árvore de busca binária:
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
.3
Como as sub-árvores de uma árvore binária apresentam as mesmas características entre si, podem ser usados métodos de Dividir e Conquistar para resolver problemas envolvendo esse tipo de estrutura.
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