Knoten löschen

[vip*r]

Hi Leute!

Ich hab hier eine Aufgabe die mir gerade Kopf zerbrechen bereitet. Ich soll aus einem AVL-Baum Werte löschen. Ich hab dazu folgenden Code:

void avltree1::searchVal(avlelem1* &elem, object o)
{
	avlelem1* predElem = new avlelem1;

	if(o < elem->val)	//links weitergehen: kleinere Werte
	{
		predElem = elem;	//Vorgänger speichern

		elem = elem->left;
		searchVal(elem, o);
	}
	else if(o > elem->val)	//rechts weitergehen: größere Werte
	{
		predElem = elem;	//Vorgänger speichern

		elem = elem->right;
		searchVal(elem, o);
	}
	else if(elem->val == o)	//Wenn Wert gefunden...
	{
		//... Nachfolger prüfen und entsprechend Pointer umhängen
		if((elem->left == NULL) && (elem->right == NULL))	//Wenn zu löschender Knoten keine Nachfolger hat, ...
		{
			//... dann Knoten einfach aushängen
			elem = predElem;	//Knoten auf Vorgänger setzen???

			//Knoten aushängen
			elem->left = NULL;
			elem->right = NULL;
		}
		else if((elem->left != NULL) || (elem->right != NULL))	//Wenn zu löschender Knoten einen linken oder rechten Nachfolger hat, ...
		{
			//... dann linken/rechten Nachfolger des zu löschenden Knoten an den Vorgänger des zu löschenden Knoten anhängen
			if(elem->left != NULL)
			{

			}
			else
			{

			}
		}
		else if((elem->left != NULL) && (elem->right != NULL))	//Wenn zu löschender Knoten einen linken und rechten Nachfolger hat, ...
		{
			//... dann zu löschenden Knoten durch den linkesten Knoten in seinem rechten Teilbaum ersetzen
		}
	}
}

In Zeile 3 lege ich mir ein neues Element meiner Klasse avlelem1 an, dass später den Voränger beinhalten soll, aber genau das wird dann in Zeile 25 zum Problem: Es ist kein Vorgänger des zu löschenden Knotens gespeichert, den ich aber brauche um die Zeiger aushängen zu können

Wie muss ich dann an diese Aufgabe rangehen? Kann mir da jemand Tips geben? Braucht ihr noch mehr Code? Die Klasse avlelem1 sieht so aus:

class avlelem1
{
public:
	int height;
	avlelem1 *left;
	object val;
	avlelem1 *right;
};