Please enable JavaScript.
Coggle requires JavaScript to display documents.
Cap. 1 Levitin / Cap. 5 Shaffer - Coggle Diagram
Cap. 1 Levitin / Cap. 5 Shaffer
Árvores
É um grafo acíclico conectado.
Um grafo que não tem ciclos, mas não está necessariamente conectado, é chamado de floresta: cada de seus componentes conectados é uma árvore.
O número de arestas em uma árvore é sempre um a menos que o número de seus vértices.
|E|=|V | − 1
Essa propriedade não é o suficiente para quem grafo seja uma árvore, mas para grafos conectados, é.
Árvores Enraizadas:
Para cada dois vértices em uma árvore, existe um caminho simples de um desses para o outro.
Geralmente, sua raiz é colocada no topo.
Uma aplicação é é para descrever hierarquias, de diretórios de arquivos a organogramas de empresas.
1 more item...
Pesquisa e inserção em uma árvore de pesquisa binária
Caso a árvore esteja vazia, a busca termina em fracasso.
Caso a árvore não seja vazia, comparamos V com a raiz da árvore K(r). Se eles corresponderem, o elemento é encontrado e a pesquisa é interrompida, caso não, a pesquisa continua.
O caso de eficiência médio é dado em log n.
Transversals de árvore binária e propriedades relacionadas
Nem todas as questões sobre árvores binárias
requerem travessias das subárvores esquerda e direita.
Cap. 5: Árvores Binárias
Cap. 5.1: Definições e propriedades
É composta por um conjunto finito de elementos chamados nós
A raiz é o ancestral de todos os nós.
A raiz é o único nó no nivel 0 e com profundidade 0.
Cap. 5.1.1: O teorema da Árvore Binária Completa
As implementações de árvore binária podem exigir alguma quantidade de espaço para nós internos e uma quantidade diferente para nós de folha.
Cap 5.2: Traversals de árvore binária
Qualquer processo para visitar todos os nós em alguma ordem é chamado de travessia.
Qualquer passagem que lista cada nó da árvore exatamente uma vez é chamado de
enumeração da árvore de nós
.
Travessia de pré-encomenda:
Quando desejamos acessar um nó específico antes de acessar seus filhos. Ele verifica antes se a árvore é vazia.