Please enable JavaScript.
Coggle requires JavaScript to display documents.
Trees, A profundidade / depth de um vértice c é o tamanho de um simples…
Trees
Trees tem propriedades importantes que outros grafos não apresentam.
O número de arestas é
SEMPRE
menor que o número de vertíces.
Em uma árvore enraizada /
rooted tree
, há uma propriedade importante, para todo dois vértices de uma tree, há sempre exatamente um caminho simples de um vértice para o outro.
O conceito de árvores enraizadas é mais importante do que o de árvores livres.
As aplicações mais obvias para o conceito de tree é a questão de hierarquias e organização
Aplicações men os óbvias é a implementação de Dictionary e codificação de dados.
Ordered Trees
É uma árvore enraizada no qual todos os filhos de um vértice v são ordenados
É conveniente considerar que todos os filhos são ordenados da esquerda para a direita.
Binary tree
É uma árvore no qual cada vértice têm no máximo 2 filhos, sendo eles chamados de filho esquerdo ou filho direitode seu pai.
Uma árvore binária também pode ser vazia.
Podemos implementar a binary search trees
A sua eficiência depende da altura da árvore.
A árvore binária geralmente é implementada na computação com o propósito pela coleção de nós correspondentes para os vértices da árvore. Cada nó contêm informação associada com os vértices e dois ponteiros dos nós que representam os filhos direito e esquerdo
É um grafo acíclico conectado.
Um grafo que não têm cíclo, mas não é necessariamente conectado é chamado de floresta
Cada componente dessa conexão é uma árvore(tree).
Tree é de grande ajuda na análise de algoritmos recursivos.
State-space trees
Contempla duas importantes tecnicas de design.
Backtracking
Brand-and-bound
A profundidade /
depth
de um vértice c é o tamanho de um simples cminho da raiz até v.
A
ALTURA
de uma árvore é o caminho mais longo da raiz até a folha.
Searching and Insertion in Binary Search Tree
Desde a inserção de uma nova chave em uma binary search tree é quase idêntica que uma busca.
Quando precisamos pesquisar um elemento de valor v em tal tree, fazemos de forma recusirva no seguinte modo
Nós comparamos o valor de v com a raiz da árvore
Caso encontramos o elemento desejado, paramos a busca.
Caso não, continuamos nossa busca na subtree esquerda da raiz se v for menor que o valor armazenado da raiz, ou buscamos na subarvore da direita caso o valor de v for maior do que o armazenado na raiz.
O que vai definir o grau de ef. é a altura da tree.
O pior caso é quando a árvore está severamente distorcida.
Isso acontece se a construção da tree foi feita por sucessicas inserções de incrementos e decrementos de sequências de keys.
O pior caso tem complexidade medido no parametro Big Theta(N)
Caso médio é de complexidade Big Theta(log N)
Caso a árvore esteja vazia, a busca não acontece
Binary Tree Traversals and Related Properties
Pensamos que a binary tree é um caso especial de uma árvore ordenada.
Podemos resolver problemas orientados a em algoritmos recursivos para a computação da altura de uma binary tree.
A altura de uma tree é o caminho mais longo de uma raiz até sua folha.
O algortimo para fazer essa conta é:
Height(T)
// Cumputes recursively the height of binary tree
// Input: A binary tree T
// Output: The height of T
if T ==
VAZIO
return -1
else return max{ Height ( T
left
),Height ( T
right
)} + 1;
Os algoritmos de dividir e conquistar mais importantes são as 3 travessias clássicas.
Preoder traversal
A raiz é visitada antes e após são as subtrees left e right ( nessa ordem )
Postorder traversal
A raiz é visitada depois da visita left e right subtree
Inoder traversal
A raiz é visitada depois da visita da subtree left mas antes visita right subtree
Nós mensuramos o tamanho do problema pelo núm. de nós dado pela binary tree.
Os nós extras são chamados de externos ( Os quadrados
Podermos perceber que o algoritmo faz a add de todos os nós internos de um árvore extendida, e faz comparações para checar se a árvore está vazia.
Portanto, para a eficiência do algoritmo nós precisamos saber quantos nós externos na árvore binary são extendidos com n nós internos.
O nós originários são chamados de internos(Os círculos)
É do tipo
Dividir para Conquistar
.
É um
