[ANSI C] - Albero binario di ricerca

[misterx]

ciao,
peccato, mi avrebbe forse semplificato un pò la vita.

grazie

[misterx]

Originariamente inviato da DanieleC88

È uno stream: le letture a buon fine lo svuotano di ciò che è stato letto, quindi non puoi fare ciò che vuoi. Leggi una riga per volta in un buffer dinamico e opera su quello.

e salvare lo stream in un buffer dinamico per poi farlo rileggere alla scanf a piacere ?

[DanieleC88]

Come ti ha detto cionci in precedenza: leggi riga per riga con fgets(), poi usi sscanf() per leggere i dati.

[misterx]

Originariamente inviato da DanieleC88

Come ti ha detto cionci in precedenza: leggi riga per riga con fgets(), poi usi sscanf() per leggere i dati.

ciao,
mi sa che non le ho mai usate a questo modo.

Io sto lavorando in "real time" se così si può dire e lo svantaggio è che l'output è incontrollabile a meno che prima di generarlo non si faccia per due volte la stessa cosa

[misterx]

while((scanf("%d",&cifra)) != 0)
tramite questa dallo standdard input:

- leggo una cifra e la successiva
- faccio la differenza
- uso la inorder per cercare nell'RB
- se il campo desiderato soddisfa i requisiti di cifra e dimensioni lo mando in display
- tutti gli altri dati dell'albero che soddisfano cifra ma presentano dimensioni minori vengono scartati

funziona bene tranne il caso in cui quando un solo dato soddisfa i requisiti di cifra ma di cifre ne ho testate n, allora dovrebbe visualizzare un messaggio ma, siccome sto mandando in dislpay il risultato in realtime tale output non è controllabile a meno che:

- faccio una inorder di test che mi verifica se il numero di dati contenuti nell'albero è pari al numero di cifre passate per il test
- se il test viene superato
- faccio la inorder come sopra


ciao

[Fibrizio]

Originariamente inviato da DanieleC88

La fai un po' troppo semplice, se ti avessi chiesto di cancellare la radice dell'albero nel mio esempio? (Che è uno particolarmente piccolo e ben ordinato, non è niente di complesso.)

Che differenza dovrebbe fare dall'eliminare un qualsiasi nodo?
Associ alla root i nodi successivi secondo la stessa logica del nodo intermedio. Inoltre se conoscessi il predecessore cosa ti cambierebbe mai nell'eliminazione della radice? Quel che è peggio dovresti cambiarla in tutti i nodi.

Originariamente inviato da DanieleC88

Comincio a pensare che non sai leggere. Dal momento il successore di un nodo lo puoi trovare o come il nodo di valore minimo nel sottoalbero destro oppure... come il primo nodo antenato nel quale sali "da sinistra"... risalendovi appunto attraverso dei puntatori ai genitori. Nel testo che mi hai citato non c'è assolutamente niente che sostenga la tua tesi, semmai il contrario.
Il testo ti sta appunto dicendo che nel caso peggiore possibile hai l'invocazione dell'algoritmo in un albero completo, sulla foglia che contiene il valore massimo nel sottoalbero sinistro della radice, e che dovrà quindi risalire lungo tutta l'altezza dell'albero fino a raggiungere la radice (che è il suo successore), è da lì che viene il tempo O(h) = O(log(n)) che mi hai addirittura citato (con h = altezza dell'albero, n = numero di nodi).

se tu avessi letto tutto il testo avresti capito e siccome hai il libro sottomano dubito avrai difficoltà a leggere l'ovvio.

Originariamente inviato da DanieleC88

Ricapitoliamo: ti ho chiesto da due pagine di trovare un algoritmo che mi restituisca il successore di un nodo in un albero binario di ricerca senza avere riferimenti ai nodi genitori

Per avere un successore ad un nodo a che ti servono mai i riferimenti genitori?

Originariamente inviato da DanieleC88

e tu mi stai semplicemente dicendo che è un'operazione senza senso.

Appunto.

Originariamente inviato da DanieleC88

Ti ho fatto l'esempio della cancellazione di un nodo in un albero binario di ricerca dove, guarda caso, un pezzo importante (e quindi sensato) è proprio la ricerca del nodo successore al nodo da cancellare, e continui a dirmi che non è così.

Ti ho detto che non è importante conoscere il nodo genitore, non il figlio. E l'ho detto anche alquanto chiaramente svariati post fa.

Temo che il C fai da te continui a fare di questi danni alla gente.

[DanieleC88]

Vabbe'. Visto e considerato che ho provato a spiegarti come si fanno le cose nella pratica e perché nella teoria, che le motivazioni te le ha provate a spiegare anche cionci, che riesci a contraddire anche ciò che leggi tu stesso sul Cormen senza nemmeno capire di cosa si sta parlando, visto che ti chiedo degli esempi pratici e te la svigni con un "non ha senso" o "non ha differenza" (quando non è così) e soprattutto visto che sei così aperto al dialogo, sai che ti dico?

Continua a sghignazzare, noi facciamo lo stesso di te e del tuo comportamento.
Dalle parti mie si dice saggiamente che "a lava' 'a capa 'u ciuccio se perde tempo, acqua e sapone", per cui non lo farò.
Continua così che sei sulla buona strada.

ciao