Cos'è un TreeMap in Java?

Il valore di un nodo in un albero è chiamato tasto. Un albero binario è un albero, in cui ogni nodo non ha più di due bambini. Un albero di ricerca binario (BST) è un albero, in cui per ogni nodo, il bambino destro è maggiore o uguale al bambino sinistro. Questo porta alla metà destra dell'albero con valori generalmente maggiori di quelli della metà sinistra ad ogni livello. Ciò significa che un albero di ricerca binario è parzialmente ordinato (un tipo di ordinamento incompleto). Un BST può essere mantenuto in una struttura simile a un array, con il nodo radice che è il primo valore.

Un albero binario può essere trasformato in diversi alberi a bilanciamento con diversi set di condizioni aggiuntive, come l'albero AVL e l'albero rosso nero.

Il Treemap in Java è un albero rosso nero. Tuttavia, ciascun nodo è costituito da una chiave e un valore corrispondente (coppia chiave/valore) anziché solo una chiave. Ogni coppia chiave/valore sarebbe un elemento in una struttura simile a un array. Questo articolo spiega come usare un TreeMap in Java, a cominciare da un albero di ricerca binaria, seguito dall'albero rosso-nero, e poi dal Java TreeMap.

Contenuto dell'articolo

• Albero di ricerca binaria
• Albero rosso-nero
• Coppie chiave/valore per Java TreeMap
• Java Treemap Construction
• Metodi Java TreeMap
• Conclusione

Albero di ricerca binaria

Quello che segue è un esempio di un albero di ricerca binaria:

Ogni nodo ha una chiave. Il tasto (valore) per il nodo radice è 8. Il bambino sinistro è 3 e il bambino destro è 10 (10> = 3). Si può vedere che per qualsiasi nodo che abbia due figli, il bambino destro è maggiore o uguale al bambino sinistro. Inoltre, la metà destra dell'albero ha valori maggiori di quelli della metà sinistra dell'albero per ogni livello.

Tutti i valori dell'albero sopra possono essere posizionati in un array, come segue:

8, 3, 10, 1, 6 ,,, 14, 4, 7 ,,,,, 13, ,

Si noti che l'array (albero) inizia a 8; scende a 3, quindi sale oltre 8 a 10; scende a 1, sale a 6, quindi ha zero, fino a 14; scende a 4; sale a 7; Nils di nuovo; poi 13 e l'ultimo zero.

8 è il primo valore all'indice 0. È il nodo radice (radice genitore). Non è necessariamente il valore più grande tra tutti i valori. Il suo primo figlio (3) è all'indice 1, il cui indice è uguale a 2 (0) + 1, dove 0 è l'indice del genitore. Il suo secondo figlio (10) è all'indice 2, che è uguale a 2 (0) + 2, dove 0 è l'indice del genitore.

3 è all'indice 1. È un genitore. Il suo primo figlio (1) è all'indice 3, che è uguale a 2 (1) + 1, dove 1 è l'indice del genitore. Il suo secondo figlio (6) è all'indice 4, che è uguale a 2 (1) + 2, dove 1 è l'indice del genitore.

6 è all'indice 4. È un genitore. Il suo primo figlio (4) è all'indice 9, che è uguale a 2 (4) + 1, dove 4 è l'indice del genitore. Il suo secondo figlio (7) è all'indice 10, che è uguale a 2 (4) + 2, dove 4 è l'indice del genitore.

10 è all'indice 3. È un genitore. Non ha il primo bambino (a sinistra), che doveva essere all'indice 7, che è uguale a 2 (3) + 1, dove 3 è l'indice del genitore. Il suo secondo figlio (14) è all'indice 8, che è uguale a 2 (3) + 2, dove 3 è l'indice del genitore.

14 è all'indice 8. È un genitore. Il suo primo figlio (13) è all'indice 17, che è uguale a 2 (8) + 1, dove 8 è l'indice del genitore. Non ha un bambino giusto (secondo), che doveva essere all'indice 18, che è uguale a 2 (8) + 2, dove 8 è l'indice del genitore.

In generale, poiché il conteggio dell'indice inizia da 0. Lascia che rappresenti l'indice di un genitore dell'array; E così, il figlio (primo) di sinistra di un genitore all'indice I, è all'indice 2i + 1; e il suo bambino giusto (secondo), è all'indice 2i + 2. Alcune celle nell'array possono essere vuote; Non devono avere valori.

Albero rosso-nero

Un albero rosso-nero è un albero di ricerca binario, equilibrato. Quello che segue è un albero rosso-nero già bilanciato:

Un albero equilibrato è un albero con un'altezza breve. Le posizioni del nodo sono cambiate e contrassegnate con colori rossi e blu per avere l'altezza dell'albero più corta possibile nel suo sviluppo.

Usando le formule, 2i + 1 e 2i + 2, i valori possono essere inseriti in una struttura simile a un array come segue:

13, 8, 17, 1, 11, 15, 25 ,, 6 ,,, 22, 27

Si noti che l'array inizia a 13, scende a 8 e poi sale a 17. Quindi scende oltre 8 a 1 e poi sale a 11, quindi 15, quindi 25; da cui c'è un zero, e poi scende a 6. Nils seguono prima del 22 e 27.

L'array di un albero equilibrato, come l'albero rosso-nero sopra, ha meno zero rispetto al suo corrispondente albero di ricerca binario che non è bilanciato. La lunghezza dell'array di un albero bilanciato è più corta dell'albero corrispondente che non è bilanciato.

Un albero rosso-nero è un albero parzialmente ordinato.

Coppie chiave/valore per Java TreeMap

Il precedente albero rosso nero ha solo tasti come valori di nodo. Ogni chiave intero può essere assegnato un valore di stringa corrispondente. L'elenco seguente ha le stesse chiavi con i valori corrispondenti:

13/tredici, 8/8, 17/settente, 1/uno, 11/undici, 15/quindici, 25/venticinque, 6/sei, 22/ventidue, 27/ventisette

Queste sono coppie chiave/valore adatte per un Java TreeMap. Ogni chiave verrà mappata al suo valore corrispondente. Una coppia chiave/valore è chiamata mappa-entry in java. Per Java TreeMap, la disposizione dei nodi è fatta da tasti (non valori delle coppie di tasti/valore). Ogni chiave è mappata al suo valore.

Java Treemap Construction

In Java, TreeMap è una classe nel Java.util.* pacchetto, che dovrebbe essere importato. Questa classe ha quattro costruttori e due costruttori sono illustrati in questo articolo.

Public TreeMap ()

Questo costruisce un treemap vuoto. Il seguente segmento di codice illustra questo:

TreeMap tm = nuovo TreeMap();
tm.put (13, "tredici"); tm.put (8, "otto"); tm.put (17, "diciassette"); tm.put (1, "uno");
tm.put (11, "undici"); tm.put (15, "quindici"); tm.put (25, "venticinque"); tm.put (6, "sei");
tm.put (22, "ventidue"); tm.put (27, "ventisette");

Il metodo Put () include coppie di tasti/valore al TreeMap. Dopo tutto ciò, il TreeMap diventa bilanciato internamente.

Treemap pubblico (mappa M)

Questo metodo del costruttore crea una mappa da un'altra mappa già creata, come nel seguente segmento di codice:

TreeMap tm = nuovo TreeMap();
tm.put (13, "tredici"); tm.put (8, "otto"); tm.put (17, "diciassette"); tm.put (1, "uno");
tm.put (11, "undici"); tm.put (15, "quindici"); tm.put (25, "venticinque"); tm.put (6, "sei");
tm.put (22, "ventidue"); tm.put (27, "ventisette");
TreeMap TM1 = nuovo TreeMap(TM);

TM1 è creato da TM. Dopo tutto ciò, entrambi i traemap hanno bilanciato internamente; con il primo equilibrato per primo. Il bilanciamento si svolge quando le chiavi includono coppie.

Metodi Java TreeMap

Public v put (K Key, V Value)

A rigor di termini, il metodo put () non aggiunge una coppia di tasti/valore. Associa un valore particolare a una chiave particolare. Se la chiave esisteva già nel TreeMap con un valore diverso, il valore viene sostituito con quello nuovo. Questo metodo restituisce il vecchio valore o null se non c'era un vecchio valore. L'uso di questo metodo è stato dimostrato sopra.

Public int size ()

Questo metodo restituisce il numero di mappature chiave/valore (coppie) nel TreeMap. Il seguente segmento di codice mostra come usarlo:

int it = tm.misurare();
Sistema.fuori.println (it);

L'output è 10, indicando che ci sono 10 coppie chiave/valore in questo oggetto TreeMap.

Public v get (tasto oggetto)

Questo metodo restituisce il valore corrispondente all'argomento, che è la chiave. Restituisce null se la chiave non esiste. Il seguente codice lo illustra per la coppia chiave/valore: 11/"undici" e per la chiave, 40, che non esiste:

String Val = TM.Ottieni (11); Stringa str = tm.Ottieni (40);
Sistema.fuori.stampa (val + ","); Sistema.fuori.stampa (str + "");
Sistema.fuori.println ();

L'output è:

Undici, null

Public Set KeySet ()

Questo metodo restituisce una visione set delle chiavi che si trovano nel TreeMap. Per visualizzare i tasti, l'iteratore deve essere utilizzato. Il seguente segmento di codice per il precedente TreeMap illustra questo:

Impostato ST = TM.mazzo di chiavi();
Iteratore iter = st.iteratore ();
mentre (iter.hasNext ())
Sistema.fuori.Stampa (iter.Next () + ",");

Sistema.fuori.println ();

L'output è:

1, 6, 8, 11, 13, 15, 17, 22, 25, 27,

L'elenco di restituzione è completamente ordinato (ascendente), sebbene il TreeMap abbia un ordinamento interno parziale.

Valori di raccolta pubblica ()

Questo restituisce la visione della raccolta (elenco) di tutti i valori nel TreeMap, senza le chiavi. Per visualizzare i valori, l'iteratore deve essere utilizzato. Il seguente segmento di codice per il precedente TreeMap illustra questo:

Collezione col = tm.valori();
Iteratore iter = col.iteratore ();
mentre (iter.hasNext ())
Sistema.fuori.Stampa (iter.Next () + ",");

Sistema.fuori.println ();

L'output è:

uno, sei, otto, undici, tredici, quindici, diciassette, ventidue, venticinque, venticinesimi,

I valori sono stati visualizzati in base alle loro chiavi ordinate complete (ascendente), sebbene il TreeMap abbia un smistamento parziale internamente.

Set pubblico EntrySet ()

Questo restituisce un set di coppie chiave/valore. Per visualizzare i tasti e i loro valori corrispondenti, l'iteratore deve essere utilizzato. Il seguente segmento di codice per il TreeMap sopra illustra questo:

Impostato> coppie = tm.entryset ();
Iteratore> iter = coppie.iteratore ();
mentre (iter.hasNext ())
Carta geografica.Iscrizione etry = iter.Prossimo();
int in = etry.getKey (); String str = etry.getValue ();
Sistema.fuori.println (in + "=>" + str);

L'output è:

1 => uno
6 => sei
8 => otto
11 => undici
13 => tredici
15 => quindici
17 => diciassette
22 => ventidue
25 => venticinque
27 => ventisette

Le coppie sono state visualizzate in base alle loro chiavi ordinate complete (ascendenti), sebbene il TreeMap abbia un smistamento parziale internamente.

Conclusione

In Java, un TreeMap è un albero rosso-nero, che è un albero di ricerca binaria auto-bilanciante. I metodi comunemente usati e la costruzione di Java Treemap sono stati discussi in questo articolo. Speriamo che tu abbia trovato utili queste informazioni. Dai un'occhiata agli altri articoli di suggerimento Linux per ulteriori suggerimenti e tutorial.