Please enable JavaScript.
Coggle requires JavaScript to display documents.
Olavo Rangel da Conceição - Coggle Diagram
Olavo Rangel da Conceição
Trees
Grafo Acíclico Conectado
Floresta
Não necessariamente precisa estar conectado
Seus Componentes Conectados são chamados de Arvores
Propriedades
|E|=|V | − 1.
Entre dois Vertices sempre existe um caminho simples entre eles
Um Vertice Arbitrario Pode se Tornar a Raiz da Arvore
Rooted Tree
Propriedades
Implementação de Dicionarios
Acesso a Grande Conjunto de Dados
Analise Recursiva de Algoritmos
Alta Importância em Ciencias da Computação
Descrever Hierarquias
Codificação de Dados
State Space Tree
Design Techniques
Backtracking
Branch and Bound
O vértice antecessor é chamado de Ancestral
Excluir o Próprio Vértice dos Ancestrais
Conjunto dos Ancestrais Próprios
(u,v) Ultima Aresta Caminho Simples da Raiz
Ao Vertice V
U diferente de V
U pai de V
Vertices que tem o mesmo pai são chamados de irmãos
V filho de U
Vertices sem filhos são chamados de folhas
Descendentes
Se existe um grupo de vários vértices
E esses vértices tem em comum um Vértice qualquer como antepassado
Eles serão descendentes desse Vertice Qualquer
Todos os descendentes formam uma subarvore, como seu antepassado como raiz
Profundidade
Comprimento do Caminho Simples do Vertice até a raiz
Altura
Comprimento do Caminho Simples Mais Longo
Da Raiz até a Folha
Ordered Trees
Todas as Crianças de Cada Vertice São ordenadas
São ordenadas da esquerda para a direta
Binary tree
árvore ordenada na qual cada vértice não tem mais de duas crianças e cada criança é designada como uma criança esquerda ou uma criança direita de seus pais
Pode ser vázia
Binary Search Tree
multiway search trees
Acesso eficiente para conjuntos de dados grandes
Analise de algoritmo
piso(log2n) ≤ h ≤ n − 1.
first child–next
sibling representation
Searching and Insertion in a Binary Search Tree
Arvore Binaria
Nós
Elementos de Conjunto de Itens Ordenaveis
Sub-arvore esquerda < Sub-arvore direita
Procurar Elemento
Recursivamente
Arvore Vazia
Falha
Arvore Não Vazia
Comparar V com raiz K(r) da arvore
Igual
Busca Interrompida
Não Corresponder
Continua Busca
Sub-arvore esquerda se v < K(r)
Sub-arvore direita se v < K(r)
Tamanho de Uma Arvore de Busca
Altura
Pior Caso
Tree skewed
Contruída por insercções sucessivas
Sequencia Crescente
Sequencia Descrencente
Chave
Worst Case
Big Teta(n)
Average-Case
Big Teta(log n)
Binary Tree Traversals and Related Properties
Técnica Dividir Para Conquistar
Usada
Definição de Arvore Binaria
A divide em duas Sub-Arvores
Sub-Arvore Esquerda
Sub-Arvore Direita
Exemplo
Computar a Altura de uma Arvore Binaria
Máximo das altura das Sub-árvores
Substituir
Empty Subtrees
Special Nodes
External
Internal
Algoritmos Importantes
Traversal
Inorder
Postorder
Preorder