Mam problem z zadaniem, mam napisać funkcje Update, którą podzieliłem sobie na mniejsze części, nie wnikając:
Znajduje poprzednik w drzewie BST (założenie, że zawsze ma przynajmniej lewe poddrzewo)
Zmieniam jego wartość dodając do niego wartość korzenia
Usuwam poprzednik z drzewa BST
Znajduje korzen
Dodaje na odpowiednie miejsce poprzednik.
Problem mam z usunięciem poprzednika, bo nie wiem jak zrobić warunek jeśli ma lewe dziecko, a potem poddrzewa itd. Tyle wykombinowałem, ktoś umie pomóc? Będę bardzo wdzięczny.
BSTdelete(BSTnode *node, BSTnode *&p) {
value = node->key;
if(p->left == node) { //if predecessor has no children
p->left = node->left;
node->left->parent =p;
else if (...) // i dont know how to do it when it has left child and then left child have children...
}
else {
node->parent->right = NULL;
}
delete node;
return value;
}