[C] Domanda sugli alberi

[Atem1]

Salve ragazzi, avrei una domanda sulla definizione di successore.

Il successore di un nodo con chiave key è il nodo con la più piccola chiave più grande di key.
Dato il nodo x di un BST:
– se il sottoalbero destro di x non è vuoto allora il successore di x è proprio il nodo più a sinistra del suo sottoalbero destro.
–Altrimenti se il sottoalbero destro di x è vuoto e x ha un successore y, allora y deve essere l’antenato più prossimo di x il cui figlio sinistro è anche antenato di x.

Prendiamo il seguente albero

La mia domanda è:
"Chi è il successore di 38?"
Stando alla prima definizione (quella colorata in blu) è 44.
Invece stando a quello che ho evidenziato in grassetto cos'è?
Il sottoalbero destro di 38 è vuoto quindi il suo successore "deve essere l’antenato più prossimo di x il cui figlio sinistro è anche antenato di x".
Il primo antenato di x è 44 ma deve essere un figlio sinistro del successore di x, e dato che 44 è il figlio sinistro di 104 allora secondo questa definizione è 104 il successore di x, quindi dov'è che sbaglio?
Insomma se "il figlio sinistro [del successore] è antenato di x" vuol dire che il successore deve essere *almeno* 2 livelli sopra X o no? Grazie mille per l'attenzione

[Atem1]

Io direi:
Il successore di un nodo con chiave key è il nodo con la più piccola chiave più grande di key.
Dato il nodo x di un BST:
– se il sottoalbero destro di x non è vuoto allora il successore di x è proprio il nodo più a sinistra del suo sottoalbero destro.
–Altrimenti se il sottoalbero destro di x è vuoto e x ha un successore y, allora y è l'antenato più prossimo se esso è maggiore di x altrimenti y deve essere l’antenato più prossimo di x il cui figlio sinistro è anche antenato di x.


Che ne pensate? L'aggiunta in blu che ho fatto è necessaria oppure no? Era giusta anche senza questa frase in blu?

[onlyReferee]

Secondo me è molto semplice: in base alla definizione "deve essere l’antenato più prossimo di x il cui figlio sinistro è anche antenato di x" possiamo avere anche il caso (come nell'esempio da te proposto) che il successore di x sia il suo nodo padre. In tal caso bisognerebbe specificare che il successore di x è "l’antenato più prossimo di x il cui figlio sinistro è anche antenato di x oppure il figlio è x stesso". Tale estensione è necessaria solo per far fronte al caso da te considerato. Se invece avessimo il nodo con chiave 44 con un solo figlio destro avente chiave pari a 48 invece il problema non si pone perché, in base sia alla definizione originale che a quella estesa appena descritta, il successore di 48 è il nodo con chiave 104.