Jeder Knoten im binären Suchbaum ist mit einer ganzen Zahl
gekennzeichnet, von der angenommen wird, dass sie der Häufigkeit des Zugriffs auf diesen Knoten entspricht.
Das besagt, dass zu erwarten ist, dass bei jeweils 18 Suchvorgängen (im Beispielbaum) in diesem Baum viermal nach A gesucht wird, zweimal nach B, einmal nach C usw.
Bei jedem der vier Suchvorgänge, die A betreffen, sind zwei Zugriffe auf Knoten erforderlich, bei jedem der zwei Suchvorgänge, die B betreffen, drei Zugriffe auf Knoten usw. Man kann ein Maß für die „Kosten“ des Baumes berechnen, indem man die jedem Knoten zugeordnete Häufigkeit mit seinem Abstand von der Wurzel multipliziert und dann die Summe dieser Produkte bildet. Dies ist die gewichtete innere Pfadlänge des Baumes.