Einen Knoten aus einem Binärbaum löschen

Neues Klassendiagramm

Analog zum Einfügealgorithmus, ist natürlich auch unser Löschalgorithmus etwas, was unserem Binärbaum im Allgemeinen gut zu Gesicht steht:

Klassendiagramm des Binärbaums mit delete-Prozedur

Wie auch bei der Einfügeprozedur, kannst Du dir zunächst selbst versuchen, einen Algorithmus zu überlegen. Dieser ist zwar etwas komplizierter, als add, aber wenn Du zumindest siehst, wo das Problem liegt, verstehst Du den unten vorgestellten delete besser. Und vielleicht gelingt es dir ja trotzdem.

Suchen

Um Ein Element aus einem Binärbaum zu löschen, müssen wir es zunächst finden. Dafür kannst Du natürlich deinen in Aufgabe 11a) entwickelten Algorithmus nutzen. Zunächst wollen wir also diesen Algorithmus in unsere Klasse einbetten:

Klassendiagramm des Binärbaums mit search-Prozedur

Um konsistent zu bleiben, können wir den gleich folgenden Code benutzen, um search in unsere Klasse zu implementieren. Wenn dein search Algorithmus allerdings passt, kannst Du natürlich auch den einfach in die Klasse implementieren.

class Knoten(object):
	def __init__(self):
		self.wert=0
		self.linkesKind = None
		self.rechtesKind = None
	
	def add(self, neuerKnoten):
		if self.wert==neuerKnoten.wert and self.rechtesKind==None:
			self.rechtesKind=neuerKnoten
		elif self.wert==neuerKnoten.wert:
			self.rechtesKind.add(neuerKnoten)
		elif self.wert<neuerKnoten.wert and self.rechtesKind==None:
			self.rechtesKind=neuerKnoten
		elif self.wert<neuerKnoten:
			self.rechtesKind.add(neuerKnoten)
		elif self.wert>neuerKnoten.wert and self.linkesKind==None:
			self.linkesKind=neuerKnoten
		else: 
			self.linkesKind.add(neuerKnoten)
		
	def search(self, key):
		if self.wert==key:
			return self
		elif self.wert>key:
			return self.linkesKind.search(key)
		else:
			return self.rechtesKind.search(key)
	
class Baum(object):
	def __init__(self):
		self.wurzel=None
	def add(self, neuerKnoten):
		if self.wurzel==None:
			self.wurzel=neuerKnoten
		else: self.wurzel.add(neuerKnoten)
	def search(self, key):
		if self.wurzel.wert==key:
			return wurzel
		else:
			self.wurzel.search(key)

Problem

Wenn wir den Schlüssel nun gefunden haben, können wir ihn natürlich löschen, aber was passiert dann? Dann haben wir entweder die Wurzel gelöscht, und somit keinen Baum mehr:

Problem beim löschen der Wurzel

Löschen wir einen inneren Knoten, haben wir plötzlich Knoten, die keinen Vaterknoten mehr haben und somit praktisch nicht mehr Teil unseres Baums sind. Schließlich gibt es keine Möglichkeit, sie mithilfe der existierenden Zeiger von der Wurzel zu erreichen:

Problem beim löschen eines inneren Knotens

Löschen wir ein Blatt, haben wir kaum ein Problem. Das einzige, was hier stört ist, dass wir einen überflüssigen Zeiger rumfliegen haben:

Problem beim löschen eines Blattes

Idee der Lösung

Um unsere Löschung jetzt korrekt durchzuführen, müssen wir die Fälle einzeln abhandeln:

Bei der Löschung unseres Blatts, können wir natürlich einfach auch den Zeiger löschen:

Lösungsidee beim löschen eines Blattes

Wollen wir einen inneren Knoten löschen, können wir zwischen zwei Sonderfällen unterscheiden, nämlich einmal dem simplen, in dem unser Knoten nur ein Kind hat:

Knoten mit nur einem Kind

In dem Fall können wir einfach das eine Kind des zu löschenden Knoten an die Stelle des zu löschenden Knoten setzen. Die Position der Kinder und Kindeskinder des entsprechenden Knotens ist natürlich weiterhin korrekt und so wie wir unsere Binärbäume aufbauen passt auch die Position des verschobenen Knotens.

Lösungsidee beim Löschen eines inneren Knotens mit einem Kind

Das selbe funktioniert auch, wenn die Wurzel nur ein Kind hat:

Löschen der Wurzel mit nur einem Kind
Lösungsidee beim Löschen der Wurzel mit nur einem Kind

Hat ein Knoten zwei Kinder, können wir ihn am besten durch einen direkten Nachbarn innerhalb des Unterbaums des zu löschenden Knotens ersetzen. Mit direktem Nachbarn ist der Knoten innerhalb der genannten Knotengruppe gemeint, der entweder der nächstgrößte oder nächstkleinste (das ist egal) gemeint. Man nennt diesen Nachbarn in-order Nachbar.

Löschen eines Knoten mit zwei Kindern
In-order Nachbar
Lösungsidee beim Löschen eines Knoten mit zwei Kindern

Hat der in-order Nachbar unseres zu löschenden Knoten selbst Kinder, kann er höchstens ein Kind haben (sonst wäre eines der Kinder der in-order Nachbar).

Wenn wir diesen also verschieben, löschen wir unten im Prizip wieder entweder ein Blatt oder einen Knoten mit nur einem Kind und können uns auf unsere Ideen von zuvor zurückziehen.

Aufgabe 13

(a) Nutze die Idee des Algorithmus, um von Hand die Knoten 3, 7 und 35(in dieser Reihenfolge) zu löschen.

(b) Wie viele Vergleiche werden benötigt, um ein Blatt zu löschen? Wie viele andere Schritte?

(c) Wie viele Vergleiche werden benötigt, um einen inneren Knoten zu löschen? Wie viele andere Schritte?

Der Algorithmus

Wenn Du nicht bereits selbst einen Algorithmus entworfen und implementiert hast, solltest Du versuchen, den gerade vorgestellten Algorithmus selbst zu implementieren. Damit Du den Algorithmus aber auf jeden Fall einmal gesehen hast, siehst Du im folgenden eine mögliche Implementation:
class Knoten(object):
	def __init__(self):
		self.wert=0
		self.linkesKind = None
		self.rechtesKind = None
	
	def add(self, neuerKnoten):
		if self.wert==neuerKnoten.wert and self.rechtesKind==None:
			self.rechtesKind=neuerKnoten
		elif self.wert==neuerKnoten.wert:
			self.rechtesKind.add(neuerKnoten)
		elif self.wert<neuerKnoten.wert and self.rechtesKind==None:
			self.rechtesKind=neuerKnoten
		elif self.wert<neuerKnoten:
			self.rechtesKind.add(neuerKnoten)
		elif self.wert>neuerKnoten.wert and self.linkesKind==None:
			self.linkesKind=neuerKnoten
		else: 
			self.linkesKind.add(neuerKnoten)
		
	def search(self, key):
		if self.wert==key:
			return self
		elif self.wert>key:
			self.linkesKind.search(key)
		else:
			self.rechteswKind.search(key)
			
	def delete(self, tree, key):
		if self.rechtesKind==None and self.linkesKind==None:
			self=None
		elif self.rechtesKind==None:
			self=self.linkesKind
		elif self.linkesKind==None:
			self=self.rechtesKind
		else:
			tree.rightStore=self.rechtesKind
			tree.leftStore=self.linkesKind
			self=self.nachbar()
			self.linkesKind=tree.leftStore
			self.rechtesKind=tree.rightStore
			self.rechtesKind.delete(tree, key)
		
	def nachbar(self):
		if self.rechtesKind.linkesKind==None:
			return self.rechtesKind
		else:
			return self.rechtesKind.kleinstesKind()
	
	def kleinstesKind(self):
		if self.linkesKind.linkesKind==None:
			return self.linkesKind
		else:
			return self.linkesKind.kleinstesKind()
	
class Baum(object):
	def __init__(self):
		self.wurzel=None
		leftStore=None
		rightStore=None
	def add(self, neuerKnoten):
		if self.wurzel==None:
			self.wurzel=neuerKnoten
		else: self.wurzel.add(neuerKnoten)
	def search(self, key):
		if self.wurzel.wert==key:
			return wurzel
		else:
			self.wurzel.search(key)
	def delete(self, key):
		search(self, key).delete

Da wir zum implementieren der delete Prozedur einige Hilfsprozeduren einführen mussten, sollten wir diese nun auch in unser Klassendiagramm aufnehmen:

Klassendiagramm des Binärbaums mit Hilfsprozeduren
X

Fehler melden

X

Suche