Atree: implementação de árvore simples e eficiente sem ponteiros

• Apter Trees em C++
• Uma árvore representada de forma simples usando apenas dois vetores: [valor do nó, índice do pai)
• A maioria das árvores é implementada como árvores binárias, com cada nó contendo seu valor e ponteiros para os nós filho da esquerda/direita
• Esse tipo de estrutura de dados costuma exigir implementação recursiva e pode ficar lenta por causa do comportamento de cache e de chamadas frequentes a malloc()
• O conceito de quem “possui” um nó da árvore pode se tornar complexo em software com múltiplas camadas
• As Apter Trees são muito mais rápidas, mais fáceis de raciocinar e mais simples de implementar

Como funciona

• Implementada com dois arrays do mesmo tamanho
  • vetor (array) de dados d
  • vetor p de índices dos pais. O índice do vetor d é usado como chave (c)
  • com frequência, a chave/índice c é um inteiro
• Se Coco for mãe de Molly e Arca, e Arca tiver um filho chamado Cricket, a estrutura fica assim
  tree.d = ["Coco", "Molly", "Arca","Cricket"]
tree.p = [0,0,0,2]
• O nó cujo pai é 0 e cuja chave é 0 é o nó raiz (em Apter Trees, o nó raiz é obrigatório, ou então -1 significa “sem pai”, mas isso é ignorado aqui)
• O computador consegue manipular vetores muito rapidamente. Como isso é bem mais rápido do que operações com ponteiros, comparar a notação Big-O dos algoritmos na prática não faz muito sentido

Por que isso importa

• Esse método de implementação é a forma de representar árvores mais elegante que o autor já viu
• Com uma biblioteca adequada de operações sobre vetores, fica fácil de entender e de encontrar bugs
• Por ser simples, pode ser adaptado facilmente para outros cenários de uso
• É possível iterar rapidamente pelos valores ignorando o vetor de índices dos pais, o que equivale a um Deep Map disponível “de graça”
• É amigável para GPU e fácil de usar em ambientes embarcados
• Também é fácil manter a segurança impedindo que o tamanho dos vetores cresça além de um limite específico

Origem

• O autor está tentando descobrir quem inventou essa técnica e supõe que ela já tinha um nome no período orientado a vetores das décadas de 1960 e 1970
• A primeira descrição completa que viu foi a explicada por Apter, mas ela também está amplamente documentada em K3
• APL implementa árvores da forma tradicional, mas usa técnica semelhante para grafos vetoriais
• A técnica também é conhecida entre usuários de J, e há uma explicação sobre implementação de árvores em J no Rosetta Code
• John Earnest explica com mais detalhes a implementação de árvores vetoriais, incluindo a abordagem de “índice por deslocamento” para tratar exclusões
• Uma abordagem mais complexa é rastrear a profundidade de cada item

Outras implementações comuns de árvore

• Há implementações como a árvore do kernel do FreeBSD, as árvores do klib, a classe Tree do Ruby e classes de árvore declarativas em Python
• Elas não oferecem exatamente a mesma funcionalidade que Apter Trees, e algumas são muito maiores por causa da generalização

Estado atual deste código

• Foi uma tentativa de implementar isso enquanto aprendia C++17
• Ainda não está pronto para uso e o autor precisa aprender mais sobre C++

Opinião do GN⁺

• Apter Trees simplificam estruturas de árvore tradicionalmente complexas, permitindo um gerenciamento de dados rápido e eficiente
• Uma implementação de árvore baseada em vetores pode minimizar a sobrecarga de memória e melhorar o desempenho por meio de acesso linear
• Este artigo é interessante por explorar uma abordagem inovadora de estruturas de dados em engenharia de software

[GN⁺]

Comentários do Hacker News

• Um usuário comentou que ficou surpreso ao ver seu trabalho linkado no Hacker News. Ele disse ter grande interesse em estruturas de dados leves baseadas em arrays e mencionou uma implementação frequentemente usada em árvores de nós para skinning de modelos 3D. Explicou que, ao ordenar o array para que os nós pais venham antes dos filhos, é possível recalcular a transformação global de todos os nós com um simples loop.
• Outro usuário respondeu a um comentário dizendo que iterar sobre nós filhos nesse estilo de árvore é O(N), observando que é na verdade fácil generalizar o design do atree adicionando ponteiros para o “primeiro filho” e o “próximo irmão”. Também recomendou adaptar a estrutura de dados para dar suporte às operações necessárias.
• Um usuário argumentou que armazenar nós em um array e usar índices como ponteiros é essencial para implementar algoritmos de árvore. Em particular, aconselhou considerar estruturas separadas para nós internos e folhas, a fim de economizar memória quando for necessário acessar os filhos de um nó.
• Outro usuário comentou que é um pouco estranho ver a representação de árvores por array de pais recebendo tanta atenção no Hacker News. Na visão dele, isso mostra até onde uma boa apresentação pode levar uma ideia básica.
• Um usuário apontou que este projeto não passa de substituir ponteiros do sistema por ponteiros próprios.
• Outro usuário sugeriu que, se a intenção é reduzir mallocs e melhorar a localidade de dados, valeria a pena tentar uma implementação tradicional de árvore usando um pool de nós.
• Houve também um comentário recomendando consultar a explicação de Aaron Hsu usando APL.
• Um usuário propôs alterar a estrutura para empacotar todos os filhos de um nó juntos. Assim, seria possível encontrar a lista completa de filhos de um nó com busca binária e obter características mais amigáveis ao cache.
• Houve um comentário sobre chamar os índices no array de “handles” ou “index-handles”, mencionando que essa forma de representar árvores lembra estruturas de dados clássicas como heap e conjunto-disjunto.
• Por fim, um comentário explicou que índices de array também podem ser considerados um tipo de “ponteiro” e que implementações tradicionais de árvore exigem malloc por causa da necessidade de adicionar ou remover nós dinamicamente. Observou ainda que, se o tamanho da árvore for limitado e exclusões forem raras, uma implementação baseada em array pode ser adequada.