Please enable JavaScript.
Coggle requires JavaScript to display documents.
Mapa Mental 7 - Coggle Diagram
Mapa Mental 7
Capítulo 1: "
Introduction
".
Seção 1.4: "
Fundamental Data Structures
".
Tópico:
"Trees
".
Também chamado de árvore livre, é um grafo conectado e acíclico.
Um grafo acíclico mas não necessariamente conectado é chamado de
floresta
Cada um de seus componentes conectados são árvores.
O número de arestas de uma árvore é sempre 1 menor que o de vértices.
Para cada dois vértices de uma árvore, existe exatamente um caminho simples de um ao outro.
Esta propriedade torna possível escolher um vértice arbitrário em uma árvore livre e considerá-lo como a
raiz
da chamada
árvore enraizada
.
Tais árvores são retratadas geralmente colocando a raiz no topo e cada nível de novos nós abaixo
Elas também são comumente chamadas apenas de
árvores
, pois são muito mais importantes que as árvores livres para a ciência de computação.
1 more item...
Uma árvore enraizada na qual todos os filhos de cada vértice estão ordenados é chamada de
árvore ordenada
.
O conveniente é considerar que eles estão ordenados da esquerda para a direita.
1 more item...
Capítulo 5: "
Divide-and-Conquer
".
Seção 5.3: "
Binary Tree Traversals and Related Properties
".
Capítulo 4: "
Decrease-and-Conquer
".
Seção 4.5: "
Variable-Size-Decrease Algorithms
".
Tópico: "
Searching and Insertion in a Binary Search Tree
".
A busca por um elemento \(v\) em uma árvore de busca binária é feita recursivamente.
Se a árvore estiver vazia, a busca termina em fracasso.
Se a árvore não estiver vazia, comparamos \(v\) à raiz da árvore, se eles forem iguais, o elemento é encontrado e a busca encerra.
Se não forem iguais:
Se \(v\) for maior do que a raiz, então continuamos a busca na subárvore da direita da raiz.
Se \(v\) for menor do que a raiz, então continuamos a busca na subárvore da esquerda da raiz.
A medida mais significante do tamanho de uma árvore de busca é sua altura, e a diminuição na altura dela normalmente muda de uma iteração para outra, o que resulta em uma ótimo exemplo de um
algoritmo de diminuição de tamanho variável
.
O pior caso acontece se uma árvore é construída por sucessivas inserções de uma sequência crescente ou decrescente de chaves.
1 more item...
A eficiência do caso médio pertence a \(Θ(\log n)\).
A inserção de uma nova chave nesse tipo de árvore é quase idêntica à busca nela.
1 more item...