Suponha que temos uma árvore de pesquisa binária balanceadasegurando n números. Nós recebemos dois números L e H e deseja somar todos os números em T que se situam entre L e H. Suponha há m tais números em T.Can alguém explica como calcular o valor absoluto do tempo gasto para calcular a soma ..?
Respostas:
2 para resposta № 1Eu vou deixar você trabalhar os detalhes completos, mas aqui está um começo. O algoritmo irá:
- Encontre o menor número na árvore que é maior que
L. Você pode fazer isso no tempo do log. - Ande na árvore, cada vez movendo-se para a próxima maior, e adicionando-a a um total em execução.
- Pare quando você chegar a um número que seja pelo menos
H.
Eu assumi que "mentir entre" significa "estritamente entre", mas você pode querer desigualdades fracas nas etapas 1 e 3.