[DSAL] Splay-Baum Löschvorgang

[RN90]

Ich steh gerade etwas auf dem Schlauch:

Wie löscht man genau beim Splay, eine Möglichkeit? :

-das gewünschte Element, das gelöscht werden soll bis zur Wurzel rotieren, dann entfernen.
Als nächstes im linken Unterbaum das "rechteste" Element aussuchen und das zur Wurzel rotieren.

-Oder einfach nur den Elternknoten zur Wurzel

[Julius]

Ich hab das genauso verstanden wie du in deiner ersten Ausführung.

1.) Suche nach dem zu löschenden Knoten über den Schlüssel K im Baum (dadurch rotiert dieser, sofern er vorhanden ist, in die Wurzel)
2.) Splay-Operation auf den größten Knoten im linken Unter-/ Teilbaum (zur Wurzel rotieren)
3.) lösche K

Das steht auch ganz gut im Skkript (Folie 163, S.55 im Skript), man muss sich nur klar machen, dass nach dem ersten Suchen nach dem Schlüssel K schon eine Splay-Operation statt findet.


Hoffe das war hilfreich.

Lg

[rf91]

Sicher?

-Oder einfach nur den Elternknoten zur Wurzel

Das sagt nämlich auch Wiki: Erst löschen, dann splay(Elternknoten), also Elternknoten hoch zur Wurzel.

[AGo]

In Der Vorlesung wurde folgendes Verfahren vorgestellt (Folie 163)

Wenn du k löschen willst:
1. Suche k (das führt zum "hochsplayen" von k falls es gefunden wird)
2. wenn k nicht in der Wurzel liegt ist es nicht im Baum
3. suche das größte Element im (neuen) linken Teilbaum und splay es hoch
4. k ist jetzt das recht Kind und kann analog zum binären Suchbaum gelöscht werden

Ja das geht auch einfacher, aber dieses Vorgehen hilft bei der (amortisierten) Laufzeitanalyse

Tante Edith hat mich drauf hingewiesen, dass Julius
ja eigentlich schon alles wichtige geschrieben hat. Hatte ich übersehen, sorry