Please enable JavaScript.
Coggle requires JavaScript to display documents.
Binary tree - Coggle Diagram
Binary tree
Binary tree search
Os valores dos ramos da esq. são menores que o do node
Os valores dos ramos da direita são maiores que o do node
Inorder traversal: Ordenar do menor para o maior
Acesso e atualização eficiente
Pointer-Based
Valor e dois ponteiros para cada ramo
As veze ponteiro para o parent
Muito overhead
As vezes o valor é um ponteiro para um dado
Mesma classe para folhas e nodes internos?
Simplifica implementação
Ineficiência de memória
Herança de classe
Array
Índice representa um node
Fórmulas para determinar essa relação
Sem overhead
Nodes
Vazio ou raiz (e ramos da esq. e direita)
Children: Novos ramos
Parent: Node que gerou o novo ramo
Edge: A ligação entre a Node e children
Depth: Tamanho do caminho da raiz até o node
Height: Tamanho da raiz ate o último node mais um
Internal Node: Pelo menos uma ramificação
Teorema da árvore binária cheia
Espaço para os nodes internos e para as folhas
O número de folhas é um a mais que o de nodes internos
O número de subárvores vazias é uma a mais que o número de nodes
Traversals
Ver todos os nodes em alguma ordem
Enumeração: Se passar por cada node apenas uma vez
Pré-ordenação: Assegurar que viu um node antes de ver os ramos
Pós-ordenação: Assegurar que viu um node só depois de ver os ramos
Inorder: Visita o ramo esq. (e suas ramificações), o node e depois o direito (e suas ramificações)