Árvores binárias são uma das estruturas de dados mais fundamentais, sendo usadas em diversas aplicações,
desde a implementação de expressões matemáticas até a construção de tabelas de símbolos. Além disso,
compreender a complexidade das operações nessas estruturas é essencial para escolher a melhor árvore para
um determinado problema. Considere as seguintes afirmações sobre árvores binárias, AVL, B, B+ e a
complexidade das operações associadas a essas estruturas:
I. A complexidade da busca, inserção e remoção em uma árvore binária de busca desbalanceada no pior caso
é O(n), mas, em uma árvore AVL, essas operações sempre têm complexidade O(log n) no pior caso;
II. Em uma árvore AVL, a rotação simples e a rotação dupla são operações fundamentais para manter a árvore
balanceada após inserções e remoções, mas essas rotações podem fazer com que o tempo de execução de
uma inserção ou remoção se degrade para O(n) em casos específicos;
III. Árvores B são ideais para sistemas de banco de dados porque permitem que várias operações de busca,
inserção e remoção sejam realizadas em tempo O(log n), com a vantagem adicional de minimizar o número
de acessos a disco devido à estrutura de nós de múltiplas chaves;
IV. Em uma árvore B+, ao contrário de uma árvore B, todas as chaves estão armazenadas apenas nos nós folha,
o que significa que as buscas por chaves sempre resultam em acessos aos nós folha. Embora isso possa
tornar a busca ligeiramente menos eficiente em comparação com uma árvore B, na qual a busca pode ser
resolvida em um nó interno, a árvore B+ oferece outras vantagens, como uma estrutura mais simples e
suporte eficiente para operações de intervalo e varreduras de dados;
V. Apesar de as árvores B e B+ serem amplamente usadas em bancos de dados, uma desvantagem das
árvores B+ em relação às árvores B é que a estrutura de encadeamento entre os nós folha pode aumentar
significativamente o tempo de execução das operações de inserção e remoção, devido à necessidade de
reorganização frequente dos nós folha.
Assinale a opção CORRETA: