Please enable JavaScript.
Coggle requires JavaScript to display documents.
Árvores, Árvores Ordenadas - Coggle Diagram
Árvores
Uma árvore (mais precisamente, uma árvore livre) é um grafo acíclico conectado. Um grafo que não tem ciclos, mas não está necessariamente conectado, é chamado de floresta: cada um de seus componentes conectados é uma árvore.
As árvores têm várias propriedades importantes que outros grafos não têm. Em particular, o número de arestas em uma árvore é sempre um a menos que o número de seus
vértices.
Esta propriedade é necessária, mas não suficiente para que um grafo seja uma árvore. No entanto, para grafos conectados, é suficiente e, portanto, fornece uma maneira conveniente de verificar se um grafo conectado tem um ciclo.
Árvores Enraizadas
Para cada dois vértices em uma árvore, sempre existe exatamente um caminho simples de um desses vértices para o outro. Esta propriedade permite selecionar um vértice arbitrário em uma árvore livre e considerá-lo como a raiz da chamada árvore enraizada.
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 além da raiz nível 2.
Aplicações
Uma aplicação óbvia de árvores é para descrever hierarquias, de diretórios de arquivos a organogramas de empresas. Existem muitas aplicações menos óbvias, como a implementação de dicionários. As árvores também são úteis na análise de algoritmos recursivos.
Além disso, existem as chamadas árvores de espaço de estados que sublinham duas técnicas importantes de projeto de algoritmo: backtracking e branch-and-bound.
Para qualquer vértice v em uma árvore T, todos os vértices no caminho simples da raiz a esse vértice são chamados de ancestrais de v. O vértice em si é geralmente considerado seu próprio ancestral; o conjunto de ancestrais que exclui o próprio vértice é referido como o conjunto de ancestrais adequados.
Se (u, v) é a última aresta do caminho simples da raiz ao vértice v (e u = v), diz-se que u é o pai de ve v é chamado de filho de u; vértices que têm o mesmo pai são considerados irmãos.
-
Árvores Ordenadas
Árvores Binarias
Uma árvore binária pode ser definida como uma árvore ordenada em que cada vértice não tem mais do que dois filhos e cada filho é designado como filho esquerdo ou filho direito de seu pai; uma árvore binária também pode estar vazia.
Algumas árvores são chamadas de árvores binárias de pesquisa. Árvores binárias e árvores binárias de busca têm uma ampla variedade de aplicações em ciência da computação
Em particular, as árvores de pesquisa binárias podem ser generalizadas para tipos mais gerais de árvores de pesquisa, denominadas árvores de pesquisa multiway, que são indispensáveis para o acesso eficiente a conjuntos de dados muito grandes.
A técnica de dividir e conquistar pode ser aplicada a árvores binárias. muitos problemas sobre árvores binárias podem ser resolvidas aplicando a técnica de dividir e conquistar.
A eficiência dos algoritmos mais importantes para árvores binárias de busca e suas extensões depende da altura da árvore. Portanto, as seguintes desigualdades para a altura h de uma árvore binária com n nós são especialmente importantes para a análise de tais algoritmos:
[log2 n]//piso ≤ h ≤ n − 1
Uma árvore binária é geralmente implementada para fins de computação por uma coleção de nós correspondentes aos vértices da árvore. Cada nó contém algumas informações associadas ao vértice (seu nome ou algum valor atribuído a ele) e dois ponteiros para os nós que representam o filho esquerdo e o filho direito do vértice, respectivamente.
-
Uma árvore ordenada é uma árvore com raiz na qual todos os filhos de cada vértice são ordenados. É conveniente supor que no diagrama de uma árvore, todos os filhos são ordenados da esquerda para a direita.