Questão FC373164
A estrutura de dados
Algoritmos e Lógica de Programação
FCC · 2023
A estrutura de dados
- pilha (ou queue) é do tipo FIFO (first-in, first-out), na qual o primeiro elemento a ser inserido será o primeiro a ser retirado.
- árvore binária tem como endereço o valor contido em sua folha principal. Dessa forma, para diferenciar duas árvores binárias é comum dizer, por exemplo: considere as árvores binárias cujas folhas são F1 e F2.
- fila (ou stack) é do tipo LIFO (last-in, first-out). Assim, uma fila permite acesso a apenas um item de dados: o último inserido. Para processar o penúltimo item inserido, deve-se remover o último.
- lista encadeada circular simples possui um único link que aponta para o próximo nó, permitindo que a mesma seja percorrida do primeiro para o último e do último para o primeiro nó, ou seja, em ambas as direções.
- árvore AVL é uma árvore binária na qual as alturas das subárvores esquerda e direita de cada nó diferem, no máximo, por uma unidade.
Mostrar resposta e comentário
Gabarito
Errado
Comentário do professor
A árvore AVL é uma árvore binária de busca em que, para todo nó, as alturas das subárvores esquerda e direita diferem no máximo por uma unidade. Formalmente, vale \( |h_{direita}(u) - h_{esquerda}(u)| \le 1 \) para cada nó \(u\).
Essa propriedade define o fator de balanço do nó, geralmente calculado como \(bf(u)=h_{direita}(u)-h_{esquerda}(u)\). Um nó está balanceado quando \(bf(u)\in\{-1,0,1\}\).
Ao garantir balanceamento local em todos os nós, a árvore mantém altura \(O(\log n)\), o que assegura operações de busca, inserção e remoção em tempo \(O(\log n)\) no pior caso.
Quando uma operação viola o balanço, aplicam-se rotações (simples ou duplas — direita/esquerda) para restaurar a propriedade AVL, atualizando alturas dos nós afetados.
Conteúdo do catálogo FC Concursos · Atualizado em