Witam.
Mam za zadanie napisać funkcję 'Delete' która usunie następnik węzła x jeżeli spełniony jest warunek 'war', w przeciwnym wypadku usuwa poprzednik węzła x. Z pomocą napisałem funkcję wyszukującą następnik i poprzednik, mam też funkcję usuwającą poprzednik ale nie wiem dalej jak to zaimplementwać z tym warunkiem 'war'.
struct node
{
node *left, *right, *up;
int val;
}*root = NULL;
node *poprzednik(node *T)
{
if (!T)
cout << "BRAK ELEMENTU"<<endl;
if (T->left)
return max(T->left);
node *p = T->parent;
while ((p) && (T == p->left))
{
T = p;
p = p->parent;
}
return p;
}
node *nastepnik(node *T)
{
if (!T)
cout << "BRAK ELEMENTU"<<endl;
if (T->right)
return min(T->right);
node* p = T->parent;
while ((p) && (T = p->right))
{
T = p;
p = p->parent;
}
return p;
}
void delete(node*&root, int k) {
node*usuwacz = nastepnik(w);
if (usuwacz)
{
if ((usuwacz->left) && (usuwacz->right))
{
node*pre = poprzednik(usuwacz);
usuwacz->val = pre->val;
if (pre->up->left == pre)
pre->up->left = pre->left;
else
pre->up->right = pre->left;
delete pre;
}
else
{
node* poddrzewo = usuwacz->left ? usuwacz->left : usuwacz->right;
if (usuwacz->up)
{
if (usuwacz->up->left == usuwacz)
usuwacz->up->left = poddrzewo;
else
usuwacz->up->right = poddrzewo;
if (poddrzewo)
poddrzewo->up = usuwacz->up;
}
else
{
poddrzewo->up = NULL;
root = poddrzewo;
}
delete usuwacz;
}
}
}