come attraversare il nodo figlio dal nodo genitore nell'albero n-ary? [chiuso]

Question

come attraversare il nodo figlio dal nodo genitore nell'albero n-ary? [chiuso]

#1 da (2 voti)

1

In un albero n-ary ...

Fornito un riferimento ad un nodo figlio
E un riferimento a un genitore distante del nodo figlio referenziato
Esiste un metodo che un nodo genitore può usare per capire quale dei suoi figli è più vicino al nodo figlio referenziato e ha un grande-oh che è minore di O (numero di spigoli tra genitore e figlio)

Immagine per illustrare la mia domanda:

              A                        
              |                        
              |                        
              B                        
             / \                       
            /   \                      
           C     D <-- distant parent  
                /|\                    
               / | \                   
              E  F  G  <-- which child?
             /|  |\  \                 
            / |  | \  \                
           H  I  J  K  L               
          /  /|    /|\                 
         /  / |   / | \                
        M  N  O  P  Q  R               
              ^     |                  
              |     |                  
That child node     S

( immagine originale )

Cose che ho provato:

Iterare l'albero (O (n)), da "quel nodo figlio" fino a quando viene trovato il genitore e restituire il nodo visitato in precedenza. Questo è il momento in cui ho notato che il mio programma impiegava troppo tempo per iterare l'albero e poteva usare qualche tipo di miglioramento.
Chiedi a ciascun nodo di salvare un riferimento a ogni singolo genitore presente in un array e l'indice utilizzato è il numero di spigoli tra il nodo nell'array e il nodo radice.

Esempio: "quel nodo figlio" avrà una matrice di dimensione 5, e il suo genitore immediato sarà nell'indice 4, e la radice, l'indice 0.

Vantaggio: questo consente di trovare il nodo da restituire molto rapidamente (O (1)) perché, il livello (numero di spigoli tra il nodo e il nodo radice) + 1 del nodo genitore , mi darà l'indice nella matrice in "quel nodo figlio" del nodo che voglio restituire.

Svantaggio: l'aggiunta di nodi all'albero diventa molto costosa in memoria e il tempo di calcolo, soprattutto se il nodo è molto lontano dal nodo radice. costoso in memoria, perché avrà un enorme array e tempo di computazione perché l'array deve essere popolato, deve essere popolato da tree traversal o copiare l'array dal suo genitore, può volerci un po 'di tempo ...
Come sopra, eccetto, invece di salvare riferimenti a ogni nodo, salva i riferimenti al nodo log2 (livello) ai nodi, in un modo simile a log2 ()

Esempio: un nodo a livello 1000000 avrebbe 20 riferimenti a nodi padre. questi riferimenti sarebbero rivolti a un genitore a ciascuno dei seguenti livelli: 500000, 750000, 875000, 937500, 968750 ... 999999.

Advanage: trova il nodo da restituire in O (log2 (n)) a O (n), non veloce quanto la soluzione sopra, ma abbastanza veloce. molto più efficiente della memoria rispetto alla soluzione precedente, ma ancora piuttosto male.

Svantaggio: è ancora piuttosto costoso aggiungere nuovi nodi all'albero in tempo di calcolo, ma non così male.

Posso pensare alle variazioni del suddetto 3 metodo per rendere le cose leggermente più efficienti in termini di memoria ed efficienti nel tempo, ma mi chiedo se c'è un metodo che impiega O (1) tempo per trovare la soluzione a questo problema Non vedo ... qualcosa come la proprietà dell'albero di ricerca binario, ma per un albero n-ario.

La proprietà dell'albero di ricerca binaria è desiderabile, poiché dato un nodo figlio, il genitore può fare un passo verso di esso, indipendentemente dal numero di fronti tra il nodo figlio dato e il genitore.

Non mi interessa inserire un indice o ID o dati aggiuntivi nel nodo figlio per rendere il metodo possibile.

trees graph-traversal binary-tree

posta Eric 04.11.2014 - 08:05

fonte

1 risposta

Leggi altre domande sui tag trees graph-traversal binary-tree

esiste qualcosa chiamato schema logico e lo schema concettuale di una tabella di database? Devo nascondere determinati codici di stato HTTP?

score 2 · Accepted Answer

Posso pensare a una varietà di possibili soluzioni, ma tutte implicano un sovraccarico di memoria elevato.

Lascia che k sia il numero di nodi genitore candidato, ℓ il livello del nodo figlio distante (ovvero la distanza dalla radice), c il nodo figlio e p il nodo genitore candidato ( s).

`O(k)` : memorizza le indicazioni stradali per ogni nodo

Ogni nodo ha una matrice ordinata di ID (ad esempio puntatori) di tutti gli antenati. Questo array può essere inteso come le direzioni dalla radice a quel nodo. Per verificare se un nodo p è padre di un altro nodo n , dobbiamo semplicemente confrontare l'ID al livello appropriato:

fun is_parent(c: Node, p: Node): Bool =
  c.directions[p.directions.length - 1] == p.id

Vantaggi: storage piuttosto compatto.

Svantaggi: l'inserimento di nodi è piuttosto costoso perché le loro indicazioni devono essere aggiornate.

`O(k)` a `O(k log ℓ)` - Salva set di tutti gli antenati

Questa è una variante della soluzione di cui sopra, ma utilizza solo una sorta di set (o una lista ordinata per ID piuttosto che per livello). A seconda di come viene implementato quel set, la complessità algoritmica della ricerca è diversa.

fun is_parent(c: Node, p: Node): Bool =
  c.ancestors.contains(p.id)

Questo condivide gli stessi vantaggi e svantaggi della soluzione precedente.

`O(k log ℓ_c)` , worst case `O(k ℓ)` - Skip Lists

Questa è una variante della prima soluzione, ma con un sovraccarico di memoria molto inferiore.

Un elenco di salto è un elenco collegato che contiene non solo un puntatore all'elemento successivo, ma anche a elementi più distanti. Ciò consente la ricerca di O(log n) in un elenco di salti ordinato, simile a una ricerca binaria in un array. Gli elenchi di salto possono anche essere utilizzati per l'indicizzazione efficiente negli elenchi collegati, che è ciò che faremo qui. Il nostro "indice" è in realtà il livello relativo di un nodo.

Nel nostro caso, ogni bambino contiene almeno un link ai genitori immediati, ma probabilmente anche ad altri antenati. Un link è una coppia di puntatori al nodo di destinazione e di un numero intero che ci dice quanti livelli questo link avanza.

data Link(distance: Int, target: Node)

fun is_parent(c: Node, p: Node): Bool = {
  val skip_length = p.level - c.level
  if (skip_length <= 0)
    return c.id == p.id
  // Node.links stores links sorted in descending distance
  val link = c.links.first(link => link.distance <= skip_length)
  return is_parent(link.target, p)
}

Vantaggi: utilizza meno memoria rispetto alle altre soluzioni.

Svantaggio: ha O (n) il caso peggiore (quando l'elenco dei salti degrada in una semplice lista concatenata). Questo può essere evitato re-threading della skip list al momento dell'inserimento.

come attraversare il nodo figlio dal nodo genitore nell'albero n-ary? [chiuso]

1 risposta

O(k) : memorizza le indicazioni stradali per ogni nodo

O(k) a O(k log ℓ) - Salva set di tutti gli antenati

O(k log ℓc) , worst case O(k ℓ) - Skip Lists

`O(k)` : memorizza le indicazioni stradali per ogni nodo

`O(k)` a `O(k log ℓ)` - Salva set di tutti gli antenati

`O(k log ℓ_c)` , worst case `O(k ℓ)` - Skip Lists