4.0.2 Path Halving

Dieses Verfahren ermöglicht es, beim Hinaufgehen in einem Baum die Weglänge zu halbieren, indem man jeden zweiten Knoten auf seinen Großvater zeigen läßt:

Dieses wird durch die folgende Prozedur realisiert:

          WHILE vater[x] $\neq$ x DO
               vater[x] := vater[vater[x]];
               x := vater[x];
          END;