Please enable JavaScript.
Coggle requires JavaScript to display documents.
Árvores, Searching e inserting em uma árvore de busca binária, travessias…
Árvores, Searching e inserting em uma árvore de busca binária, travessias de árvore binária e propriedades relacionadas
Árvores
Árvores enraizadas
Consiste em escolher um vértice arbitrário e considerá-lo como a raiz da rooted tree, assim todos o outros vértices viriam abaixo dele (a raiz(root) estaria no level 0, os vértices que estão ligados a esse vértice arbitrário estariam no level 1, e assim por diante)
Árvores enraizadas tem um papel fundamental na computação, é mais importante que as free trees
Servem para aplicar dicionários, representar hierarquia, acessar de uma forma eficiente grande quantidades de conjunto de dados, codificação de dados, análise de algoritmos recursivos, e state-space trees que permitem duas técnicas importantes de design de algoritmos: backtracking e branch-and-bound
Árvores ordenadas:
Uma árvore ordenada é uma árvore enraizada na qual todos os filhos de cada vértice estão ordenados (da esquerda para direita)
Uma implementação de uma árvore arbitrária ordenada pode ser feita simplesmente provendo para o pai a quantidade de ponteiros, que representa a quantidade de filhos (essa representação pode ser inconveniente se a quantidade de filhos mudar bastante entre os vértices). Outra possibilidade é fazer os filhos como uma linked list e ai o pai só teria 2 ponteiros, o da esquerda para o primeiro filho e o da direita para o próximo irmão (first child-next sibling representation) Uma imagem dessa representação tem no livro de Levitin na pg 35
Uma árvore binária pode ser definida como uma árvore ordenada em que todos os vértices não tem mais que 2 filhos, assim cada filho é designado ou como filho da esquerda ou filho da direita do seu pai, uma árvore binária pode estar vazia. Uma árvore binária pode ser definida recursivamente, já que as subárvores também são árvores binárias. Uma árvore de busca binária é quando todos os nós de uma subárvore da esquerda são menores e todos os nós da subárvore da direita são maiores que a raiz daquela subárvore
Uma árvore binária é normalmente implementada por uma coleção de nós que correspondem aos vértices da árvore, cada nó contem uma informação associada ao vértice (como o nome, ou valor) e 2 ponteiros para os nós que apontam para o filho da esquerda e o filho da direita, se não existir algum desses filhos ele aponta para NULL
Uma árvore é um grafo conexo acíclico. Um grafo que não tem ciclos mas não necessariamente conectado é chamado de floresta, onde cada componente conectado da floresta é uma árvore
-
O número de arestas em uma árvore é sempre igual a o número de vértices - 1: E = V - 1 (essa condição é necessária, mas não suficiente para um grafo ser uma árvore(para grafos conexos isso é suficiente e fornece uma forma conveniente de chegar quando um grafo conexo tem um ciclo))
Para qualquer vértice em uma árvore, todos os vértices que aparecem no caminho até a raiz são chamados de ancestrais do vértice. Geralmente considera-se o vértice v como ancestral dele mesmo, mas o conjunto de ancestrais que exclui o vértice em si é chamado de proper ancestors
O vértice U que vêm logo acima de V no caminho até a raiz é chamado de pai de V, e V é chamado de filho de U. Se o U tiver 2 filhos, eles são chamados de irmãos (entre si). Um vértice sem filho é chamado de folha. Todos os vértices que têm V como ancestral são chamados de descendentes de V, o proper descendants exlcui o V em si. Todos os descendentes de V com suas respectivas arestas formam uma subárvore sendo V como raiz. A altura da árvore é o tamanho do caminho simples mais longo entre a raiz para uma folha (ou seja o level mais alto da árvore), já a profundidade de uma árvore é o tamanho de um caminho simples entre a raiz e um vértice V (ou seja é o level de V)
-
-