Please enable JavaScript.
Coggle requires JavaScript to display documents.
Árvores - Coggle Diagram
Árvores
é um gráfico conectado cíclicamente
Um gráfico que não é ciclicamente conectado, é chamado de floresta. Cada componente é uma árvore.
Árvores possuem algumas propriedades importantes que outros grafos não têm
O números de arestas é sempre o nr de vertices menos um
Árvores possuem raiz e dois "caminhos", então existe somente um único caminho da raiz para um nó
Os vertices localizados no caminho "contrário" indo de um nó para a raiz, é chamado de ancestrais do nó
Os vertices localizados após um nó, é chamado de filho
Nós que possuem o mesmo pai são chamados de irmãos
O nó que não possui filho é chamado de folha
A profundidade de uma árvore até um nó, é o tamanho do caminho da raiz até o nó.
A altura de uma árvore é o maior caminho da raiz até uma folha
Árvore ordenada: considera um grafo ordenado (por default) da esquerda para a direita.
Árvore binária: cada nó só tem no maximo 2 filhos
Buscas binárias e inserção
Inserção pode ser feita de várias formas, durante a implementação já ir de forma ordenada, ou inserir e depois ordenar (mais custoso).
A busca binária é feita em árvores já ordenadas, em que somente é comparado os valores dos nós, se for menor vai para a esquerda e se for maior para a direita
Big Theta log n
A utilização do algoritmo de dividir e conquistar é eficiente no método de cálculo do tamanho da árvore, dividindo as subárvores em árvores e fazendo o cálculo recursivamente falando.
Preorder
raiz, filho + folha, filho do filho + folha...
Inorder
O último pai + a folha, depois o penúltimo pai + a folha, e assim recursivamente
Postorder
A folha + pai, a penultima folha + pai,...