Calculadora de nós da árvore de recursão
Conte os nós de uma árvore de recursão de dividir para conquistar: dois subproblemas com metade do tamanho a partir de 16 dão 5 níveis com 1, 2, 4, 8 e 16 nós, 31 no total e 16 folhas. Confira exercícios sem desenhar a árvore. Grátis no seu navegador.
- Grátis
- Funciona no seu navegador
- Sem cadastro
- Seus dados não saem do seu aparelho
Executar grátis
Exemplo resolvido
- Fator de ramificação
- 2
- Razão de redução
- 2
- Tamanho da entrada
- 16
- Quantidade de níveis
- 5
- Altura da árvore
- 4
- Total de nós
- 31
- Nós folha
- 16
Recorrências de dividir e conquistar da forma T de n igual a a vezes T de n sobre b mais o trabalho não recursivo aparecem em todo curso de algoritmos quando merge sort, partições espaciais binárias ou recursão multiway são desenhados como árvores. Os estudantes precisam de uma contagem confiável de quantos nós ficam em cada nível e quão profunda a árvore cresce antes que os subproblemas atinjam o caso base. Esta calculadora de nós da árvore de recursão aceita o fator de ramificação a, a razão de redução b e o tamanho de entrada da raiz n, percorre a árvore até o tamanho do subproblema ser no máximo um, e devolve a contagem de níveis, a altura, totais de nós e folhas, a sequência de nós por nível, os tamanhos de subproblema e duas distribuições fracionárias do trabalho. Uma assume custo unitário por nó; a outra assume trabalho proporcional ao tamanho do subproblema, no estilo clássico do merge sort em que cada nível completo ainda faz trabalho linear em n.
O que uma árvore de recursão conta e como os níveis são definidos
Uma árvore de recursão é a imagem de cada subproblema criado por um algoritmo de dividir e conquistar cujo tempo satisfaz T de n igual a a vezes T de n sobre b mais f de n. A raiz representa a instância original de tamanho n. Cada nó interno tem exatamente a filhos, cada um resolvendo um problema cujo tamanho é o tamanho do pai dividido por b.
Os níveis são numerados a partir de zero na raiz. No nível i há a elevado a i nós, e cada um desses nós tem tamanho de subproblema n dividido por b elevado a i, desde que os tamanhos permaneçam reais e positivos. A varredura continua enquanto o tamanho atual for estritamente maior que um; o primeiro nível cujo tamanho é menor ou igual a um é mantido como nível de folhas de casos base e então a varredura para.
Essa convenção coincide com a condição de parada dos livros ao resolver entradas de tamanho constante diretamente. A altura da árvore é a contagem de níveis menos um, o número de arestas em um caminho da raiz até uma folha. Nós folha equivalem a a elevado à altura quando os tamanhos chegam a um em uma potência exata e, de modo geral, à contagem de nós do último nível registrado.
Nós internos são o total menos as folhas. Com fator de ramificação um a árvore é uma única espinha de comprimento igual ao número de divisões sucessivas até o tamanho ser no máximo um.
Onde contar os nós da árvore ajuda
Cursos de algoritmos e plataformas de tutoria usam uma calculadora de nós da árvore de recursão para que os aprendizes verifiquem profundidade e largura para a, b e n arbitrários sem desenhar centenas de nós à mão. Geradores de prova precisam de um oráculo determinístico que marque como errada uma contagem de folhas ou de níveis alegada em vez de aceitar palpites assintóticos vagos.
Ferramentas de preparação para entrevistas e visualizadores de complexidade emparelham os arrays por nível com gráficos para que os candidatos vejam por que dividir e conquistar equilibrado costuma gastar o mesmo trabalho em cada nível quando a é igual a b. Cadernos de engenharia que prototipam divisores multiway ou grafos de tarefas paralelas podem validar o fan-out antes de escrever escalonadores de produção. Validação falha não consome saldo.
Casos de uso
Lição de casa e tutoria de algoritmos
Permita que os alunos enviem a, b e n para T(n)=a T(n/b)+f(n) e verifiquem contagem de níveis, folhas e a sequência geométrica de nós em relação aos desenhos do livro.
Correção automática de provas e LMS
Avalie itens de árvore de recursão com um oráculo determinístico de nós totais e altura em vez de aceitar palpites assintóticos como respostas exatas.
Perguntas frequentes
Quantos nós tem a árvore de recursão do merge sort?
Com uma entrada de 16 dividida em duas metades a cada chamada, há 5 níveis com 1, 2, 4, 8 e 16 nós. No total são 31 nós, sendo 16 folhas e 15 nós internos.
Quando a árvore para de crescer?
No primeiro nível em que o tamanho do subproblema cai para 1 ou menos. Esse nível reúne os casos base. A altura é o número de níveis menos um, então 5 níveis dão altura 4.
O que mostram as duas distribuições de trabalho?
Uma supõe que cada nó custa o mesmo, então a maior parte do trabalho fica nas folhas. A outra supõe trabalho proporcional ao tamanho, como no merge sort, em que cada um dos 5 níveis faz um quinto do trabalho.
E se cada chamada criar um único subproblema?
Aí a árvore vira uma única corrente, tão longa quanto o número de divisões necessárias para levar o tamanho a 1. A razão de redução precisa ser sempre maior que um; senão, os subproblemas nunca diminuiriam.
Ferramentas relacionadas
Para desenvolvedores — acesso via API
Tudo nesta página está disponível via API. Esta seção é para equipes que querem integrar a ferramenta aos próprios sistemas; quem não precisa disso pode simplesmente usar a ferramenta acima.
Endpoint
Autenticação por token Bearer. Um único POST coloca a tarefa na fila; o resultado chega por webhook ou link assinado.
Chame do seu código
curl -X POST https://api.kit.forhosting.com/dev/recursion-tree-nodes \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"branching_factor":2,"shrink_ratio":2,"input_size":16}'const res = await fetch("https://api.kit.forhosting.com/dev/recursion-tree-nodes", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"branching_factor": 2,
"shrink_ratio": 2,
"input_size": 16
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/dev/recursion-tree-nodes",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"branching_factor": 2,
"shrink_ratio": 2,
"input_size": 16
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/dev/recursion-tree-nodes", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"branching_factor":2,"shrink_ratio":2,"input_size":16}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"branching_factor":2,"shrink_ratio":2,"input_size":16}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/dev/recursion-tree-nodes", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Exemplo de requisição
{
"branching_factor": 2,
"shrink_ratio": 2,
"input_size": 16
}Exemplo de resposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "dev.recursion_tree_nodes",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}A API é assíncrona: cada chamada devolve um task_id na hora. Se preferir polling, consulte o status a até 1 requisição por segundo.
Preço
Preço publicado, sem tokens nem créditos escondidos. Tarefa que falha não é cobrada.
Erros
| HTTP | Código | O que significa |
|---|---|---|
401 | unauthorized | Token ausente ou inválido. Confira o header Authorization. |
402 | insufficient_balance | Saldo insuficiente para esta tarefa. Faça uma recarga e tente de novo. |
404 | unknown_type | Esse tipo de tarefa não existe. Confira o campo type no catálogo. |
429 | rate_limited | Muitas requisições em pouco tempo. Espere um instante e tente de novo. |
Notas técnicas
O que uma árvore de recursão conta e como os níveis são definidos
Com fator maior que um a forma fechada do total de nós em L níveis é a elevado a L menos um, tudo sobre a menos um; este endpoint recalcula isso somando a série geométrica para que tamanhos fracionários e casos base precoces fiquem consistentes com a varredura.
Contrato de entrada, campos de resposta e visões do repartimento do trabalho
A string recurrence reafirma T de n em termos de a e b, e o campo formula resume a regra de níveis e a forma fechada do total de nós. Combinações patológicas que excederiam um teto seguro de níveis ou nós são rejeitadas com mensagem clara para que os clientes nunca travem em uma árvore explosiva. Exemplo: fator de ramificação dois, razão de redução dois, tamanho de entrada dezesseis produz cinco níveis com contagens um, dois, quatro, oito, dezesseis, trinta e um nós no total e dezesseis folhas — a clássica árvore de recursão binária perfeita do merge sort em um array potência de dois. Envie um corpo JSON via POST com três números finitos obrigatórios: branching_factor, inteiro maior ou igual a um; shrink_ratio, número finito estritamente maior que um para que os subproblemas encolham; e input_size, número finito pelo menos um para a raiz. Cadeias numéricas são aceitas; campos ausentes, valores não finitos, fatores de ramificação não inteiros ou menores que um, razões de redução não maiores que um e tamanhos de raiz abaixo de um falham com invalid_input e não são cobrados. Em sucesso o corpo ecoa as três entradas e informa level_count, tree_height, total_nodes, leaf_nodes e internal_nodes. O array nodes_per_level lista quantos nós ficam em cada nível da raiz para baixo. O array subproblem_size_per_level lista o tamanho compartilhado por todos os nós daquele nível, arredondado a doze casas decimais para igualdade estável entre runtimes. Dois arrays de frações em paralelo somam um: node_fraction_per_level divide a contagem de nós de cada nível pelo total geral, modelando trabalho unitário por chamada recursiva; size_work_fraction_per_level pondera cada nível por nós vezes tamanho do subproblema, modelando trabalho não recursivo proporcional ao tamanho naquele nó.
Casos de integração
Visualizadores de complexidade e entrevistas
Alimente nodes_per_level e size_work_fraction_per_level em gráficos para que os candidatos vejam como o trabalho se espalha pelos níveis em árvores no estilo merge sort.
Perguntas técnicas
Como contar nós em uma árvore de recursão dividir e conquistar?
Envie branching_factor a inteiro ≥ 1, shrink_ratio b > 1 e input_size n ≥ 1. A API percorre níveis com a^i nós de tamanho n/b^i até size ≤ 1 e devolve totais mais arrays por nível.
Qual a diferença entre level_count e tree_height?
level_count é o número de níveis incluindo a raiz (pelo menos 1). tree_height é level_count menos 1, o número de arestas em um caminho da raiz até uma folha.
Como a distribuição do trabalho é calculada?
node_fraction_per_level é a contagem de nós de cada nível sobre total_nodes. size_work_fraction_per_level pondera cada nível por nós vezes tamanho do subproblema, alinhado ao trabalho não recursivo Θ(size) por chamada.
Quando a calculadora rejeita a entrada?
Campos ausentes ou não finitos, branching_factor não inteiro ou menor que um, shrink_ratio ≤ 1, input_size < 1, ou árvores que excedem o teto seguro de níveis ou nós falham com invalid_input e não são cobrados.
Quanto custa a calculadora de nós da árvore de recursão?
A ferramenta do navegador é gratuita. Pedidos API usam saldo pré-pago KIT a US$ 0,002 por chamada bem-sucedida; entrada inválida não é cobrada.