4.1 Binary Search Tree

Lithanel
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 21. Apr 2015 12:13

4.1 Binary Search Tree

Beitrag von Lithanel »

Darf man davon ausgehen, dass der zu löschende Knoten auch immer im Baum existiert? Ansonsten müsste man ja einen boolean-Wert am Ende übergeben.

Gumbario
Neuling
Neuling
Beiträge: 7
Registriert: 30. Apr 2015 01:36

Re: 4.1 Binary Search Tree

Beitrag von Gumbario »

http://wiki.algo.informatik.tu-darmstad ... ee:_remove

"Wichtig: Machen Sie sich fur die Bearbeitung der Ubungsaufgaben intensiv mit dem Wiki vertraut und
nutzen Sie bei Verstandnisproblemen die zusatzlichen Materialien aus dem Moodle!"

da auch im wiki davon ausgegangen wird ist es besser wenn du auch davon ausgehst ist meine meinung

Lithanel
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 21. Apr 2015 12:13

Re: 4.1 Binary Search Tree

Beitrag von Lithanel »

Ich meine es stand ja nirgends im Wiki explizit geschrieben, dass man davon ausgehen soll und da ich deswegen nicht das Testat verhauen will, dachte ich mir, dass ich besser mal nachfrage. ;) Also danke, dass du das nochmal klargestellt hast. :D

escape
Erstie
Erstie
Beiträge: 12
Registriert: 25. Apr 2015 20:47

Re: 4.1 Binary Search Tree

Beitrag von escape »

Sorgt nicht der folgende Codeteil (leicht abgewandelt; aus dem Wiki) dafür, dass der Algorithmus auch "funktioniert", wenn der zu entfernende Knoten nicht existiert?

Code: Alles auswählen

// Man müsste nach links absteigen
if(K < p.key) {
   // Es gibt keinen linken Kindknoten => Abbruch
   if(p.left == null) return false;
}
(Den Code für einen Abstieg nach rechts habe ich mir gespart...)

Insofern wäre es fatal davon auszugehen, dass der zu entfernende Knoten immer existiert. Oder denke ich falsch?

AlexIschuk
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 11. Apr 2015 10:22

Re: 4.1 Binary Search Tree

Beitrag von AlexIschuk »

Ich habe eine Frage zur Implementationsinvariante bezgl. des Keys. In wiki (http://wiki.algo.informatik.tu-darmstad ... earch_tree) steht das der Key generischen Typs ist. Wenn ich aber richtig verstehe dann haben right, left in einem BST ja den generischen Datentyp BinarySearchTreeNode<T> mit T als Typparameter. Ist ein über den Typparameter T deklarierter key (T key;) ebenfalls ein generischer Datentyp und nicht einfach ein Objekt vom Typ T?

Gruss
Alex

Antworten

Zurück zu „Archiv“