Cześć, czy mógłby ktoś stwierdzić, co jest źle w takiej funkcji usuwania węzła z BST ?
Przy usuwaniu np. 20 z 200 węzłów w 3/5 przypadków wyrzuca błąd.
void usun0(bst * & root, bst * wez) // dla 0 dzieci
{
if (wez->up->left==wez)
{
wez->up->left=0;
}
else
{
wez->up->right=0;
}
delete wez;
}
void usun1(bst * & root, bst * wez) // dla 1
{// sprawdz czy rodzic !=0
if (wez->up!=0) // 4 sytuacje
{
if (wez->left==0) //czyli prawy
{
if (wez->up->left==wez)
{
wez->up->left=wez->right;
}
else
{
wez->up->right=wez->right;
}
wez->right->up=wez->up;
}
else // lewy
{
if (wez->up->left==wez)
{
wez->up->left=wez->left;
}
else
{
wez->up->right=wez->left;
}
wez->left->up=wez->up;
}
}
else
{//dziecko na roota
if (root->right!=0)
{
root=root->right;
}
else
{
root=root->left;
}
root->up=0;
}
delete wez;
}
void usun2(bst * & root, bst * wez) // dla 2
{
int temp;
bst * minP; // najmniejszy z prawej
minP=wez->right;
while (minP->left!=0)
{
minP=minP->left;
}
temp=minP->key; //zamienia wartosc ostatniego z usuwanym
if (minP->right!=0) //jezeli z prawej cos jest
{
usun1(root,minP);
}
else
{
usun0(root,minP);
}
wez->key=temp;
}
void usun_wezel(bst * & root, bst * wez) // wywolywana funkcja szukaj dla 2 arg
{
if (wez->left!=0 && wez->right!=0) // 2 dzieci
{
usun2(root,wez);
}
else
{
if (wez->left==0 && wez->right==0) //usuwany element nie ma dzieci
{
usun0(root,wez);
}
else //jedno dziecko
{
usun1(root,wez);
}
}
}