H-Baum

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Die ersten zehn Stufen eines H-Baumes

Als H-Baum wird ein spezieller Baum in der Graphentheorie bezeichnet. Es handelt sich dabei um die Einbettung eines binären Baums in ein rechteckiges Gitter – Wurzel in der Mitte –, sodass Baum und Teilbäume die Form des Großbuchstabens H zeigen. Jeder Knoten kann wieder Mittelpunkt eines Hs sein.

Der H-Baum ist eine FASS-Kurve, d. h., er füllt die ganze Ebene aus. Seine fraktale Hausdorff-Dimension ist 2. Mit jeder neuen Iteration multipliziert sich die Gesamtlänge der Kurve um .

H-Bäume spielen beim Entwurf von synchronen digitalen Schaltungen zur Signalverteilung eine Rolle. So wird in jenen Schaltungen über H-Bäume die Übertragung der zentral eingespeisten Taktsignale zu allen Schaltungsteilen am Chip mit identischen Übertragungszeiten sichergestellt.

Ein anderes Beispiel für die Verwendung von H-Bäumen ist die Abbildung der Kommunikationsstruktur eines Programms auf die Prozessoren in einem Computercluster.