Mondo Java: Algoritmo della settimana: Trovare il più basso antenato comune

Introduzione

Ecco un compito relativo alla struttura di dati ad albero. Dati due nodi, si può trovare il loro minimo comune antenato?

È un dato di fatto, questo compito ha sempre una soluzione adeguata perché almeno il nodo radice è sempre un antenato comune di tutte le coppie di nodi. Tuttavia, qui il compito è di trovare il più basso, che può essere abbastanza lontano dalla radice.

A noi non importa che tipo di alberi che abbiamo. Tuttavia la soluzione, come vedremo, può essere molto diverso a seconda del tipo di albero. In effetti trovare il minimo comune antenato può avere complessità lineare per gli alberi binari di ricerca, che non è vero per gli alberi normali.

Panoramica

Diciamo che abbiamo un albero (non binario!) E due nodi di questo albero. Il compito è quello di trovare il loro minimo comune antenato. Il fatto è che non ne so molto di cui sembrano essere nella struttura.

Possiamo pensare a questo albero come un albero DOM di una linea singola pagina HTML. Non è binario o bilanciata e non può essere sicuro dove questi nodi sono.

Prima dobbiamo trovare entrambi i percorsi dalla radice a ciascuno dei nodi di destinazione. Si noti che questo richiede memoria aggiuntiva! Poi, nel tempo lineare, siamo in grado di passare attraverso questi "percorsi" ed eseguirà la scansione dalla radice verso il basso per i nodi. Ci aspettiamo che questi array di essere uguali almeno nel loro primo elemento (la radice). L'utilizzo di questo scenario il più basso antenato comune è l'ultimo elemento uguale in entrambi gli array.

Una volta che sappiamo i percorsi dalla radice verso il basso per i nodi, possiamo confrontare, al fine di trovare il minimo comune antenato!

Per vedere come questo algoritmo può essere cambiato radicalmente a seconda della struttura dei dati, vediamo un altro esempio. Ora diciamo che abbiamo un albero binario di ricerca (BST). Sappiamo che in un BST tutti gli elementi della sub-tree sinistra sono più piccole della radice e tutti gli elementi sulla destra sub-tree sono maggiori della radice. Questo è vero anche per la sinistra e la destra sotto-alberi.

Ora, perché stiamo cercando il più basso antenato comune, non abbiamo bisogno di raccogliere i percorsi dalla radice ai nodi in due matrici. Sappiamo solo che gli elementi superiori siano a destra, mentre gli oggetti più piccoli sono a sinistra. Questo può aiutarci a trovare la tariffa più antenato partendo direttamente dalla radice.

In un BST confrontiamo entrambi i valori con un dato nodo (a partire dalla radice). Nel caso in cui il valore del nodo è in mezzo a loro - questo è il minimo antenato comune. In caso contrario - andiamo sia a sinistra oa destra!

Quello che facciamo è quello di confrontare le due chiavi dei nodi di destinazione con il tasto principale.Se uno dei tasti sono più piccoli, e l'altro è maggiore di chiave della radice, allora ovviamente la radice è il più basso antenato comune. Questo è vero perché uno degli elementi sarà in qualche parte sinistra sub-tree, mentre l'altro sarà nella giusta sub-tree.

Nel caso in cui entrambi i valori sono maggiori (o minori) che la radice, siamo in grado di spostarsi a destra (oa sinistra) sub-tree e riprovare con la stessa procedura. Così il primo nodo che chiave è tra i due valori di destinazione sarà il più basso antenato comune.

Codice

Ecco una applicazione molto semplice PHP che ci mostra questi due algoritmi.

classe Albero

{

pubblico $ nodo = null;

pubblico $ id = null;

pubblico $ genitore = null;

pubblico $ bambini = matrice ();

 

pubblica funzione __construct ( $ node , $ id = null)

{

$ this -> nodo = $ nodo ;

$ this -> id = $ id ;

}

 

pubblica funzione addChild (Node e $ n )

{

$ n - genitore> = $ this ;

$ this -> figli [] = $ n ;

}

 

/ **

* Restituisce un elemento dal suo ID

*

* @ param $ id mescolati

* @ return nodo

* /

pubblica funzione di ricerca ( $ id )

{

se ( $ this -> id == $ id ) {

ritorno $ this ;

}

 

$ a = false;

 

/ / ricerca in tutti i bambini a partire dai più a sinistra

foreach ( $ this -> bambini da $ bambino ) {

$ a = $ bambino -> Ricerca ( $ id );

}

 

ritorno $ a ;

}

 

/ **

* Trova un percorso dalla radice alla

* voce e la restituisce come una lista

*

​​* @ param $ id mescolati

* @ return array di

* /

pubblica funzione find_path ( $ id , & $ path )

{

array_push ( $ path , $ this -> id);

 

se ( $ this -> id == $ id ) {

ritorno 1;

}

 

foreach ( $ this -> bambini da $ bambino ) {

se (1 == $ bambino -> find_path ( $ id , $ path )) di ritorno 1;

array_pop ( $ path );

}

}

 

pubblica funzione __toString ()

{

ritorno $ this - nodo>. ' ' . $ this -> id. "\ n" ;

}

}

 

$ dom = nuovo Albero ( 'DOM' , 'root' );

 

$ corpo = nuovo Albero ( 'BODY' , 1);

$ div1 = nuovo Albero ( 'DIV' , 'div-1' );

$ div2 = nuovo Albero ( 'DIV' , 'my-id' );

 

$ a = nuovo albero ( "A" , 'un po' di-link ' );

 

$ dom - addChild> ( $ body );

$ corpo - addChild> ( $ div1 );

$ corpo - addChild> ( $ div2 );

$ div2 - addChild> ( $ a );

 

$ path1 = $ path2 = matrice ();

$ dom -> find_path ( 'div-1' , $ path1 );

$ dom -> find_path ( 'un po-link' , $ path2 );

Trovare più basso antenato comune in un BST

classe Albero

{

pubblica $ chiave ;

 

pubblico $ genitore   = null;

. 06pubblica $ sinistra     = null;

pubblico $ destra    = null;

 

pubblica funzione __construct ( $ key )

{

$ this -> key = $ chiave ;

}

 

pubblica funzione insert (Albero $ n )

{

se ( $ this -> tasto < $ n - tasto>) {

se ( $ this -> destro == null) {

/ / inserire

$ this -> diritto = $ n ;

. 20$ n - genitore> = $ this ;

} else {

$ this -> tasto destro> insert ( $ n );

}

}

se ( $ this -> tasto> $ n - tasto>) {

se ( $ this -> sinistro == null) {

/ / inserire

$ this -> sinistra = $ n ;

$ n - genitore> = $ this ;

} else {

$ this -> sinistra-> insert ( $ n );

}

}

}

}

 

$ t = nuovo albero (10);

 

$ n1 = nuovo albero (20);

. 40$ n2 = nuovo albero (5);

$ n3 = nuovo albero (7);

$ n4 = nuovo albero (13);

 

$ t - inserto> ( $ n1 );

. 45$ t - inserto> ( $ n2 );

​​$ t -> insert ( $ n3 );

 

funzione find_common ( $ node1 , node2 $ , $ albero )

{

se ( $ node1 -> tasto < $ albero -> && chiave $ node2 -> tasto> $ albero- tasto>) {

ritorno $ albero ;

} else se ( $ node1 -> tasto < $ albero -> && chiave $ node2 -> tasto <$ albero - tasto>) {

find_common ( $ node1 , node2 $ , $ albero - a sinistra>);

} else se ( $ node1 -> tasto> $ albero -> && chiave $ node2 -> tasto> $ albero - tasto>) {

find_common ( $ node1 , node2 $ , $ albero -> destra);

}

}

 

$ nodo = find_common ( $ n3 , n4 $ , $ t );

Applicazione

Un tipico caso d'uso di questo algoritmo è trovare il minimo comune antenato di due nodi in un albero DOM. A volte abbiamo solo bisogno di collegare un listener di eventi per entrambe le voci (anche prima di essere attaccato al DOM!). Anche se questo evento per attaccare il "documento" funziona bene, di tutti gli elementi dai nodi fino alla radice sarà "catturare" questi eventi a causa di bubbling degli eventi.Quindi collegare l'evento al più basso antenato comune è una soluzione migliore.

Corso Java - Corsi Java - Corsi programmazione Java

Corso programmazione Android - Certificazione Android