Pesquisa e Operações em Árvores - Estruturas de Dados e Algoritmos

Flashcards cobrindo conceitos de pesquisa sequencial, pesquisa binária, definição de BST e operações de inserção, pesquisa e remoção (fusão e cópia).

Qual é a eficiência do Pior Caso e do Caso Médio na pesquisa sequencial em vetores?

A eficiência é $O(n)$.

Qual é a condição necessária para que a pesquisa binária em um vetor seja realizada de forma eficiente?

O vetor deve estar ordenado.

Descreva o funcionamento básico da pesquisa binária.

Considera-se primeiro o elemento do meio do vetor; se a chave for menor que o pretendido, repete-se o processo no lado direito, caso contrário, repete-se no lado esquerdo, reduzindo os elementos para metade a cada passo.

Quais são as eficiências (Melhor, Pior e Caso Médio) da pesquisa binária?

Melhor Caso: $O(1)$; Pior Caso: $O(\text{log } n)$; Caso Médio: $O(\text{log } n)$.

Quais são os critérios que definem uma Árvore de Pesquisa Binária (BST)?

O valor de qualquer nó da subárvore esquerda é menor ou igual ao da raiz; o valor de qualquer nó da subárvore direita é maior que o da raiz; e as subárvores esquerda e direita também são árvores de pesquisa.

Como é definida a estrutura de um nó (struct nodo) para uma BST segundo o material?

Possui um campo 'item' (int), um apontador 'esquerda' para a subárvore esquerda e um apontador 'direita' para a subárvore direita.

Quais são os três cenários possíveis para a remoção de um nó em uma BST?

1. O nó não tem filhos (é uma folha); 2. O nó tem um único filho (subárvore); 3. O nó tem dois filhos (subárvores).

Quais são os dois métodos mencionados para realizar a remoção de um nó com dois filhos?

Remoção por fusão e Remoção por cópia.

Explique o processo de 'Remoção por Fusão'.

Navega-se para a subárvore esquerda e encontra-se o seu nó mais à direita. Atribui-se a subárvore direita do nó a remover ao lado direito desse nó mais à direita. O nó original é então substituído pela sua subárvore esquerda modificada.

Explique o processo de 'Remoção por Cópia'.

Navega-se para o nó mais à direita da subárvore esquerda, trocam-se os conteúdos desse nó com o nó a ser removido e, em seguida, remove-se o nó que agora contém o valor original (o antigo nó mais à direita da esquerda).

Na implementação da pesquisa recursiva em BST (PesquisaBST), o que acontece se o item for menor que o valor da raiz?

A função chama-se recursivamente passando a subárvore esquerda: $PesquisaBST(\text{raiz->esquerda, item})$.