3.2.3 Binärer Baum

Der vollständige binäre Baum B(k) der Höhe k hat 2^{k + 1} - 1 Knoten und besteht aus k + 1 Ebenen. Jeder Knoten (bis auf die Wurzel) hat einen Vater, jeder Knoten (bis auf die Blätter) hat zwei Söhne.

K₁ : ja

K₂ : 3

K₃ : laufe vom Start aufwärts zum gemeinsamen Vorfahren, dann abwärts zum Ziel

K₄ : 2 · k

K₅ : nein

Zur Vermeidung eines Kommunikationsflaschenhalses werden in einem Fat Tree die Links nahe der Wurzel mehrfach ausgelegt. Außerdem repräsentieren nur die Blätter Prozessoren: innere Knoten sind Schaltelemente.