C Warum wird nur die Wurzel eingefügt?

[InfDude]

Guten Tag, stehe vor dem Problem, dass mein Programm Werte nicht richtig in einen AVL Baum einfügt. Ich sitze bereits gefühlt eine Ewigkeit dran und bin langsam extrem am verzweifeln.. Alle anderen Funktionen - Rotate, Balance etc. - sind geschrieben und sollten funktionieren, kanns halt nur nicht testen.. Bis auf die simple Ausgabe InOrder, die zeigt er mir korrekt an. Folgender Code:

AVLNode* CreateNode(int value) {

AVLNode* newNode=malloc(sizeof(AVLNode));
newNode->left=newNode->right=NULL;
newNode->height=1;
newNode->value=value;
return newNode;
}

void AVL_insert_value(AVLTree* avlt, int value)
{
AVLNode* next=avlt->root;
AVLNode* current;

if (avlt->root==NULL){
        avlt->root=CreateNode(value);
        }
else {

        while(next!=NULL) {
                current=next;
                if(value < next->value) {
                        next=current->left;
                        }
                else if (value > next->value) {
                        next=current->right;
                        }
                else {  return;
                        }
                }
        if(value > current->value){ current->right=CreateNode(value); }
        if(value < current->value){ current->left=CreateNode(value); }
        }
}

Keine Compilermeldungen, Valgrind beschwert sich auch nicht (free Funktion ist vorhanden). Wo verliere ich den Knoten? Würde mich sehr freuen wenn mir jemand helfen könnte. Typedef ist übrigens auch mit drin, der Fehler muss also semantischer Natur sein..

EDIT: Hab was falsches reinkopiert, bin am ändern
EDIT: Jetzt stimmts. Mein Fehler
EDIT: Mit "Jetzt stimmts" mein ich den Code. Programm läuft immernoch nicht

 

[titanskin]

Bitte änder deine Variablen tmp, tmp2 in gescheite Namen um. Ich glaube tmp soll parent/current heißen. Überlege dir ob du tmp2 brauchst. Mach den Code simpler.

Node* current = root;
while ( ! current ) {

if (current->val < val)
current = current->left;
else if (current->val > val)
current = current->right;
else return;

}

// create node

 

[InfDude]

Ja, das wäre "current/parent", ohne tmp2 hätte ich folgendes:

else {

        while(current!=NULL) {

                if(value < current->value) {
                        current=current->left;
                        }
                else if (value > current->value) {
                        current=current->right;
                        }
                else {  return;
                        }
                }
        current=CreateNode(value);
        }
}

Aber das macht für mich keinen Sinn. Current wäre ja jetzt NULL, und selbst wenn ich anstelle von current meine neue Node einsetzen würde, wär die ja nicht im Baum, oder? Somit brauch ich noch ein "next", deswegen hatte ich tmp und tmp2. Ich nenn mal tmp und tmp2 eben um. Klappen tut es mit diesem Code übrigens auch nicht

 

[hgader]

Hallo,

du überschreibst dir bereits vorhandene Einträge.
Versuch mal

if( (value > current->value) && current->rigth == null){ current->right=CreateNode(value); }
if( (value < current->value) && current->left== null){ current->left=CreateNode(value); }

 

[titanskin]

ich glaube ich weiß warum.
die zweite variable ist für den parent da .

 

[InfDude]

@titanskin

Ja genau. Current wird dann sozusagen der parent von dem neuen Knoten. Dies beabsichtige ich ja mit meinen letzten Zeilen, in denen entweder current->right oder current->left der neue Knoten wird

@hgader

Wenn ich das schreibe, kriege ich "free() invalid next size (fast)". Gibt einige beiträge auf Stack overflow und co., aber ich versteh die nicht ganz. Anscheinend bedeutet dies, dass entweder etwas ungültiges "gefreed" wird, oder zu wenig Speicher gemalloc'd wurde. Aber egal wie ich mein malloc in "CreateNode" ändere, der Fehler bleibt..

EDIT: Wobei es ja Sinn machen würde, wenn die Insert Funktion nicht richtig einfügt und ich dann versuche was zu free'n. Vorher wurde ja die Wurzel eingefügt und die konnte er free'n. Jetzt fügt er anscheinend nichts mehr ein..

 

[hgader]

Sorry, hab mich mit den Klammerungen verhaut, die if Abfragen gehören in die while Schleife.
Aussserhalb ist current nicht mehr gültig.

        while(next!=NULL) 
	{
            current=next;
            if(value < next->value) {
                next=(AVLNode *)current->left;
            }
            else if (value > next->value) 
	    {
                 next=(AVLNode *)current->right;
            }
            else{
		return;
            }

	    if( (value > current->value) && current->right == NULL ) { current->right=CreateNode(value); }
	    if( (value < current->value) && current->left == NULL ) { current->left=CreateNode(value); }
	}

 

[InfDude]

Klappt leider noch immer nicht. Nur die Root wird eingefügt.. mit valgrind oder --leak-check=full finde ich 0 Fehler..

 

[hgader]

Kannst du mal deine Datentypen posten. Habs bei mir probiert funktioniert tadellos.