My Recursion Tree Visualizer project went viral on Linkedin

Bruno Papa — Sun, 04 Oct 2020 00:34:16 +0000

Recently I finished my favorite side project by now.

It is a Recursion Tree Visualizer that helps programmers understand recursion. You input any recursive function using javascript code and visualize your corresponding recursion tree.

I first published this in my Linkedin profile and I was surprised by the quick engagement that the post generated.

More than 15K views and more than 1K likes in just a few days 🤯.

If you want just to try it out, access https://recursion.now.sh.

Árvore de segmentos com RMQ

Bruno Papa — Sun, 26 Jan 2020 10:01:12 +0000

Uma árvore de segmentos é uma representação de segmentos de um vetor em uma árvore binária para que consultas em um dado segmento possam ser feitas de forma eficiente com complexidade de tempo O(log(N)), uma vantagem importante, visto que N pode ser excessivamente grande.

Mas é importante deixar claro que:

O custo de sua implementação só compensa os seus ganhos se o vetor for frequentemente atualizado e várias consultas sejam requeridas.

Para entender minha implementação, considere que:

Nos foi dado um vetor arr de tamanho N.
A árvore binária é armazenada como um vetor bt com tamanho de até 4*N, onde 0 é o índice da raiz, bt[v] o valor do vértice v, e bt[v*2+1] e bt[v*2+2] o valor de seus filhos à esquerda e à direita, respectivamente.

Está confuso? Calma! Abaixo vamos aplicá-la à uma RMQ para entender seu funcionamento de forma visual antes de ir para o código.

Range Minimum Query (RMQ)

Encontre o menor valor no sub-vetor {arr[i], …, arr[j]}, sendo 0 < i ≤ j< N.

build bt

A raiz, bt[0], representa o segmento [0 .. N-1] de arr. Para cada vértice representante de um segmento [l .. r], divide-o em dois segmentos menores: [l .. (l+r)/2] e [(l+r)/2+1 .. r].

Abaixo um exemplo da árvore de segmentos, após buildBT, com arr = {18, 17, 13, 19, 15, 11, 20} e N = 7.

Executamos bt.assign(4*N,0) e, em seguida, chamamos buildBT(0, 0, N-1) para construir os valores iniciais da nossa árvore de segmentos em O(N*log(N)).

range query

Como o algoritmo divide intervalos sucessivamente, conseguimos consultar um intervalo qualquer em complexidade de tempo O(log(N)).

Por exemplo, observe que rangeQuery(0, 0, N-1, 1, 3) nos retornará 13, como descrito no diagrama abaixo.

point update

Caso o vetor arr mude em alguma posição i, basta usar as mesmas ideias utilizadas acima para atualizar bt em O(log(N)).

Considerações finais

Por hoje é só. Vimos que uma árvore de segmentos nos permite fazer consultas eficientes, mas sua implementação é recursiva e, por isso, é preciso estar atento à muitos detalhes.

Agradeço a sua leitura, e espero que eu tenha contribuído em, pelo menos, colocar dúvidas na sua cabeça.

Referências bibliográficas:

HALIM, Steven. HALIM, Felix. Competitive Programming 3: "the new lower bound of programming contests". Chapter 2.4.3. 2013.