Twitter und Facebook-Anbindung
X
Tweet Follow @twitterapi
!!! Anbindung an twitter und facebook öffnen !!!

Wenn Ihnen mein Online-Buch gefällt,
dann bedanken Sie sich doch mit einer kleinen Spende...

10.3.4 Löschen von Elementen

10.3.4 Löschen von Elementen

Das Erstellen von Bäumen kann man nicht verallgemeinern, da die Kriterien für die Ordnung im Baum je nach Aufgabenstellung unterschiedlich sein können. Oftmals ist der Baum auch nicht sortiert und oder ausgeglichen, also der linke Ast ist beispielsweise viel größer als der rechte.

Das Löschen eines kompletten Baumes ist jedoch einfach. Um alle Elemente zu löschen, muss man erst einmal alle finden. Wie dies funktioniert, habe ich eben beschrieben. Man nimmt hierfür immer die Postorder. Anstatt der Ausgabe steht nun ein "delete" (bzw. ein "free", wenn man mit "malloc" arbeitet).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
					
// ...

// Löscht ein Element/Ast aus dem Baum ////////////////////////////////////////
void DeleteTree(PIntegerTreeItem pHelpItem) {
	// Rekursionsbedingung
	if (pHelpItem != NULL) {
		DeleteTree(pHelpItem->pLeftItem);
		DeleteTree(pHelpItem->pRightItem);

		delete pHelpItem;
	} // end of if
} // DeleteTree ///////////////////////////////////////////////////////////////

// ...

DeleteTree(pRootItem);

// ...
					

Andere Verfahren würden die Knotenpunkte frühzeitig löschen und man könnte alle Unterbäume an ihnen nicht mehr freigeben. Mit Preorder würde beispielsweise gleich das Wurzelelement gelöscht werden, jedoch nicht seine Äste. Was dies zur Folge hat, wurde von mir bereits erwähnt.

Wenn man ein einzelnes Element aus dem Baum löschen will, so bedarf es ein wenig Denkarbeit. Zunächst muss man das entsprechende Element suchen (wie, ist egal) und dann muss man prüfen, um was es sich für ein Element handelt. Hierbei können vier Fälle auftreten.

Abschließend möchte ich zu diesem Thema noch sagen, dass das Sortieren von Bäumen mindestens genauso spaßig ist, wie das Löschen. Im Endeffekt läuft es aber darauf hinaus, dass man so lange Element sucht, welche nicht an der richtigen Stelle stehen, bis alles ok ist. Die falsch positionierten Elemente löscht man aus dem Baum (also nur abhängen und nicht freigeben) und sortiert sie anschließend neu ein (man lässt sie durch rieseln). Alternativ kann man auch einen komplett neuen Baum aufbauen, was aber nicht unbedingt schneller sein muss (auch wenn man es im ersten Moment vermuten könnte). Allerdings sortiert man nicht im Nachhinein Bäume, sondern sorgt gleich beim aufbauen, dass eine Sortierung vorliegt. Dafür gibt es auch verschiedene Konzepte, wie z.B. s.g. AVL-Bäume, Rot-Schwarz-Bäume oder die s.g. B bzw. B* Bäume. Für die entsprechenden Konzepte gibt es dann auch spezielle Regeln, wie Elemente gelöscht werden. Da dies aber eher in die theoretische Informatik geht und ich mich mehr auf C bzw. C++ konzentrieren möchte, belasse ich es hiermit dabei. Notfalls wissen Sie jetzt aber, über welche Themen Sie sich noch informieren müssten.

Zum Seitenanfang
Zum Inhaltsverzeichnis

© Copyright by Thomas Weiß, 2009 - 2012