Der HV Baum ist die monotone Zeichnung eines Binärbaums bei dem der Kindknoten des Baumes in der Zeichnung immer rechts oder unterhalb des Vaterknotens liegt und alle Kanten des Baumes in der Zeichnung rechtwinklich oder Paralel zueinander liegen.
HV-Baum
Die HV-Baum Zeichnung, Zeichnen eines Baumes mit rechtwinkligen Kanten.
Der HV Baum ist die monotone Zeichnung eines Binärbaums bei dem der Kindknoten des Baumes in der Zeichnung immer rechts oder unterhalb des Vaterknotens liegt und alle Kanten des Baumes in der Zeichnung rechtwinklich oder Paralel zueinander liegen. Ein n-ärer Baum kann nicht als HV-Baum dargestellt werden.
HV( = horizontal -vertikal)-Baum-Zeichnungen lassen sich leicht nach der Teile-und-Hersche (Divide & Conquer) Methode erstellen:
Divide: Rekursiv linken und rechten Teilbaum konstruieren
Conquer: horizontale (a) oder vertikale (b) Kombination:
rechtsschwere HV-Baum Zeichnung
Wenn beim Baumzeichnen eines Binärbaumes der Platz stark beschränkt ist und die Ordnung der Kinder des Baumes in der Zeichnung nicht erhalten bleiben muss ist die rechtsschwere HV-Baum Zeichnung mit einer maximalen Höhe von O(log(n)) geeignet.
Ein rechtsschwerer HV-baum lässt sich wie folgt Zeichnen:
Divide: Rekursiv Teilbäume konstruieren
Conquer: mit horizontaler Kombination größerer Teilbaum rechts von anderem
Die Höhe der Zeichnung des Baumes steigt mit jedem conquer Schritt, bei dem zwei Teilbäume vorhanden waren um maximal Höhe der Zeichnung des niedrigeren Teilbaumes +1. Wenn nur ein Teilbaum vorhanden war steigt die Höhe der Zeichnung des Baumes nicht. Da die maximale Anzahl von Knoten die zwei Kinder haben in einem Binärbaum log(n) ist, kann der Baum die Höhe von log(n) nicht überschreiten.