Dlaczego należy przechowywać dane tylko w węzłach liści w zrównoważonym drzewie wyszukiwania binarnego?
Kupiłem ładną małą książkę o geometrii obliczeniowej. Czytając go tu i tam, często natknąłem się na użycie tego specjalnego rodzaju drzewa wyszukiwania binarnego. Drzewa te są zrównoważone i powinny przechowywać dane tylko w węzłach liści, podczas gdy węzły wewnętrzne powinny przechowywać tylko wartości, aby prowadzić wyszukiwanie do liści.
Poniższy obraz pokazuje przykład tych drzew (gdzie liście są prostokątami, a wewnętrzne węzły są okręgami).
Mam dwa pytania:
Jaka jest zaleta braku przechowywania danych w wewnętrznych węzłach?
W celu nauki chciałbym wdrożyć takie drzewo. Dlatego pomyślałem, że dobrym pomysłem byłoby użycie drzewa AVL jako podstawy, ale czy to dobry pomysł?
Jakikolwiek pomocny zasób jest bardzo mile widziany.