Usuwanie poprzednika z drzewa BST

Question

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;
}

 

Comments

Nie za bardzo rozumiem problem. Czym jest p? Z kodu wnioskuje, że rodzicem właśnie tego węzła node, tylko że komentarz wtedy bez sensu, bo przecież sprawdzasz czy lewy potomek rodzica jest węzłem, który planujemy usunąć i prawidłowo w ifie podmieniasz wskaźniki. 

 

---

To może spróbuje inaczej, treść brzmi tak:

Dane jest drzewo BST wskazywane przez Root (implementacja wskaźnikowa). Napisz funkcję Update, której argumentem jest wskaźnik do węzła p mającego przynajmniej lewe poddrzewo, i która zmodyfikuje wartość klucza poprzednika węzła p, dodając do przechowywanej wartości w poprzedniku wartość korzenia. Przywróć strukturze drzewa własność BST. Zdefiniuj wszystkie potrzebne struktury, zmienne i funkcje.

I już dochodząc do momentu usuwania nie umiem rozwiązać przypadku kiedy poprzednik ma lewe dziecko, (po prostu nie wiem jakie warunki tam dać, że to usuwać prawidłowo)