[ANSI C] - Albero binario di ricerca

[misterx]

Originariamente inviato da DanieleC88

Ma scanf() non ti restituisce l'ultimo carattere letto, ti restituisce il numero di elementi letti dall'input.

ciao,
quindi while((scanf("%d",&cifra)) != '\0')
è corretto giusto ?

[cionci]

Originariamente inviato da misterx

ciao,
quindi while((scanf("%d",&cifra)) != '\0')
è corretto giusto ?

Mi immagino che tu non sappia quanti valori hai nella riga...
In tal caso usa fgets per leggere una riga intera, poi usa sscanf per leggere i valori dalla riga fino a quando non ti torna 0.

[DanieleC88]

Dovrebbe funzionare, ma:

while((scanf("%d",&cifra)) != '\0')

dovrebbe diventare:

while((scanf("%d",&cifra)) != 0)

dal momento che ti restituisce un intero.

ciao

[misterx]

Originariamente inviato da cionci

Mi immagino che tu non sappia quanti valori hai nella riga...
In tal caso usa fgets per leggere una riga intera, poi usa sscanf per leggere i valori dalla riga fino a quando non ti torna 0.

ciao,
esatto. Per ora sto usando la scanf ed avendo provato con almeno 10000 valori in input credo che funzioni.

ciao e grazie

Originariamente inviato da DanieleC88

Dovrebbe funzionare, ma:

while((scanf("%d",&cifra)) != '\0')

dovrebbe diventare:

while((scanf("%d",&cifra)) != 0)

dal momento che ti restituisce un intero.

ciao

ciao,
direi che ci siamo.
Un'altra dritta: ho l'albero RB popolato ed uso la funzione inorder per visualizzare il suo contenuto ordinato per chiave. I campi riferiti ad ogni nodo sono:

A, B, C, D, E

quando uso la inorder mi viene mostrato quindi l'albero riordinato per A; se necessitassi di riordinare per C ad esempio vale la pena ricostruirsi un nuovo albero usando C come chiave e quindi usare inorder per visualizzare l'albero ordinato per C oppure ci sono metodi più ingegnosi ?

ciao

[DanieleC88]

A questo ti avevo già risposto in prima pagina:

Originariamente inviato da DanieleC88

Mi sembra troppo complicato da fare... Io terrei traccia del numero di nodi presente nell'albero, creerei un'array con un numero uguale di elementi, e lo riempirei con una visita in-order. Poi lo ordinerei in base a dato2.
Verrebbe un tempo O(n) per la creazione dell'array, più O(n·log(n)) per l'ordinamento dell'array (dove n è il numero di nodi dell'albero), quindi per un costo totale di O(n·log(n)).

[misterx]

Originariamente inviato da DanieleC88

A questo ti avevo già risposto in prima pagina:

ciao,
scusa ma sono proprio fuso, non ricordavo più di averlo già chiesto.

Volevo evitare di aggiungere ulteriore codice e magari sfruttare la inorder esistente.

E se creassi un albero temporaneo solo con la chiave che mi serve riordindare mettendo a zero gli altri campi e poi sfruttando la inorder, riodinerei l'output dell'albero temporaneo usandolo però come argomento di input per la RBsearch, così facendo verrebbe troppo costoso ?

ciao

[DanieleC88]

Dovrebbe venire ugualmente O(n·log(n)), se ho capito bene cosa intendi fare.

[misterx]

è un'idea per continuare a sfruttare sempre la stessa struttura

ciao

[misterx]

ciao,
l'idea l'ho implementata e funziona correttamente. Ho un dubbio quando si cancella un nodo sia esso nero oppure rosso che se non ricordo va rimesso tutto com'era

niente, sto ripassando un pò la teoria

[misterx]

ciao,
è possibile con una qualche tecnica dopo aver memorizzato area e posizione di rettangoli in un albero RB conoscere se tali aree si sovrappongono ?

grazie

[cionci]

Originariamente inviato da misterx

ciao,
è possibile con una qualche tecnica dopo aver memorizzato area e posizione di rettangoli in un albero RB conoscere se tali aree si sovrappongono ?

grazie

A che ti serve memorizzare area e posizione di un rettangolo in un albero RB ? Cioè...quale ordinamento attui ?

[misterx]

Originariamente inviato da cionci

A che ti serve memorizzare area e posizione di un rettangolo in un albero RB ? Cioè...quale ordinamento attui ?

ciao,
onestamente non lo so, è un'idea che mi è venuta osservando il mondo dei database dove fai unione o intersezione di dati.
Ho pensato che chi si occupa di grafica, magari ha escogitato un qualche modo per intersecare aree in un qualche modo che non conosco e magari attraverso gli RB che trovo molto prestanti.

Il link su wikipedia li presenta come strutture dati adatte per il real time.

ciao

[cionci]

La misura di questi rettangoli è in interi o float ? Di quanti rettangoli si parla ? Hanno dei limiti di coordinate ? Quando ti servono i risultati ? Ogni volta che aggiungi un rettangolo o solo alla fine dell'elaborazione ?

[misterx]

Originariamente inviato da cionci

La misura di questi rettangoli è in interi o float ? Di quanti rettangoli si parla ? Hanno dei limiti di coordinate ? Quando ti servono i risultati ? Ogni volta che aggiungi un rettangolo o solo alla fine dell'elaborazione ?

ciao,
dev'essere fatto in tempo reale

[cionci]

Originariamente inviato da misterx

ciao,
dev'essere fatto in tempo reale

Il fatto che debba essere fatto in tempo reale ancora non mi dice niente
Se deve essere fatto in tempo reale, quale dead line hai ? Quanti rettangoli possono essere aggiunti all'inizio di ogni periodo (uno, cento, mille, oppure vengono eliminati tutti e ricreati tutti).
All'inizio dell'elaborazione, quando ti si presentano i primi rettangoli hai un tempo di compensazione ?

[misterx]

Originariamente inviato da cionci

Il fatto che debba essere fatto in tempo reale ancora non mi dice niente
Se deve essere fatto in tempo reale, quale dead line hai ? Quanti rettangoli possono essere aggiunti all'inizio di ogni periodo (uno, cento, mille, oppure vengono eliminati tutti e ricreati tutti).
All'inizio dell'elaborazione, quando ti si presentano i primi rettangoli hai un tempo di compensazione ?

ciao,
forse sono andato un pò fuori strada, meglio se ci penso ancora un pochino.

Ho un'altra domanda: come duplico un albero RB ?

ciao

[DanieleC88]

Potresti fare una sorta di visita in cui replichi ogni informazione del nodo in questione in un nuovo nodo radice, associando poi al sottoalbero sinistro e destro la chiamata ricorsiva dell'algoritmo stesso. Al termine avresti un duplicato dell'albero su cui hai invocato la funzione, non dovrebbe essere difficile scriverla.

[misterx]

ciao e grazie

sto leggendo da stdin con

while((scanf("%d",&carattere)) != 0)

ma al termine vorrei rileggere una seconda volta la stringa passata come si riavvolge l'input ?

ciao

[cionci]

Non si riavvolge...

[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.