He comprado un buen libro sobre geometría computacional. Mientras lo leía aquí y allá, a menudo me tropecé con el uso de este tipo especial de árbol binario de búsqueda. Estos árboles están equilibrados y deben almacenar los datos solo en los nodos de hoja, mientras que los nodos internos solo deben almacenar valores para guiar la búsqueda hacia las hojas.

La siguiente imagen muestra un ejemplo de estos árboles (donde las hojas son rectángulos y los nodos internos son círculos).

Tengo dos preguntas:

¿Cuál es la ventaja de no almacenar datos en los nodos internos?

Con el propósito de aprender, me gustaría implementar tal árbol. Por lo tanto, pensé que podría ser una buena idea usar un árbol AVL como base, pero ¿es una buena idea?

Cualquier tipo de recurso útil es muy bienvenido.