Árvores Balanceadas de Radix Relaxadas: Vetores Imutáveis Eficientes

Este artigo apresenta árvores balanceadas de radix relaxadas (RRB trees), uma estrutura de dados projetada para implementação eficiente de vetores imutáveis. Ao contrário dos vetores persistentes, as árvores RRB oferecem vantagens significativas de desempenho em operações de mesclagem. O artigo mergulha no funcionamento das árvores RRB, explicando o conceito central de relaxar a restrição de densidade esquerda e como uma tabela de tamanhos e a invariante M..M-1 garantem pesquisas e mesclagens eficientes. Uma implementação em TypeScript é fornecida, juntamente com uma explicação detalhada do algoritmo de mesclagem, mostrando a eficiência das árvores RRB na prática.