4.1 Binary Search Tree

infermaticker
Erstie
Erstie
Beiträge: 21
Registriert: 25. Apr 2015 00:21

4.1 Binary Search Tree

Beitrag von infermaticker »

Mir ist nicht ganz klar, wo beim Löschen gestartet wird. Startet man bei der Wurzel und traversiert den Baum bis man den zu löschenden Wert gefunden hat, oder wird direkt der zu löschende Knoten übergeben?
Im Wiki ist nämlich bei "Binary search tree: delete" bei "auxiliary data" von einem Pointer auf einen Knoten die Rede, nicht von einem Key.
Das würde dann allerdings die rekursive Implementation von delete hinfällig machen, die von deleteNode allerdings nicht.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: 4.1 Binary Search Tree

Beitrag von Prof. Karsten Weihe »

infermaticker hat geschrieben:Mir ist nicht ganz klar, wo beim Löschen gestartet wird. Startet man bei der Wurzel und traversiert den Baum bis man den zu löschenden Wert gefunden hat, oder wird direkt der zu löschende Knoten übergeben?
Der Key wird bei Methode remove übergeben.

infermaticker hat geschrieben: Im Wiki ist nämlich bei "Binary search tree: delete" bei "auxiliary data" von einem Pointer auf einen Knoten die Rede, nicht von einem Key.
Das würde dann allerdings die rekursive Implementation von delete hinfällig machen, die von deleteNode allerdings nicht.
Wovon reden Sie :?:

Die Methoden heißen bei uns remove bzw. remove node, nicht delete bzw. delete node. Und beide Methoden sind bei uns iterativ.

KW

infermaticker
Erstie
Erstie
Beiträge: 21
Registriert: 25. Apr 2015 00:21

Re: 4.1 Binary Search Tree

Beitrag von infermaticker »

Prof. Karsten Weihe hat geschrieben:
infermaticker hat geschrieben: Im Wiki ist nämlich bei "Binary search tree: delete" bei "auxiliary data" von einem Pointer auf einen Knoten die Rede, nicht von einem Key.
Das würde dann allerdings die rekursive Implementation von delete hinfällig machen, die von deleteNode allerdings nicht.
Wovon reden Sie :?:

Die Methoden heißen bei uns remove bzw. remove node, nicht delete bzw. delete node. Und beide Methoden sind bei uns iterativ.

KW
Ich meinte natürlich remove. Das rekursiv bezog sich auf die konkrete Theorieaufgabe.
Mir ist nun klar, dass der Key übergeben wird und der Baum erst traversiert werden muss, bis der Knoten der den Key enthält gefunden ist und gelöscht werden kann.

Allerdings:
Mit dem Pointer als "auxiliary data" bei "Binary search tree: remove" ist ja die Wurzel des Baums gemeint.
Aber mir ist nicht ganz klar, wieso hier nicht auch der zu suchende Key aufgelistet wird, oder wird dieser nicht als "auxiliary data" angesehen?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: 4.1 Binary Search Tree

Beitrag von Prof. Karsten Weihe »

infermaticker hat geschrieben: Mit dem Pointer als "auxiliary data" bei "Binary search tree: remove" ist ja die Wurzel des Baums gemeint.
Nein, der Pointer wird nur initial auf die Wurzel gesetzt und wandert dann abwärts.

infermaticker hat geschrieben: Aber mir ist nicht ganz klar, wieso hier nicht auch der zu suchende Key aufgelistet wird, oder wird dieser nicht als "auxiliary data" angesehen?
Nein, der Key ist ein Input und ist daher Teil der Problemstellung: http://wiki.algo.informatik.tu-darmstad ... nce#Remove.

"Auxiliary data" sind hingegen Teil der Lösung (=des Algorithmus) und sind daher auf der Wikiseite zum Algorithmus aufgeführt.

KW

Antworten

Zurück zu „Archiv“