[ANSI C] - Albero binario di ricerca

[Fibrizio]

Originariamente inviato da DanieleC88

È talmente senza senso che ciò che ti ho chiesto lo puoi trovare ad esempio a p.259 di Introduction to Algorithms (seconda edizione), di Cormen, Leiserson, Rivest, Stein. (Il Rivest in questione è uno degli autori di RSA ed MD5, tanto per farti capire il calibro.)
Anzi, ti dirò di più, è una richiesta talmente senza senso che è un passo essenziale per la cancellazione di un nodo da un albero binario di ricerca. Ma magari non ti fidi, provaci anche tu.

ciao

non vedo niente di simile a pagina 259
inoltre il fatto che non abbia senso non impedisce che lo si faccia.

edit: inoltre non è per nulla essenziale. la cancellazione si fa arrivando al valore precedente e verificando che il valore figlio contenga i parametri del nodo ricercato, se sì si sostituisce il puntatore al figlio col figlio del figlio. dunque non è essenziale.

[DanieleC88]

Originariamente inviato da Fibrizio

non vedo niente di simile a pagina 259

Io ho l'edizione americana, tu quale hai? Magari è solo su un'altra pagina, è l'algoritmo "Tree-Successor", lo descrive nel capitolo riguardante gli alberi binari di ricerca.

Originariamente inviato da Fibrizio

inoltre il fatto che non abbia senso non impedisce che lo si faccia.

E non è ciò che ti ho chiesto. È una cosa sensata e ben motivata, volevo arrivare a rendere chiaro questo punto... Non è uno "spreco".

ciao

[DanieleC88]

Originariamente inviato da Fibrizio

edit: inoltre non è per nulla essenziale. la cancellazione si fa arrivando al valore precedente e verificando che il valore figlio contenga i parametri del nodo ricercato, se sì si sostituisce il puntatore al figlio col figlio del figlio. dunque non è essenziale.

Forse sono riuscito a decifrare questa frase.

Hmm. Come arrivi al "valore precedente"? Diciamo che ci arrivo: se è una foglia funziona. Se il nodo ha un solo figlio, funziona. Se il nodo ha due figli, quale dei due prenderebbe il suo posto secondo la tua tecnica?

ciao

[misterx]

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


Devi scrivere una funzione che stampi il valore del nodo e passarla come secondo argomento ad "inorder()".

P.S.: un consiglio, quando hai:

quel (*op)(p) è un appesantimento sintattico inutile, funzionerà anche senza l'asterisco:

void inord(rbnode *p, rbnode *nil, void (*op)(rbnode *))
{
	if(p != nil) {
        	inord(p->left,nil,op);
		op(p);
        	inord(p->right,nil,op);
	}
}

Mi sembra molto più leggibile.

ciao,
grazie come sempre. Quello che osservi è codice già pronto che sto utilizzando senza reinventare l'acqua calda, come dice il docente, ed in alcuni suoi punti lo trovo un C piuttosto complicato.

ciao

[Fibrizio]

Originariamente inviato da DanieleC88

Hmm. Come arrivi al "valore precedente"? Diciamo che ci arrivo: se è una foglia funziona. Se il nodo ha un solo figlio, funziona. Se il nodo ha due figli, quale dei due prenderebbe il suo posto secondo la tua tecnica?

E' irrilevante se ha uno o due figli, il problema si ripresenta anche se il nodo ha un riferimento al genitore e si risolve ordinando i due figli secondo il criterio di ordinamento dell'albero. Nel caso specifico del tuo esempio se togliamo il nodo con valore 2 possiamo tranquillamente reinserire sia l'1 che il 3, visto che l'ordinamento non dipende dall'ordine di inserimento.

[Fibrizio]

Originariamente inviato da DanieleC88

Io ho l'edizione americana, tu quale hai? Magari è solo su un'altra pagina, è l'algoritmo "Tree-Successor", lo descrive nel capitolo riguardante gli alberi binari di ricerca.

Ho giust'appunto l'edizione americana, dal momento che preferisco i libri di informatica in lingua originale. A pagina 259 non c'è niente di simile, ma un problema da risolvere. Il tema di successori e predecessori in un albero binario viene trattato nel capitolo 12.2 Querying a binary search tree (così non ci si sbaglia con le pagine), dove viene spiegato chiaramente che

The running time of TREE-SUCCESSOR on a tree of height h is O(h), since we either follow a path up the tree or follow a path down the tree. The procedure TREE-PREDECESSOR,which is symmetric to TREE-SUCCESSOR, also runs in time O(h).

Ossia il predecessore viene calcolato in maniera simmetrica al successore e non vi è necessità di un puntatore specifico, ma solo di destro e sinistro, e anzi impiegano perfino lo stesso tempo di calcolo!
Da cui deriva anche il teorema

The dynamic-set operations SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, and
PREDECESSOR can be made to run in O(h) time on a binary search tree of height h.

Insomma non mi è ben chiaro dove hai trovato l'illuminante capitolo sull'essenzialità (?) di un puntatore al predecessore o alla radice dell'albero.
Che seppure sia possibile fare è tutt'altro che essenziale.

[cionci]

Originariamente inviato da Fibrizio

non vedo niente di simile a pagina 259
inoltre il fatto che non abbia senso non impedisce che lo si faccia.

edit: inoltre non è per nulla essenziale. la cancellazione si fa arrivando al valore precedente e verificando che il valore figlio contenga i parametri del nodo ricercato, se sì si sostituisce il puntatore al figlio col figlio del figlio. dunque non è essenziale.

Dipende tutto da quello che si vuole fare...se si cercano le prestazioni è sicuramente meglio avere il puntatore al nodo che il valore, perché si arriva direttamente al nodo senza, nel worst case, attraversare tutta la profondità dell'albero.

[misterx]

ciao,
non ho ancora ben chiaro questo codice per la visita in-ordine di un albero RB.

void inord(rbnode *p, rbnode *nil, void (*op)(rbnode *))
{
	if(p != nil) {
        	inord(p->left,nil,op);
		printf("%d ", p->v);
        	inord(p->right,nil,op);
	}
}

/****************************************************************************/

void inorder(rbtree *p, void (*op)(rbnode *))
{
	inord(p->root, p->nil, op);
}

allocando un albero con:

rbtree *MioLberoRB;
MioLberoRB = creaAlberoRB();

e poi inserisco un pò di dati;

inserisci(MioLberoRB, 18 , 2, 3 ,4);
inserisci(MioLberoRB, 20 , 20, 30 ,40);
inserisci(MioLberoRB, 5 , 22, 32 ,42);

ora chiamo la inorder con: inord(MioLberoRB, treemin(MioLberoRB));

note: la treemin() mi ritorna la chiave minima dell'albero e che io passo come tipo nodo

[Fibrizio]

Originariamente inviato da misterx

ciao,
non ho ancora ben chiaro questo codice per la visita in-ordine di un albero RB.

void inord(rbnode *p, rbnode *nil, void (*op)(rbnode *))
{
	if(p != nil) {
        	inord(p->left,nil,op);
		printf("%d ", p->v);
        	inord(p->right,nil,op);
	}
}

/****************************************************************************/

void inorder(rbtree *p, void (*op)(rbnode *))
{
	inord(p->root, p->nil, op);
}

allocando un albero con:

rbtree *MioLberoRB;
MioLberoRB = creaAlberoRB();

e poi inserisco un pò di dati;

inserisci(MioLberoRB, 18 , 2, 3 ,4);
inserisci(MioLberoRB, 20 , 20, 30 ,40);
inserisci(MioLberoRB, 5 , 22, 32 ,42);

ora chiamo la inorder con: inord(MioLberoRB, treemin(MioLberoRB));

note: la treemin() mi ritorna la chiave minima dell'albero e che io passo come tipo nodo

cos'è che non ti è chiaro esattamente? La ricerca o l'ordinamento?

[Fibrizio]

Originariamente inviato da cionci

Dipende tutto da quello che si vuole fare...se si cercano le prestazioni è sicuramente meglio avere il puntatore al nodo che il valore, perché si arriva direttamente al nodo senza, nel worst case, attraversare tutta la profondità dell'albero.

Non ti cambia nulla, dal momento che devi effettuare lo scorrimento fino al nodo in ogni caso per leggerlo.

[misterx]

ciao,
nel frattempo ho modificato il codice e quello che non mi è chiaro è come funziona questa parte di codice:

void inord(rbnode *p, rbnode *nil)
{
	if(p != nil) {
        	inord(p->left,nil);
		printf("%d ",p->v);
        	inord(p->right,nil);
	}
}


void inorder(rbtree *p)
{
	inord(p->root, p->nil);
}

ora passo solo il puntatore della radice ed inserendo valori casuali, questi mi vengono mostrati in odine; mi chiedo se avendo implementato un RB è perchè questi sono già ordinati nell'albero ?

[Fibrizio]

Originariamente inviato da misterx

ciao,
nel frattempo ho modificato il codice e quello che non mi è chiaro è come funziona questa parte di codice:

void inord(rbnode *p, rbnode *nil)
{
	if(p != nil) {
        	inord(p->left,nil);
		printf("%d ",p->v);
        	inord(p->right,nil);
	}
}


void inorder(rbtree *p)
{
	inord(p->root, p->nil);
}

ora passo solo il puntatore della radice ed inserendo valori casuali, questi mi vengono mostrati in odine; mi chiedo se avendo implementato un RB è perchè questi sono già ordinati nell'albero ?

Ok, ho capito. Allora l'ordine deriva dal metodo con cui si compone l'albero. Per esempio inserendo dei numeri i più grandi a destra e i più piccoli a sinistra.
Quando cominci a leggere l'albero il codice dice:

if(p != nil) { se p è diverso da nil, ossia se quello che segue è un nodo allora

inord(p->left,nil);
richiama la funzione stessa sul ramo di sinistra

Ora immagina che l'albero sia quello proposto prima da DanieleC88

              4
         /         \
     2               5
  /     \           /    \
1        3      6       7

Prendo 4, il ramo di sinistra ha un valore, è 2, prendo 2, il ramo di sinistra ha un valore, è 1, prendo 1, il ramo di sinistra non ha alcun valore,

la funzione inord sul ramo di sinistra di 1 non fa niente, segue

printf("%d ",p->v);

che stampa 1

segue inord sul ramo di destra di 1, non stampa nulla, la funzione finisce.

erano rimaste in pausa le funzioni inord su 2 e 4. torniamo a 2,

stampa 2 su schermo con printf, poi esegue il controllo sul ramo di destra, è 3, prende 3. esegue il controllo sul ramo di sinistra, non c'è nulla, stampa 3, esegue il controllo a destra, non c'è nulla. la funzione finisce, si torna a 2.
Anche su 2 non c'è altro da fare, si torna su 4 e si stampa, si prende la funzione sul ramo di destra.

ecc ecc


Alla fine come vedi abbiamo stampato 1, 2, 3, 4 ...e così via, in ordine. Se vuoi invertire l'ordine fai inord prima sul ramo di destra e poi su quello di sinistra.

[misterx]

ciao e grazie,
ho notato che per capire si dovrebbe scoprire come funzionala insertRB ma è piuttosto complessa e richiederebbe troppo tempo per essere compresa; importante è sapere che i dati vengono messi ordinati come negli ABR in quanto gli RB sono ABR con in aggiunta la colorazione in aggiunta alle funzioni per mantenerlo tale giusto ?

rbnode *simpleinsert(rbtree *tree, int k)
{
	rbnode *q = malloc(sizeof(rbnode));
	rbnode *r = tree->root;
	rbnode *s = tree->nil;

	if(!q) { 
		fprintf(stderr,"Errore di allocazione C\n");
        	exit(-4);
	}
	q->v = k;
	q->left = q->right = tree->nil;
	q->c = red;
	while(r != tree->nil) {
		s = r;
		r = k < r->v ? r->left : r->right;
	}
	q->up = s;
	if(s == tree->nil)
		return tree->root = q;
	if(k < s->v)
		s->left = q;
	else
		s->right = q;
	return q;
}

/****************************************************************************/

void rbinsert(rbtree *tree, int k)
{
	rbnode *x = simpleinsert(tree, k);
	rbnode *y;

	while(x != tree->root && x->up->c == red) {
		if(x->up == x->up->up->left) {                 /* caso L */
			y = x->up->up->right;
			if(y->c == red) {
				x->up->c = black;                  /* caso 1L */
				y->c = black;                      /* caso 1L */
				x->up->up->c = red;                /* caso 1L */
				x = x->up->up;                     /* caso 1L */
			} else {
				if(x == x->up->right)              /* caso 2L */
					leftrotate(tree,x = x->up);  /* caso 2L */				
				x->up->c = black;                  /* caso 3L */
				x->up->up->c = red;                /* caso 3L */
				rightrotate(tree,x->up->up);       /* caso 3L */
			}
		} else {                                       /* caso R */
			y = x->up->up->left;
			if(y->c == red) {
				x->up->c = black;                  /* caso 1R */
				y->c = black;                      /* caso 1R */
				x->up->up->c = red;                /* caso 1R */
				x = x->up->up;                     /* caso 1R */
			} else {
				if(x == x->up->left)               /* caso 2R */
					rightrotate(tree,x = x->up); /* caso 2R */					
				x->up->c = black;                  /* caso 3R */
				x->up->up->c = red;                /* caso 3R */
				leftrotate(tree,x->up->up);        /* caso 3R */
			}
		}
	}
	tree->root->c = black;
}

[cionci]

Originariamente inviato da Fibrizio

Non ti cambia nulla, dal momento che devi effettuare lo scorrimento fino al nodo in ogni caso per leggerlo.

Allora...mettiamo delle semplici operazioni per entrambi i casi.
Caso in cui si ritornano nodi:

struct node * find_first_greater_than(int x); //ritorna un nodo se presente o NULL
void delete(struct node * n); //elimina il nodo

Caso in cui si ritornano valori:

bool find_first_greater_than(int x, int * v); //ritorna true se l'ha trovato, mette il valore in *v
void delete(int v); //elimina il valore v


Prima di tutto i due approcci non sono equivalenti. Con la seconda delete non siamo sicuri di elminare proprio quel v, visto che nel frattempo l'albero potrebbe essere stato ribilanciato.
La prima funzione in entrambi i casi ha un tempo di esecuzione proporzionale alla profondità dell'albero.
La seconda invece:
- nel primo caso ha un tempo di esecuzione costante o al proporzionale al tempo necessario a ribilanciare l'albero
- nel secondo caso ha un tempo di esecuzione proporzionale al tempo necessario a ribilanciare l'albero + il tempo di ricerca
Nel caso di alberi di dimensione molto grande questa differenza è tutt'altro che trascurabile.

[cionci]

Originariamente inviato da misterx

ciao e grazie,
ho notato che per capire si dovrebbe scoprire come funzionala insertRB ma è piuttosto complessa e richiederebbe troppo tempo per essere compresa; importante è sapere che i dati vengono messi ordinati come negli ABR in quanto gli RB sono ABR con in aggiunta la colorazione in aggiunta alle funzioni per mantenerlo tale giusto ?

Sono degli alberi binari di ricerca auto bilanciati. Tutto il codice che vedi in più serve per bilanciare nuovamente l'albero.
Stranamente wikipedia è fatta veramente bene in questo caso: http://it.wikipedia.org/wiki/RB-Albero

[DanieleC88]

Originariamente inviato da Fibrizio

E' irrilevante se ha uno o due figli, il problema si ripresenta anche se il nodo ha un riferimento al genitore e si risolve ordinando i due figli secondo il criterio di ordinamento dell'albero. Nel caso specifico del tuo esempio se togliamo il nodo con valore 2 possiamo tranquillamente reinserire sia l'1 che il 3, visto che l'ordinamento non dipende dall'ordine di inserimento.

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

Originariamente inviato da Fibrizio

[...] dove viene spiegato chiaramente che

Ossia il predecessore viene calcolato in maniera simmetrica al successore e non vi è necessità di un puntatore specifico, ma solo di destro e sinistro, e anzi impiegano perfino lo stesso tempo di calcolo!

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

Originariamente inviato da Fibrizio

Insomma non mi è ben chiaro dove hai trovato l'illuminante capitolo sull'essenzialità (?) di un puntatore al predecessore o alla radice dell'albero.
Che seppure sia possibile fare è tutt'altro che essenziale.

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, e tu mi stai semplicemente dicendo che è un'operazione senza senso. 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ì.
Che vogliamo fare a questo punto? Possiamo continuare ad oltranza, decidi tu.

Se poi non sei convinto di ciò che dico, puoi anche leggere l'ultima risposta di cionci e valutare da te. La sua parola è sicuramente più autorevole della mia, se non ti fidi né di me né del Cormen.

ciao

[misterx]

Originariamente inviato da cionci

Sono degli alberi binari di ricerca auto bilanciati. Tutto il codice che vedi in più serve per bilanciare nuovamente l'albero.
Stranamente wikipedia è fatta veramente bene in questo caso: http://it.wikipedia.org/wiki/RB-Albero

ciao,
effettivamente interessa maggiormente come lavora concettualmente un RB invece di conoscere a fondo l'implentazione finale.

Approfitto per una dritta visto il mio digiuno di C.

Devo leggere da standard input una stringa del tipo:

12 20 45 90 ......... e così via

avevo pensato ad una cosa del tipo
int cifra;
while((cifra = getchar()) != '\n')

ma credo di essere in parte sulla strada sbagliata

ciao

[DanieleC88]

Non andava bene scanf()?

[misterx]

Originariamente inviato da DanieleC88

Non andava bene scanf()?

ciao,
sai che lo sto provando proprio ora ma non funziona con lo '\n' ?

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


ma funziona con '\0'

[DanieleC88]

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