Was ist ein Treemap in Java?

Der Wert eines Knotens in einem Baum wird als Schlüssel bezeichnet. Ein binärer Baum ist ein Baum, bei dem jeder Knoten nicht mehr als zwei Kinder hat. Ein binärer Suchbaum (BST) ist ein Baum, bei dem für jeden Knoten das rechte Kind größer oder gleich dem linken Kind ist. Dies führt zu der rechten Hälfte des Baumes mit Werten, die im Allgemeinen größer sind als die der linken Hälfte auf jeder Ebene. Dies bedeutet, dass ein binärer Suchbaum teilweise sortiert ist (eine Art unvollständiger Sortierung). Ein BST kann in einer Array-ähnlichen Struktur gehalten werden, wobei der Wurzelknoten der erste Wert ist.

Ein binärer Baum kann zu verschiedenen selbstausgleichenden Bäumen mit verschiedenen Sätzen zusätzlicher Bedingungen wie dem AVL-Baum und dem rotschwarzen Baum verarbeitet werden.

Das Treemap in Java ist ein rotschwarzer Baum. Jeder Knoten besteht jedoch aus einem Schlüssel und einem entsprechenden Wert (Schlüssel-/Wertpaar) anstelle eines Schlüssels. Jedes Schlüssel-/Wertpaar wäre ein Element in einer Array-ähnlichen Struktur. In diesem Artikel wird erklärt.

Artikelinhalt

• Binärer Suchbaum
• Rotschwarzer Baum
• Schlüssel-/Wertpaare für Java Treemap
• Java Treemap -Konstruktion
• Java Treemap -Methoden
• Abschluss

Binärer Suchbaum

Das Folgende ist ein Beispiel für einen binären Suchbaum:

Jeder Knoten hat einen Schlüssel. Der Schlüssel (Wert) für den Stammknoten beträgt 8. Das linke Kind ist 3 und das rechte Kind ist 10 (10> = 3). Es ist ersichtlich, dass für jeden Knoten mit zwei Kindern das rechte Kind größer oder gleich dem linken Kind ist. Auch die rechte Hälfte des Baumes hat Werte, die größer sind als die der linken Hälfte des Baumes für jede Ebene.

Alle Werte des obigen Baumes können wie folgt in ein Array platziert werden:

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

Beachten Sie, dass das Array (Baum) bei 8 beginnt; steigt auf 3 ab und steigt dann auf 8 um 10 auf; steigt auf 1 ab, steigt auf 6, hat dann Nils, bis 14; steigt auf 4 ab; steigt auf 7; Wieder Nils; dann 13 und der letzte Null.

8 ist der erste Wert bei Index 0. Es ist der Stammknoten (Root übergeordnet). Es ist nicht unbedingt der größte Wert unter allen Werten. Sein erstes Kind (3) befindet sich bei Index 1, dessen Index 2 (0) + 1 entspricht, wobei 0 der Index des übergeordneten ist. Sein zweites Kind (10) liegt bei Index 2, was gleich 2 (0) + 2 entspricht, wobei 0 der Index des Elternteils ist.

3 ist am Index 1. Es ist ein Elternteil. Sein erstes Kind (1) liegt in Index 3, was gleich 2 (1) + 1 entspricht, wobei 1 der Index des Elternteils ist. Sein zweites Kind (6) liegt bei Index 4, der 2 (1) + 2 entspricht, wobei 1 der Index des Elternteils ist.

6 ist am Index 4. Es ist ein Elternteil. Sein erstes Kind (4) liegt in Index 9, was 2 (4) + 1 entspricht, wobei 4 der Index des Elternteils ist. Sein zweites Kind (7) liegt bei Index 10, was 2 (4) + 2 entspricht, wobei 4 der Index des Elternteils ist.

10 ist am Index 3. Es ist ein Elternteil. Es hat kein erstes (links) Kind, das in Index 7 sein sollte, was gleich 2 (3) + 1 entspricht, wobei 3 der Index des Elternteils ist. Sein zweites Kind (14) liegt bei Index 8, was 2 (3) + 2 entspricht, wobei 3 der Index des Elternteils ist.

14 ist am Index 8. Es ist ein Elternteil. Sein erstes Kind (13) befindet sich in Index 17, was 2 (8) + 1 entspricht, wobei 8 der Index des Elternteils ist. Es hat kein rechtes (zweites) Kind, das sich in Index 18 befinden sollte, was 2 (8) + 2 entspricht, wobei 8 der Index des Elternteils ist.

Im Allgemeinen beginnt das Indexzählen von 0. Lassen Sie mich den Index eines Elternteils des Arrays darstellen; und so ist das linke (erste) Kind eines Elternteils bei Index I in Index 2i + 1; und sein rechtes (zweites) Kind ist bei Index 2i + 2. Einige Zellen im Array können leer sein; Sie dürfen keine Werte haben.

Rotschwarzer Baum

Ein rotschwarzer Baum ist ein binärer Suchbaum, der ausgewogen ist. Das Folgende ist ein bereits ausgewogener rotschwarzer Baum:

Ein ausgewogener Baum ist ein Baum mit einer kurzen Höhe. Die Knotenpositionen werden verändert und mit roten und blauen Farben markiert, um die kürzeste Baumhöhe in seiner Entwicklung zu haben.

Unter Verwendung der Formeln 2i + 1 und 2i + 2 können die Werte wie folgt in eine Array-ähnliche Struktur eingefügt werden:

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

Beachten Sie, dass das Array bei 13 beginnt, auf 8 abfällt und dann auf 17 erhöht wird. Es steigt dann über 8 bis 1 ab und erhebt sich dann auf 11, dann 15, dann 25; von dem es einen Null gibt, und dann steigt es auf 6 ab. Nils folgen vor 22 und 27.

Die Anordnung eines ausgewogenen Baumes hat wie der rotschwarzige Baum oben weniger NILs als seinen entsprechenden binären Suchbaum, der nicht ausgeglichen ist. Die Arraylänge eines ausgewogenen Baumes ist kürzer als der entsprechende Baum, der nicht ausgeglichen ist.

Ein rotschwarzer Baum ist ein teilweise bestellter Baum.

Schlüssel-/Wertpaare für Java Treemap

Der vorherige rot-schwarze Baum hat nur Schlüssel als Knotenwerte. Jeder Ganzzahl -Schlüssel kann ein entsprechender Zeichenfolgenwert erhalten. Die folgende Liste enthält die gleichen Schlüssel mit entsprechenden Werten:

13/Dreizehn, 8/acht, 17/siebzehn, 1/eins, 11/elf, 15/fünfzehn, 25/fünfundzwanzig, 6/sechs, 22/22, 27/siebenundzwanzig

Dies sind Schlüssel-/Wertpaare, die für eine Java -Treemap geeignet sind. Jeder Schlüssel wird seinem entsprechenden Wert zugeordnet. Ein Schlüssel-/Wertpaar wird als Karteneingang in Java bezeichnet. Für die Java -Treemap erfolgt die Anordnung der Knoten durch Schlüssel (keine Werte der Schlüssel-/Wertpaare). Jeder Schlüssel wird seinem Wert zugeordnet.

Java Treemap -Konstruktion

In Java ist Treemap eine Klasse in der Java.Util.* Paket, das importiert werden sollte. Diese Klasse hat vier Konstruktoren, und in diesem Artikel werden zwei Konstruktoren veranschaulicht.

Öffentliche Treemap ()

Dies konstruiert eine leere Treemap. Das folgende Codesegment zeigt dies:

Treemap TM = neues Treemap();
tm.put (13, "dreizehn"); tm.put (8, "acht"); tm.put (17, "siebzehn"); tm.put (1, "eins");
tm.put (11, "elf"); tm.put (15, "fünfzehn"); tm.put (25, "fünfundzwanzig"); tm.put (6, "sechs");
tm.Put (22, "22"); tm.Put (27, "siebenundzwanzig");

Die Put () -Methode enthält Schlüssel-/Wertpaare zum Treemap. Nach all dem wird das Treemap in intern ausgeglichen.

Öffentliches Treemap (Karte M)

Diese Konstruktormethode erstellt wie im folgenden Codesegment eine Karte aus einer anderen bereits erstellten Karte:

Treemap TM = neues Treemap();
tm.put (13, "dreizehn"); tm.put (8, "acht"); tm.put (17, "siebzehn"); tm.put (1, "eins");
tm.put (11, "elf"); tm.put (15, "fünfzehn"); tm.put (25, "fünfundzwanzig"); tm.put (6, "sechs");
tm.Put (22, "22"); tm.Put (27, "siebenundzwanzig");
Treemap tm1 = neuer Treemap(TM);

TM1 wird aus TM erstellt. Nach all dem haben beide Treemaps intern ausgeglichen; mit dem ersten zuerst ausgeglichen. Balancing findet statt, da Tasten Paare enthalten.

Java Treemap -Methoden

Öffentlich V Put (K Key, V -Wert)

Streng genommen fügt die Put () -Methode kein Schlüssel-/Wertpaar hinzu. Es assoziiert einen bestimmten Wert einem bestimmten Schlüssel. Wenn der Schlüssel bereits im Treemap mit einem anderen Wert existierte, wird der Wert durch den neuen ersetzt. Diese Methode gibt den alten Wert oder Null zurück, wenn es keinen alten Wert gab. Die Verwendung dieser Methode wurde oben gezeigt.

Öffentliche int size ()

Diese Methode gibt die Anzahl der Schlüssel-/Wert -Zuordnungen (Paare) in der Treemap zurück. Das folgende Codesegment zeigt, wie es verwendet wird:

int it = tm.Größe();
System.aus.println (es);

Die Ausgabe ist 10, was angibt, dass in diesem Treemap -Objekt 10 Schlüssel-/Wertpaare enthält.

Öffentlich V GET (Objektschlüssel)

Diese Methode gibt den Wert zurück, der dem Argument entspricht, der der Schlüssel ist. Es gibt null zurück, wenn der Schlüssel nicht existiert. Der folgende Code zeigt dies für das Schlüssel-/Wertpaar: 11/”elf” und für den Schlüssel 40, der nicht vorhanden ist:

String val = tm.Holen Sie sich (11); String str = tm.Holen Sie sich (40);
System.aus.print (val + ","); System.aus.print (str + "");
System.aus.println ();

Die Ausgabe ist:

Elf, Null

Public Set Keyset ()

Diese Methode gibt einen Set-View der Schlüssel zurück, die sich in der Treemap befinden. Um die Schlüssel anzuzeigen, muss der Iterator verwendet werden. Das folgende Codesegment für das vorherige Treemap zeigt Folgendes:

Satz ST = TM.Schlüsselsatz();
Iterator iter = st.Iterator ();
während (Iter.HasNext ())
System.aus.drucken (iter.next () + ",");

System.aus.println ();

Die Ausgabe ist:

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

Die Rückkehrliste ist vollständig sortiert (aufsteigend), obwohl die Treemap eine teilweise interne Sortierung hat.

Öffentliche Sammelwerte ()

Dadurch wird die Sammelansicht (Liste) aller Werte in der Treemap ohne die Schlüssel zurückgegeben. Um die Werte anzuzeigen, muss der Iterator verwendet werden. Das folgende Codesegment für das vorherige Treemap zeigt Folgendes:

Sammlung col = tm.Werte();
Iterator iter = col.Iterator ();
während (Iter.HasNext ())
System.aus.drucken (iter.next () + ",");

System.aus.println ();

Die Ausgabe ist:

Eins, sechs, acht, elf, dreizehn, fünfzehn, siebzehn, zweiundzwanzig, fünfundzwanzig, siebenundzwanzig,

Die Werte wurden basierend auf ihren kompletten Sortierschlüssel (aufsteigend) angezeigt, obwohl die Treemap in intern eine teilweise Sortierung aufweist.

Öffentliches Set Einstieg ()

Dies gibt eine Reihe von Schlüssel-/Wertpaaren zurück. Um die Schlüssel und deren entsprechenden Werte anzuzeigen, muss der Iterator verwendet werden. Das folgende Codesegment für das obige Treemap zeigt Folgendes:

Satz> Paare = TM.EinstiegSet ();
Iterator> iter = pairs.Iterator ();
während (Iter.HasNext ())
Karte.Eintrag ERTRY = ITER.nächste();
int in = etry.getKey (); String Str = Emers.Wert erhalten();
System.aus.println (in + "=>" + str);

Die Ausgabe ist:

1 => eins
6 => sechs
8 => acht
11 => elf
13 => dreizehn
15 => fünfzehn
17 => siebzehn
22 => 22
25 => fünfundzwanzig
27 => siebenundzwanzig

Die Paare wurden basierend auf ihren kompletten sortierten Schlüssel (aufsteigend) angezeigt, obwohl die Treemap in intern eine teilweise Sortierung hat.

Abschluss

In Java ist ein Treemap ein rotschwarzer Baum, der ein selbstausgleichender binärer Suchbaum ist. Die häufig verwendeten Methoden und die Java -Treemap -Konstruktion wurden in diesem Artikel erörtert. Wir hoffen, dass Sie diese Informationen hilfreich gefunden haben. Weitere Tipps und Tutorials finden Sie in den anderen Linux -Hinweisartikeln.