Hva er et treemap i Java?

Verdien av en node i et tre kalles nøkkelen. Et binært tre er et tre, der hver node ikke har mer enn to barn. Et binært søketre (BST) er et tre, der for hver node er det høyre barnet større enn eller lik det venstre barnet. Dette fører til at høyre halvdel av treet har verdier generelt større enn de venstre halvdelen på hvert nivå. Dette betyr at et binært søket er delvis sortert (en type ufullstendig sortering). En BST kan holdes i en matrise-lignende struktur, med rotnoden som den første verdien.

Et binært tre kan gjøres til forskjellige selvbalanserende trær med forskjellige sett med tilleggsforhold, for eksempel AVL-treet og det rød-svarte treet.

Treemap i Java er et rødt svart tre. Imidlertid består hver node av en nøkkel og tilsvarende verdi (nøkkel/verdipar) i stedet for bare en nøkkel. Hvert nøkkel/verdipar vil være ett element i en matrise-lignende struktur. Denne artikkelen forklarer hvordan du bruker et treemap i Java, som begynner med et binært søketre, etterfulgt av det rød-svarte treet, og deretter Java Treemap.

Artikkelinnhold

• Binært søketre
• Rød-svart tre
• Nøkkel/verdipar for Java Treemap
• Java Treemap Construction
• Java Treemap -metoder
• Konklusjon

Binært søketre

Følgende er et eksempel på et binært søketre:

Hver node har en nøkkel. Nøkkelen (verdien) for rotnoden er 8. Det venstre barnet er 3 og det høyre barnet er 10 (10> = 3). Det kan sees at for enhver node som har to barn, er det rette barnet større enn eller lik det venstre barnet. Den høyre halvdelen av treet har også verdier som er større enn venstre halvdel av treet for hvert nivå.

Alle verdiene til treet ovenfor kan plasseres i en matrise, som følger:

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

Legg merke til at matrisen (treet) begynner klokka 8; stiger ned til 3, stiger deretter til utover 8 ved 10; stiger ned til 1, stiger til 6, har deretter nils, til 14; stiger ned til 4; stiger til 7; Nils igjen; deretter 13 og siste null.

8 er den første verdien ved indeks 0. Det er rotnoden (rotforelder). Det er ikke nødvendigvis den største verdien mellom alle verdiene. Det første barnet (3) er ved indeks 1, hvis indeks er lik 2 (0) + 1, der 0 er indeksen for foreldrene. Det andre barnet (10) er ved indeks 2, som er lik 2 (0) + 2, der 0 er indeksen for foreldrene.

3 er ved indeks 1. Det er en forelder. Det første barnet (1) er ved indeks 3, som er lik 2 (1) + 1, der 1 er indeksen for foreldrene. Det andre barnet (6) er på indeks 4, som er lik 2 (1) + 2, der 1 er indeksen for foreldrene.

6 er på indeks 4. Det er en forelder. Det første barnet (4) er ved indeks 9, som er lik 2 (4) + 1, der 4 er indeksen for foreldrene. Det andre barnet (7) er ved indeks 10, som er lik 2 (4) + 2, der 4 er indeksen for foreldrene.

10 er ved indeks 3. Det er en forelder. Det har ikke noe første (venstre) barn, som skulle være på indeks 7, som er lik 2 (3) + 1, der 3 er indeksen for foreldrene. Det andre barnet (14) er ved indeks 8, som er lik 2 (3) + 2, der 3 er indeksen for foreldrene.

14 er ved indeks 8. Det er en forelder. Det første barnet (13) er på indeks 17, som er lik 2 (8) + 1, der 8 er indeksen for foreldrene. Det har ingen rett (andre) barn, som skulle være på indeks 18, som er lik 2 (8) + 2, der 8 er indeksen for foreldrene.

Generelt sett som indekstelling begynner fra 0. La jeg representere indeksen til en forelder av matrisen; Og så, venstre (første) barn av en forelder ved indeks I, er ved indeks 2i + 1; og dets høyre (andre) barn, er på indeks 2i + 2. Noen celler i matrisen kan være tomme; De må ikke ha verdier.

Rød-svart tre

Et rødt svart tre er et binært søketre, som er balansert. Følgende er et allerede balansert rød-svart tre:

Et balansert tre er et tre med kort høyde. Nodeposisjonene endres og merket med røde og blå farger for å ha den korteste trehøyden som mulig i utviklingen.

Ved å bruke formlene, 2i + 1 og 2i + 2, kan verdiene settes i en matrise-lignende struktur som følger:

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

Legg merke til at matrisen starter klokken 13, stiger til 8 og deretter stiger til 17. Den går deretter nedover 8 til 1 og stiger deretter til 11, deretter 15, deretter 25; hvorfra det er en null, og så går den ned til 6. Nils følger før 22 og 27.

Utvalget av et balansert tre, som det rød-svart treet over, har færre nils enn det tilsvarende binære søketreet som ikke er balansert. Arrayens lengde på et balansert tre er kortere enn det tilsvarende treet som ikke er balansert.

Et rødt svart tre er et delvis ordnet tre.

Nøkkel/verdipar for Java Treemap

Det forrige rød-svart-treet har bare nøkler som nodeverdier. Hver heltallstast kan gis en tilsvarende strengverdi. Følgende liste har de samme tastene med tilsvarende verdier:

13/tretten, 8/åtte, 17/sytten, 1/en, 11/elleve, 15/femten, 25/tjuefem, 6/seks, 22/tjueto, 27/tjueen-syv

Dette er nøkkel/verdipar som er egnet for et Java Treemap. Hver tast blir kartlagt til den tilsvarende verdien. Et nøkkel/verdipar kalles et kartinngang i Java. For Java Treemap er arrangementet av nodene laget av nøkler (ikke verdier av nøkkelen/verdiparene). Hver tast er kartlagt til verdien.

Java Treemap Construction

I Java er Treemap en klasse i Java.util.* pakke, som skal importeres. Denne klassen har fire konstruktører, og to konstruktører er illustrert i denne artikkelen.

Offentlig treemap ()

Dette konstruerer et tomt treemap. Følgende kodesegment illustrerer dette:

Treemap TM = nytt Treemap();
tm.put (13, "tretten"); tm.put (8, "åtte"); tm.put (17, "sytten"); tm.put (1, "en");
tm.put (11, "elleve"); tm.put (15, "femten"); tm.put (25, "tjuefem"); tm.put (6, "seks");
tm.put (22, "tjueto"); tm.put (27, "tjuesju");

Put () -metoden inkluderer nøkkel/verdipar til Treemap. Etter alt dette blir treemapet balansert internt.

Offentlig treemap (kart m)

Denne konstruktørmetoden lager et kart fra et annet allerede opprettet kart, som i følgende kodesegment:

Treemap TM = nytt Treemap();
tm.put (13, "tretten"); tm.put (8, "åtte"); tm.put (17, "sytten"); tm.put (1, "en");
tm.put (11, "elleve"); tm.put (15, "femten"); tm.put (25, "tjuefem"); tm.put (6, "seks");
tm.put (22, "tjueto"); tm.put (27, "tjuesju");
Treemap TM1 = nytt Treemap(tm);

TM1 er opprettet fra TM. Etter alt dette balanserte begge treemaps internt; med den første balanserte først. Balansering foregår da nøkler inkluderer par.

Java Treemap -metoder

Public V Put (K Key, V -verdi)

Strengt tatt legger ikke put () -metoden til et nøkkel-/verdipar. Den knytter en bestemt verdi til en bestemt nøkkel. Hvis nøkkelen allerede eksisterte i Treemap med en annen verdi, erstattes verdien med den nye. Denne metoden returnerer den gamle verdien eller null hvis det ikke var noen gammel verdi. Bruken av denne metoden er påvist ovenfor.

Offentlig int -størrelse ()

Denne metoden returnerer antallet nøkkel/verdiskart (par) i Treemap. Følgende kodesegment viser hvordan du bruker det:

int it = tm.størrelse();
System.ute.println (it);

Utgangen er 10, noe som indikerer at det er 10 nøkkel/verdipar i dette Treemap -objektet.

Public v Get (Objektnøkkel)

Denne metoden returnerer verdien som tilsvarer argumentet, som er nøkkelen. Den returnerer null hvis nøkkelen ikke eksisterer. Følgende kode illustrerer dette for nøkkelen/verdiparet: 11/”elleve”, og for nøkkelen, 40, som ikke eksisterer:

String val = tm.få (11); String str = tm.få (40);
System.ute.print (val + ","); System.ute.print (str + "");
System.ute.println ();

Utgangen er:

Elleve, null

Public Set Keyset ()

Denne metoden returnerer et sett-visning av nøklene som er i Treemap. For å vise nøklene, må iteratoren brukes. Følgende kodesegment for forrige Treemap illustrerer dette:

Sett ST = TM.Keyset ();
Iterator iter = st.iterator ();
mens (iter.hasnext ())
System.ute.trykk (iter.neste () + ",");

System.ute.println ();

Utgangen er:

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

Returlisten er fullstendig sortert (stigende), selv om Treemap har delvis intern sortering.

Offentlige innsamlingsverdier ()

Dette returnerer innsamlingsvisning (liste) for alle verdiene i Treemap, uten nøklene. For å vise verdiene, må iteratoren brukes. Følgende kodesegment for forrige Treemap illustrerer dette:

Samling col = tm.verdier ();
Iterator iter = col.iterator ();
mens (iter.hasnext ())
System.ute.trykk (iter.neste () + ",");

System.ute.println ();

Utgangen er:

en, seks, åtte, elleve, tretten, femten, sytten, tjueto, tjuefem, tjuesju,

Verdiene er vist basert på deres komplette sorterte nøkler (stigende), selv om Treemap har delvis sortering internt.

Offentlig sett Entryset ()

Dette returnerer et sett med nøkkel/verdipar. For å vise tastene og deres tilsvarende verdier, må iteratoren brukes. Følgende kodesegment for ovennevnte Treemap illustrerer dette:

Sett> par = tm.inngangssett ();
Iterator> iter = par.iterator ();
mens (iter.hasnext ())
Kart.Inngang etry = iter.neste ();
int i = etry.getKey (); String str = etry.getValue ();
System.ute.println (i + "=>" + str);

Utgangen er:

1 => en
6 => seks
8 => åtte
11 => elleve
13 => Tretten
15 => femten
17 => sytten
22 => tjueto
25 => tjuefem
27 => tjuesju

Parene er vist basert på deres komplette sorterte nøkler (stigende), selv om Treemap har delvis sortering internt.

Konklusjon

I Java er et treemap et rødt svart tre, som er et selvbalanserende binært søketre. De ofte brukte metodene og Java Treemap -konstruksjonen har blitt diskutert i denne artikkelen. Vi håper du fant denne informasjonen nyttig. Sjekk ut de andre Linux -hint -artiklene for flere tips og opplæringsprogrammer.