Flashcard FC268567
Qual a regra para calcular o menor número de níveis h necessários para armazenar N elementos em uma árvore binária balanceada completamente preenchida?
Algoritmos e Lógica de Programação
IDECAN · 2024
Qual a regra para calcular o menor número de níveis h necessários para armazenar N elementos em uma árvore binária balanceada completamente preenchida?
Mostrar resposta e comentário
Resposta
h = \( \lceil \log_2(N+1) \rceil \)Fórmula: máximo de nós em h níveis = \(2^h - 1\).
Como \(2^h - 1 \ge N \Rightarrow 2^h \ge N+1 \Rightarrow h \ge \log_2(N+1)\).
Portanto, o menor h é \(h = \lceil \log_2(N+1)\rceil\).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/266056
Conteúdo do catálogo FC Concursos · Atualizado em