Newsgroup: it.comp.www.php
Titolo: A Modified Preorder Tree Traversal Algorithm

con questo algoritmo come posso fare per selezionare (mostrare) un solo 
livello dell'albero
non riesco a capire la query che devo fare per individurare un livello di 
profondità

yag wrote:

per selezionare tutti i discendenti di un elemento devi ricavare il valore
left ed il right e fare una query selezionando tutti i valori interni ai
due..
il livello come lo intendi tu (se ho capito cosa chiedi) lo ricavi cercando
all'interno dei valori compresi tra left e rigth gli elementi che non sono
contenuti all'interno di altri elementi del gruppo..
ex..
x 1 10
c 2 5
v 6 9
b 3 4 
n 7 8
l'albero e' (perdona la grafica)..
x[ c[ b] v[ n]]
per selezionare il primo livello (tutto quello locato subito sotto radice)..
cerchi i valori interni alla radice
c v b n
e poi selezioni tutti i valori che non sono contenuti all'interno di altri
di suddetto gruppo..
c v
-- 
www.iuz-lab.info

 c v
perdonami ma mi son perso potresti farmi un esempio poù dummyy  ? per dire 
da questo
x 1 10
c 2 5
v 6 9
b 3 4
n 7 8
come faccio a capire quali sono gli elementi subito dopo la root ?

 come faccio a capire quali sono gli elementi subito dopo la root ?
allora..
tu sai che la root e' x..
selezioni i 2 valori di x (1, 10)..
adesso selezioni tutti i valori compresi tra 1 e 10..
ora che hai tutti i nodi contenuti in root con i loro valori devi escludere
i sotto livelli..
un sotto livello di 1° grado lo distingui dal fatto che non e' contenuto in
nessun altro sotto livello della lista selezionata..
c e v rispondono a questo criterio poiche' nessun elemento della lista ha
contemporaneamente un valore di sinistra minore ed uno di destra maggiore a
c e v..
b e n invece non soddisfano questo criterio poiche' c(sinistra) <
b(sinistra) AND c(destra) > b(destra) mentre v(sinistra) < n(sinistra) AND
v(destra) > n(destra).. qualificandoli come sotto livelli di c e v..
se sei arrivato fino a qui e non hai capito non ti preoccupare..
per raggiungere il tuo scopo puoi semplificare notevolmente aggiungendo un
campo in modo da tracciare la relazione figlio, padre..
quindi la tabella si presenta..
  - x - 1 - 10
x - c - 2 - 5
x - v - 6 - 9
c - b - 3 - 4
v - n - 7 - 8
dove il primo campo e' il genitore..
adesso per determinare i sotto livelli di 1° grado di x ti bastera' una
semplice selezione con condizione di genitore = 'x', evitando di
sovracaricare con una ricerca inutile ed un algoritmo piu' complesso del
dovuto..
e' una piccola modifica ma d'altra parte questo tipo di albero una volta
popolato e' incline alla determinazione rapida di tutti i discendenti di un
nodo senza specificare l'araldica..
fammi sapere se hai capito..
-- 
www.iuz-lab.info

> perdonami ma mi son perso potresti farmi un esempio po dummyy  ? per

Ho capito abbastanza bene il tutto  più o meno ero arrivato a queste 
conclusione ma mi sembra alquanto macchinoso..
tu hai confermato comunque i miei dubbi grazie.
Un ultima (si fa per dire nota) ora vorrei capire come dovrei cambiare 
attuando questo approccio le operazioni di inserimento e cancellazione .. 
oppure non si applicano modifiche ?

 oppure non si applicano modifiche ?
no non e' macchinoso.. vedrai che appena avrai chiaro tutto il complesso ti
sembrera' tutto molto piu' semplice..
beh l'albero come dice il nome e' preordinato e la struttura impone che la
cancellazione senza il riordinamento implichi delle lacune nella
continuita' dei valori di sinistra e destra (lacune comunque gestibili)
mentre invece l'inserimento impone il riordinamento dell'intera struttura
(non so' che tipo di applicazione ti serve ma se gli inserimenti ed
eliminamenti sono frequenti non credo sia quello che fa al caso tuo)
-- 
www.iuz-lab.info

 eliminamenti sono frequenti non credo sia quello che fa al caso tuo)
[...]
si sono frequenti in quel caso cosa mi consigli ?
...
io parlavo del valore del livello... 

yag wrote:

credo che se fai modifiche frequenti e l'albero deve contenere molti nodi
sia meglio un algoritmo ad adiacenza semplice..
ci sarebbe anche un modo di adattare l'albero MPTT per lavorare velocemente
anche con modifiche frequenti ma sarebbe comunque difficile da gestire a
livello di algoritmo..
se vuoi ti creo uno script di esempio, ma non credo che ti converrebbe..
fammi sapere..
-- 
www.iuz-lab.info


Se vuoi si tanto non prenderei il codice ma lo studierei e basta.... se hai 
tempo vedi anche l'altro post
grazie mille

 ha scritto nel messaggio 
news:cgzWd.1012243$35.37...@news4.tin.it...

ho fatto un pň ricerca ho visto che ditemise sbaglio
SELECT COUNT(P2.id) AS 'level', P1.nome
   FROM personale AS P1, personale AS P2
  WHERE P1.sx BETWEEN P2.sx AND P2.dx
  GROUP BY P1.nome
  ORDER BY P1.sx;
con questa query trovo (mostro) tutto il nodo ordinato per livelli giusto ?
e quindi non mi serve il campo aggiuntivo per indicare il livello o sbaglio 
? 

 eliminamenti sono frequenti non credo sia quello che fa al caso tuo)
In pratica per gestire un catalogo - l'utente puň creare categorie e 
sottocategorie... eliminare ecc. 

 sbaglio ?
attento che come query e' piu' pesante di quella 'normale'..
visto che la natura prima di questo albero e' alleggerire il lavoro io
preferirei agiungere un campo (visto che il livello e' comunque un valore
statico)..
a cosa ti serve esattamente il livello di un nodo?
-- 
www.iuz-lab.info


Immagina la rappresentazione di un catalogo o il classi tree voglio mostra 
solo un livello (magari si espandono i sotto nodi tramite un + etc.)
solo per quello... in pratica... 


Ok ma come faccio poi per gli inserimento e cancellazioni ?

 solo per quello... in pratica...
ora credo di capire quello che hai in mente..
allora se vuoi visualizzare una struttura (per capirci) come quella usata
per i NG
- x
  -_ y
     +_ g
     +_ h
+ z
allora e' meglio se usi un albero ad adiacenza normalmente strutturato
se invece vuoi visualizzare una cosa del genere..
-path
-to
-selection
 + item
 + item
 + item
allora puoi usare l'MPTT ma magari mantenendo anche il campo parent nel db
per trovare piu' agevolmente il livello desiderato oppure usando parte
della funzione sotto citata.. 
con attenzione alla parte (while ($right[count($right)-1]<$row['rgt']))
<?php
function display_tree($root) { 
  $result = mysql_query("SELECT lft, rgt FROM tree WHERE title='$root'");
  $row = mysql_fetch_array($result); 
  $right = array(); 
  $result = mysql_query("SELECT title, lft, rgt FROM tree WHERE lft BETWEEN
'{$row['lft']}' AND '{$row['rgt']}' ORDER BY lft ASC"); 
 
  while ($row = mysql_fetch_array($result)) {  
    if (count($right)>0) { 
      while ($right[count($right)-1]<$row['rgt']) { 
        array_pop($right); 
      } 
    } 
    echo str_repeat('--',count($right)).$row['title']."\n"; 
    $right[] = $row['rgt']; 
  }
} 
?>
-- 
www.iuz-lab.info

 Ok ma come faccio poi per gli inserimento e cancellazioni ?
tenendo conto che hai letto anche l'altro post nell'albero ad adiacenza
procedi come dovuto..
nel MPTT devi per forza ricalcolare i valori di sinistra e destra (almeno
nella parte interessata dell'albero).. 
-- 
www.iuz-lab.info