"gelöschter" Knoten nicht entfernt

User1291

Ich versuch, einen Binären Suchbaum zu implementieren.
Mit dem Löschen hab ich noch ein Problem, dessen Ursache sich mir entzieht:
Manchmal kommt es vor, dass ein "gelöschter" Knoten wieder angesteuert wird.
Nun hab ich aber nur vier Orte, an denen Pointer überhaupt auf einen Knoten n zeigen können:
1.) bst->root
2.) n->left->parent
3.) n->right->parent
3.) n->parent->right oder n->parent->left

Und ich dachte eigentlich, ich hätte alle vier abgedeckt.

Habe alle nicht-problemrelevante Funktionen weggelassen.
Ich schätze, der Fehler liegt im "deleteF".

bst.h

#ifndef BST_H
#define BST_H

typedef struct node Node;
typedef struct node{
	int value;
	Node *parent, *left, *right;
}Node;

typedef struct tree BSTree;
typedef struct tree{
	Node *root;
	int size;
	void (*add)(BSTree*,int);
	void (*delete)(BSTree*,int);
	Node*(*lookup)(BSTree*,int);
	void (*traverse)(Node*);
}BSTree;

BSTree *newBST(void);

#endif

bst.c

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>

#include "bst.h"

Node *replacement(Node *n){
	/*returns pointer to replacement candidate when deleting n, null if no replacement is necessary*/
	//note to self: never returns bst->root
	Node *rtn;
	if((n->parent) == NULL){ //in case we're deleting the root
		if(n->right != NULL)
			goto doRight;
		else if (n->left != NULL)
			goto doLeft;
		else 
			return NULL;
	}

	if((n->right != NULL) && ((n->value) > (n->parent->value))){
		//find symmetric successor
		doRight:
		rtn = n->right;
		while(rtn->left != NULL)
			rtn = rtn->left;
	}else{
		//find symmetric predecessor
		doLeft:
		rtn = n->left;
		if(rtn == NULL)
			return NULL;
		while(rtn->right != NULL)
			rtn = rtn->right;		
	}

	return rtn;
}

void deleteF(BSTree *bst, int k){
	/*deletes the node containing k from bst,
	 *does nothing if there is none
	 */
	Node *n = bst->lookup(bst, k);
	if(n == NULL)
		return;

	Node *r = replacement(n);
	if(r != NULL){
		//rid r of its child (at most one), reassign it to r's parent
		if((r->value) > (r->parent->value)){
			if(r->left != NULL)
				r->left->parent = r->parent;
			r->parent->right = r->left;
		}else{
			if(r->right != NULL)
				r->right->parent = r->parent;
            r->parent->left = r-> right;
		}

		//reassign n's children (at most two) to r
		r->right = n->right;
		if(n->right != NULL)
			r->right->parent = r;

		r->left = n->left;
		if(n->left != NULL)
			r->left->parent = r;

                r->parent = n->parent;
	}

	//now actually replace n
	if((n->parent) == NULL){
		bst->root = r;
	}else{
		if((n->value) < (n->parent->value)){
			n->parent->left = r;
		}else
			n->parent->right = r;
	}

	//and get rid of it
	free(n);
	n = NULL;

	return;
}

Node *lookupF(BSTree *bst, int k){
	/*returns pointer to node containing value k or NULL if no such node exists in bst*/
	Node *it;
	it = bst->root;

	while(it != NULL){
		if(k == (it->value))
			break;
		else if(k > (it->value)){
			it = it->right;
		}else
			it = it->left;
	}
	return it;
}

Testen tu ich das Ganze übrigens wie folgt:

void bstTest(void){
	printf("BINARY SEARCH TREE\n");
	BSTree *bst = newBST();

	int i;
	int arr[20];

	srand(time(NULL));

	for(i = 0; i < 20; i++){
		arr[i] = rand() % 100;
		bst->add(bst, arr[i]);
	}
	bst->traverse(bst->root);
	printf("\n");

	for(i=0; i < 3; i++){
		bst->delete(bst, arr[rand() % 20]);
	}

	bst->traverse(bst->root);
	printf("\n");

}

Wäre dankbar, wenn da jemand kurz einen Blick darauf werfen könnte.

EDIT
Linie bst.c 69 fehlte.

philipp2100

Du hast vergessen, newBST() zu posten. traverse() fehlt auch.
Und was meinst du mit "angesteuert"? Speicherzugriffsfehler oder was?

Übrigens ist das mit den gotos sehr schlechter Stil. Versuch mal, ohne gotos auszukommen und den Code allgemein lesbarer und symmetrischer zu machen, sonst wird das nichts mit dem "kurzen Blick". Auch für dich selbst, wenn du den in nem Jahr nochmal nachvollziehen willst.

User1291

philipp2100 schrieb:

Du hast vergessen, newBST() zu posten. traverse() fehlt auch.

Die hab ich wie gesagt, als nicht-problemrelevant weggelassen.
Und ich wusste, dass sie nicht problemrelevant sind, weil ohne Löschoperationen alles funktionierte.

Und was meinst du mit "angesteuert"? Speicherzugriffsfehler oder was?

Teils Segfault, teils wurden Garbage-values ausgegeben.

den Code allgemein lesbarer und symmetrischer zu machen

Was meinst du mit "symmetrisch"?
Wie würdest du dir "lesbarer" vorstellen?

Der Fehler ist übrigens gefunden, Linie 69 im bst.c fehlte.

SeppJ

User1291 schrieb:

philipp2100 schrieb:

Du hast vergessen, newBST() zu posten. traverse() fehlt auch.

Die hab ich wie gesagt, als nicht-problemrelevant weggelassen.

Das mag ja so richtig sein, aber optimal wäre es, wenn du compilierbare Minimalbeispiele geben würdest. So muss man sich als Leser keinen Code mit gotos antun, sondern kann das ganze Beispiel einfach durch den Debugger jagen, was die Fehlersuche sehr viel einfacher macht.

Und was meinst du mit "angesteuert"? Speicherzugriffsfehler oder was?

Teils Segfault, teils wurden Garbage-values ausgegeben.

Das wäre auch hilfreich im ersten Beitrag gewesen. Lies dir mal die Links in meiner Signatur durch und die als wichtig markierten Threads. Da erfährst du, wie du Fragen so stellen kannst, dass sie möglichst schnell eine möglichst gute Antwort erhalten, anstatt...

Der Fehler ist übrigens gefunden, Linie 69 im bst.c fehlte.

...dass der Thread tagelang ignoriert wird und du das Problem selber lösen musst.

philipp2100

User1291 schrieb:

philipp2100 schrieb:

Du hast vergessen, newBST() zu posten. traverse() fehlt auch.

Die hab ich wie gesagt, als nicht-problemrelevant weggelassen.
Und ich wusste, dass sie nicht problemrelevant sind, weil ohne Löschoperationen alles funktionierte.

Selbst wenn man drauf vertraut, dass das wirklich stimmt (deine Tests also ausgiebig genug waren), heißt es immer noch nicht, dass die nicht problemrelevant sind. In deinem Testcode, der ja ein wertvoller Anhaltspunkt ist, arbeitest du mit den Funktionen, um den nachzuvollziehen, muss man die also sehen. Wie soll ich sonst wissen, was in dem *bst genau gespeichert ist, z.B.?

User1291 schrieb:

den Code allgemein lesbarer und symmetrischer zu machen

Was meinst du mit "symmetrisch"?

Das die beiden Teile, die du mit "find symmetric ..." kommentiert hast, symmetrisch sind, also einmal der Fall mit < und einmal der Fall > abgedeckt wird mit dem gleichen Code (nur right und left, < und > usw. vertauscht), und weitere Fälle in extra Codeblöcken. Dann kannst du dir nämlich das goto sparen.

User1291 schrieb:

Wie würdest du dir "lesbarer" vorstellen?

Das oben gesagte, auch sonst gotos vermeiden und noch ein paar kleinere Sachen wie an manchen Stellen aussagekräftigere Variablennamen (node statt it), und überflüssige Klammern weglassen. Und immer schön geradlinig bleiben, nicht so um die Ecke denken wie bei deiner goto-Fummelei..

Ansonsten kann und muss ich SeppJ uneingeschränkt Recht geben.

User1291 schrieb:

Der Fehler ist übrigens gefunden, Linie 69 im bst.c fehlte.

Schön!

&quot;gelöschter&quot; Knoten nicht entfernt

"gelöschter" Knoten nicht entfernt