Eu comprei um pequeno livro sobre geometria computacional. Enquanto lia aqui e ali, eu frequentemente tropeçava no uso desse tipo especial de árvore de busca binária. Essas árvores são balanceadas e devem armazenar os dados apenas nos nós folha, enquanto os nós internos devem armazenar apenas valores para guiar a busca até as folhas.

A imagem a seguir mostra um exemplo dessas árvores (onde as folhas são retângulos e os nós internos são círculos).

Eu tenho duas perguntas:

Qual é a vantagem de não armazenar dados nos nós internos?

Para o propósito de aprender, eu gostaria de implementar essa árvore. Portanto, achei que seria uma boa ideia usar uma árvore AVL como base, mas é uma boa ideia?

Qualquer tipo de recurso útil é muito bem-vindo.