Please enable JavaScript.
Coggle requires JavaScript to display documents.
Rooted trees - Coggle Diagram
Rooted trees
Árvore ordenada: todos os filhos estão ordenados (esquerda pra direita)
Árvore binária: cada vértice tem no máximo dois filhos (pode ser vazia)
Pode ser definida recursivamente
Números das subárvore direita sempre são maiores que os das subárvores esquerdas
Eficiência depende do número de vértices
Busca: checa se árvore é vazia, checa se número é igual a raiz, checa se é maior (vai pra lado direito da raiz) ou menor (lado esquerdo)
Eficiência:
Worst case: big theta(n)
Average case: big theta (log n)
Inserção é igual
Medir posto: A(n(T )) = A(n(Tleft)) + A(n(Tright)) + 1
A(0) = 0
Vértices externos (vazios) e internos (ocupados)
Preorder traversal: raiz/lado esquerdo/lado direito
Inorder traversal: lado esquerdo/raiz/lado direito
Postorder traversal: lado esquerdo/lado direito/raiz
Ordem de acesso à raiz
Grafo acíclico conexo
Floresta: grafo acíclico desconexo
Só existe um caminho entre dois vértices
Raiz da árvore é o topo (nível 0)
Backtracking
Branch-and-bound
Vértice num nível menor é o ancestral
Vértice pai/filho/irmãos
Folha: vértice sem filhos
Profundidade: da raiz até vértice qualquer
Posto: maior caminho da raiz até a folha mais longe