alberi binari

[misterx]

qualcuno sa rappresentarmi tale albero binario nei 3 attraversamenti principali ?

anticipato/simmetrico/posticipato

          7 
        /   \
       /     \
     11       8
     / \       \
    /   \       \
  20     4       2
  / \
 /   \
1     3

[mjordan]

Quello non è un albero binario.
Quella struttura dati la ha la particolarità che un figlio sinistro di un nodo deve avere la chiave < o = a quella del padre, mentre il figlio destro la deve avere strettamente maggiore.
O meglio: se quell'albero la lo vogliamo considerare un albero binario di ricerca (cioè una struttura dati) allora non ha senso, altrimenti rimaniamo nel puro ambito algebrico. E visto che stai parlando di visite dei nodi, siamo nell'ambito "strutture dati":

In ogni caso la visita simmetrica (come da nome stesso) significa che scorri i nodi del sottoalbero sinistro, poi la radice e infine i nodi del sottoalbero destro.
Ottieni quindi la seguente visita:
1, 20, 3, 11, 4, 7, 8, 2

Analogamente la visita di un albero binario in ordine anticipato significa che elenchi prima la radice e poi i sottoalberi:

7, 11, 20, 1, 3, 4, 8, 2

Per il differito si elencano prima i sottoalberi e solo alla fine si elenca la radice:

1, 3, 20, 4, 2, 11, 8, 7

Comunque sia, quello non è un albero binario di ricerca.

[misterx]

ok, di ricerca lo hai aggiunto tu; ma quello sotto ora lo è, un "albero di ricerca"

cmq, il mio libro li chiama "alberi binari"

quello che mi interessa capire è se vi è un ordine specifico da seguire

ti hai scritto 1 20 3 ma si poteva anche scrivere 1 3 20 ?

         20 
        /  \
       /    \
      7      24
     / \      \
    /   \      \
   2     11     30
  / \
 /   \
1     5

[mjordan]

No albero binario puro non è una struttura dati bensì una struttura algebrica.
Per illustratre i concetti molte volte si usano semplici "alberi binari". In realtà gli algoritmi vanno applicati su "alberi binari di ricerca" altrimenti quelli basati sulle chiavi di un nodo (per esempio inserzione di un nodo e cancellazione) non funzionano. Nel tuo caso le cose funzionano lo stesso perchè l'algoritmo ricorsivo di visita non usa le chiavi dei nodi.

L'ordine è quello. Non può essere modificato. In una visita di un albero, la sequenza di nodi visitabili è unica. Pertanto se due alberi binari sono uguali, la sequenza di nodi visitata è identica.

1, 3, 20, ..., non è uguale a 1, 20, 3, ...,

[Luc@s]

Originariamente inviato da misterx
cmq, il mio libro li chiama "alberi binari"

Che libro hai?

[Luc@s]

Originariamente inviato da mjordan
L'ordine è quello. Non può essere modificato.

Ma nn c'era la possibilità(ho letto ieri sul mio Sedgewick) di swappare i nodi(però li lo diceva se si doveva inserire un dato maggiore del padre di un BST, per nn costruirne uno identico tranne che x il padre)???

[/\/\@®¢Ø]

Originariamente inviato da mjordan
Quello non è un albero binario.
Quella struttura dati la ha la particolarità che un figlio sinistro di un nodo deve avere la chiave < o = a quella del padre, mentre il figlio destro la deve avere strettamente maggiore.
O meglio: se quell'albero la lo vogliamo considerare un albero binario di ricerca (cioè una struttura dati) allora non ha senso, altrimenti rimaniamo nel puro ambito algebrico. E visto che stai parlando di visite dei nodi, siamo nell'ambito "strutture dati":

Mah, mi sembra che sia un albero binario a tutti gli effetti. Oltretutto non e' neanche detto che non sia nemmeno di ricerca o ordinato perche' in linea generale la funzione (<=) non e' l'unica funzione di confronto utilizzabile.
In ogni caso nell'ambito delle strutture dati gli alberi binari non vengono utilizzati solo per inserimento/ricerca di dati; l'albero di parsing di una espressione (a sole funzioni binarie) ad esempio e' un albero binario ed e' una struttura dati con le contropalle .

[mjordan]

Un albero binario di ricerca è tale se e solo se la visita in ordine simmetrico restituisce la sequenza delle chiavi in modo ordinato. Altrimenti è un semplice albero binario. Anche gli alberi Red-Black oltre ad avere le loro proprietà, mantengono le proprietà degli alberi binari di ricerca, cioè le chiavi del sottoalbero sinistro sono <= di quelle del sottoalbero destro. Inoltre sebbene nessuno ti vieti di "inventare" nuove operazioni su un albero, bisogna considerare il significato "puro" dei termini. Un albero di parsing è un albero binario ma non un albero binario di ricerca. E' appunto un albero di parsing. Il fatto che la funzione "<=" non sia l'unica è sbagliato. In un nodo puoi inserire quello che vuoi ma devi avere sempre e solo una chiave che ti consenta di utilizzare confronti, altrimenti, ripeto, non è un albero di ricerca puro.
Cioè i confronti non li devi fare su quello che effettivamente vuoi memorizzare nei nodi. Le chiavi sono solo dei mezzi per manipolare le strutture e non come fanno vedere i libri, i dati su cui lavorare.

[cionci]

Ma lui non aveva chiesto un albero binario di ricerca...

"la visita in ordine simmetrico restituisce la sequenza delle chiavi in modo ordinato."

Dipende comunque dalla funzione di ordinamento

Concordo con /\/\@®¢Ø nel dire che un albero binario generico è comunque una struttura dati...

[VegetaSSJ5]

allora il mio prof distingueva gli alberi binari, cioè gli alberi formati da nodi che possono avere al max 2 figli, dagli ABR ovvero alberi binari di ricerca dove <figlio_sinistro> < <padre(o radice)> < <figlio_destro>.

cmq passando alle visite dovrebbero essere così:

simmetrica:
1-20-3-11-4-7-8-2

anticipata (inorder):
7-11-20-1-3-8-2

postiipata (postorder):
1-3-20-4-11-2-8-7

se ho sbagliato (molto probabile ) correggetemi.

[recoil]

diamo una definizione più rigorosa di albero binario:

un albero può dirsi binario se è vuoto oppure se la sua radice ha al massimo due nodi i quali sono a loro volta degli alberi binari.

in particolare si parla di albero binario completo se ogni nodo (escluse naturalmente le foglie) ha esattamente due figli e tutte le foglie sono allo stesso livello, quindi raggiungibili dalla radice con cammini di pari lunghezza.

in particolare possiamo notare che in un albero binario il tempo di accesso a ogni elemento è limitato dal logaritmo del numero di nodi, quindi è O(log n).
ciò rende gli alberi vantaggiosi per operazioni di inserimento/ricerca di elementi, non per niente si è parlato di alberi binari di ricerca

naturalmente bisogna cercare di bilanciare il più possibile gli elementi all'interno di un albero, poiché in una situazione simile a questa:

o
 \
  o
   \
    o

la ricerca di un elemento ha tempo lineare (come si usasse una lista). esistono alberi bilanciati, tra i quali gli alberi red&black e i b-alberi (questi però non sono binari).

per ora mi fermo qui

[misterx]

e volendo implementare in java tale albero ?

          7 
        /   \
       /     \
     11       8
     / \       \
    /   \       \
  20     4       2
  / \
 /   \
1     3

[recoil]

una piccola correzione, nell'ultima visita (quella posticipata) devi invertire 4 e 11

[mjordan]

Originariamente inviato da cionci

Dipende comunque dalla funzione di ordinamento

Scusa di che funzione di ordinamento parli?

Concordo con /\/\@®¢Ø nel dire che un albero binario generico è comunque una struttura dati...

Prima di essere una struttura dati è una struttura algebrica. Forse mi sono espresso male. Non intendevo dire che non è una struttura dati. Ho solo detto che gli algoritmi di visita classici se non è un ABR non funzionano correttamente

[mjordan]

Originariamente inviato da VegetaSSJ5
allora il mio prof distingueva gli alberi binari, cioè gli alberi formati da nodi che possono avere al max 2 figli, dagli ABR ovvero alberi binari di ricerca dove <figlio_sinistro> < <padre(o radice)> < <figlio_destro>.

Esatto. E' quello che sto facendo capire. Non possono essere scambiati per la stessa cosa.

[/\/\@®¢Ø]

Originariamente inviato da mjordan
Esatto. E' quello che sto facendo capire. Non possono essere scambiati per la stessa cosa.

Non per sembrare polemico (o si ? ) ma quello che ha fatto confusione sei stato tu , visto che non si parlava di ABR da nessuna parte prima del tuo intervento

[misterx]

e volendo implementare in java tale albero ?

          7 
        /   \
       /     \
     11       8
     / \       \
    /   \       \
  20     4       2
  / \
 /   \
1     3

[misterx]

recoil, hai la mail-box piena

[recoil]

Originariamente inviato da misterx
recoil, hai la mail-box piena

hai ragione, grazie per avermelo fatto notare

riguardo al tuo albero non capisco con che logica sono inseriti gli elementi

[Luc@s]

          7 
        /   \
       /     \
      /       \
    1              8
  / \              / \
 /   \            /   \
2    3           /     \
               11     20

Non ha + senso cosi??? IMHO