Ich habe ein schönes kleines Buch über Computergeometrie gekauft. Während ich es hier und da las, stolperte ich oft über die Verwendung dieses speziellen binären Suchbaums. Diese Bäume sind ausgeglichen und sollten die Daten nur in den Blattknoten speichern, während die inneren Knoten nur Werte speichern sollten, um die Suche zu den Blättern hinunterzuleiten.

Das folgende Bild zeigt ein Beispiel für diese Bäume (wobei die Blätter Rechtecke und die inneren Knoten Kreise sind).

Ich habe zwei Fragen:

Was ist der Vorteil, wenn keine Daten in den inneren Knoten gespeichert werden?

Zum Zwecke des Lernens möchte ich einen solchen Baum implementieren. Daher hielt ich es für eine gute Idee, einen AVL-Baum als Basis zu verwenden, aber ist es eine gute Idee?

Jede Art von hilfreicher Ressource ist willkommen.