Co to jest Treemapa w Javie?

Wartość węzła w drzewie nazywa się klucz. Drzewo binarne to drzewo, w którym każdy węzeł nie ma więcej niż dwoje dzieci. Drzewo wyszukiwania binarnego (BST) to drzewo, w którym dla każdego węzła prawe dziecko jest większe lub równe lewym dziecku. Prowadzi to do prawej połowy drzewa o wartościach na ogół większych niż w lewej połowie na każdym poziomie. Oznacza to, że binarne drzewo wyszukiwania jest częściowo sortowane (rodzaj niepełnego sortowania). BST może być przechowywany w strukturze przypominającej tablicę, przy czym węzeł główny jest pierwszą wartością.

Drzewo binarne można wykonać w różne same równoważenie drzew z różnymi zestawami dodatkowych warunków, takich jak drzewo avl i czerwone czarne drzewo.

Treemapa w Javie to czerwono-czarne drzewo. Jednak każdy węzeł składa się z klucza i odpowiedniej wartości (para klucza/wartości) zamiast tylko klucza. Każda para klucza/wartości byłaby jednym elementem w strukturze podobnej do tablicy. W tym artykule wyjaśniono, jak użyć Treemapa w Javie, zaczynając od binarnego drzewa wyszukiwania, a następnie czerwono-czarnego drzewa, a następnie Java Treemap.

Treść artykułu

• Drzewo wyszukiwania binarnego
• Czerwone czarne drzewo
• Pary klucza/wartości dla Java Treemap
• Java Treemap Construction
• Metody Java Treemap
• Wniosek

Drzewo wyszukiwania binarnego

Poniżej znajduje się przykład binarnego drzewa wyszukiwania:

Każdy węzeł ma klucz. Klucz (wartość) dla węzła głównego to 8. Lewe dziecko ma 3, a prawe dziecko to 10 (10> = 3). Można zauważyć, że w każdym węźle, który ma dwoje dzieci, prawe dziecko jest większe lub równe lewym dziecku. Również prawa połowa drzewa ma wartości większe niż w lewej połowie drzewa dla każdego poziomu.

Wszystkie wartości powyższego drzewa można umieścić w tablicy, jak następuje:

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

Zauważ, że tablica (drzewo) zaczyna się o 8; schodzi do 3, a następnie wznosi się do 8 o 10; schodzi do 1, wznosi się do 6, a następnie ma zerowe, do 14; schodzi do 4; wznosi się do 7; Znowu zerowe; Następnie 13 i ostatni zero.

8 to pierwsza wartość w indeksie 0. Jest to węzeł główny (główny nadrzędny). Niekoniecznie jest to największa wartość wśród wszystkich wartości. Jego pierwsze dziecko (3) jest w indeksie 1, którego indeks jest równy 2 (0) + 1, gdzie 0 jest wskaźnikiem rodzica. Jego drugie dziecko (10) znajduje się w indeksie 2, który jest równy 2 (0) + 2, gdzie 0 jest wskaźnikiem rodzica.

3 jest w indeksie 1. To rodzic. Jego pierwsze dziecko (1) znajduje się w indeksie 3, który jest równy 2 (1) + 1, gdzie 1 jest wskaźnikiem rodzica. Jego drugie dziecko (6) znajduje się w indeksie 4, który jest równy 2 (1) + 2, gdzie 1 jest wskaźnikiem rodzica.

6 jest w indeksie 4. To rodzic. Jego pierwsze dziecko (4) znajduje się w indeksie 9, który jest równy 2 (4) + 1, gdzie 4 jest wskaźnikiem rodzica. Jego drugie dziecko (7) jest w indeksie 10, który jest równy 2 (4) + 2, gdzie 4 jest wskaźnikiem rodzica.

10 znajduje się na indeksie 3. To rodzic. Nie ma pierwszego (lewego) dziecka, które miało być w indeksie 7, co jest równe 2 (3) + 1, gdzie 3 jest wskaźnikiem rodzica. Jego drugie dziecko (14) znajduje się w indeksie 8, który jest równy 2 (3) + 2, gdzie 3 jest wskaźnikiem rodzica.

14 jest na indeksie 8. To rodzic. Jego pierwsze dziecko (13) znajduje się w indeksie 17, który jest równy 2 (8) + 1, gdzie 8 jest wskaźnikiem rodzica. Nie ma właściwego (drugiego) dziecka, które miało być przy indeksie 18, co jest równe 2 (8) + 2, gdzie 8 jest wskaźnikiem rodzica.

Ogólnie rzecz biorąc, gdy zliczanie indeksu rozpoczyna się od 0. Niech reprezentuję wskaźnik rodzica tablicy; I tak, lewe (pierwsze) dziecko rodzica przy indeksie I, znajduje się w indeksie 2i + 1; a jego prawe (drugie) dziecko jest w indeksie 2i + 2. Niektóre komórki w tablicy mogą być puste; Nie mogą mieć wartości.

Czerwone czarne drzewo

Czerwone czarne drzewo to binarne drzewo wyszukiwania, które jest zrównoważone. Poniżej znajduje się już zrównoważone czerwone czarne drzewo:

Zrównoważone drzewo to drzewo o krótkiej wysokości. Pozycje węzłów są zmieniane i oznaczone czerwonymi i niebieskimi kolorami, aby mieć możliwą wysokość drzewa w swoim rozwoju.

Za pomocą wzorów, 2i + 1 i 2i + 2, wartości można umieścić w strukturze podobnej do tablicy w następujący sposób:

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

Zauważ, że tablica zaczyna się od 13, schodzi do 8, a następnie wznosi się do 17. Następnie schodzi ponad 8 do 1, a następnie wznosi się do 11, następnie 15, następnie 25; z którego jest zero, a następnie schodzi do 6. Nils następują przed 22 i 27.

Westra. Długość tablicy zrównoważonego drzewa jest krótsza niż odpowiednie drzewo, które nie jest zrównoważone.

Czerwone czarne drzewo to częściowo uporządkowane drzewo.

Pary klucza/wartości dla Java Treemap

Poprzednie czerwono-czarne drzewo ma tylko klucze jako wartości węzłów. Każdy klawisz liczb całkowitych może otrzymać odpowiednią wartość ciągu. Poniższa lista ma te same klucze z odpowiednimi wartościami:

13/trzynaście, 8/ósemka, 17/siedemnaście, 1/jeden, 11/Eleven, 15/piętnaście, 25/dwadzieścia pięć, 6/sześć, 22/dwadzieścia dwa, 27/dwadzieścia siedem

Są to pary kluczowe/wartości odpowiednie dla Java Treemap. Każdy klucz zostanie zmapowany na odpowiednią wartość. Para klucza/wartości nazywa się entry mapy w Javie. W przypadku Treemapa Java rozmieszczenie węzłów jest wykonywane przez klucze (nie wartości par kluczy/wartości). Każdy klucz jest mapowany na jego wartość.

Java Treemap Construction

W Javie Treemap to klasa w Javie.Util.* Pakiet, który należy zaimportować. Ta klasa ma cztery konstruktory, a dwa konstruktory są zilustrowane w tym artykule.

Public Treemap ()

To konstruuje pustą moc. Poniższy segment kodu to ilustruje:

Treemap tm = nowy Treemap();
tm.Put (13, „trzynaście”); tm.Put (8, „Eight”); tm.Put (17, „siedemnaście”); tm.Put (1, „jeden”);
tm.Put (11, „Eleven”); tm.Put (15, „piętnaście”); tm.Put (25, „dwadzieścia pięć”); tm.Put (6, „Six”);
tm.Put (22, „Twenty-dwa”); tm.Put (27, „dwadzieścia siedem”);

Metoda put () zawiera pary klucza/wartości z Treemap. Po tym wszystkim treemapa staje się zrównoważona wewnętrznie.

Public Treemap (mapa m)

Ta metoda konstruktora tworzy mapę z innej już utworzonej mapy, jak w następującym segmencie kodu:

Treemap tm = nowy Treemap();
tm.Put (13, „trzynaście”); tm.Put (8, „Eight”); tm.Put (17, „siedemnaście”); tm.Put (1, „jeden”);
tm.Put (11, „Eleven”); tm.Put (15, „piętnaście”); tm.Put (25, „dwadzieścia pięć”); tm.Put (6, „Six”);
tm.Put (22, „Twenty-dwa”); tm.Put (27, „dwadzieścia siedem”);
Treemap tm1 = nowy Treemap(TM);

TM1 jest tworzony z TM. Po tym wszystkim oba treremy zrównoważone wewnętrznie; z pierwszym zrównoważonym pierwszym. Równoważenie odbywa się, ponieważ klucze obejmują pary.

Metody Java Treemap

Public v put (key key, wartość v)

Ściśle mówiąc, metoda put () nie dodaje pary klucza/wartości. Wiąże się z określoną wartością do konkretnego klucza. Jeśli klucz istniał już w Treemapie o innej wartości, wartość jest zastąpiona nową. Ta metoda zwraca starą wartość lub null, jeśli nie było starej wartości. Zastosowanie tej metody zostało pokazane powyżej.

Public int size ()

Ta metoda zwraca liczbę mapowań kluczy/wartości (par) w Treemapie. Poniższy segment kodu pokazuje, jak go używać:

int it = tm.rozmiar();
System.na zewnątrz.println (it);

Wyjście to 10, co wskazuje, że w tym obiekcie Treemap jest 10 par kluczy/wartości.

Public v get (klucz obiektu)

Ta metoda zwraca wartość odpowiadającą argumentowi, który jest kluczem. Zwraca Null, jeśli klucz nie istnieje. Poniższy kod ilustruje to dla pary klucza/wartości: 11/„Eleven”, a dla klucza 40, który nie istnieje:

String Val = TM.Get (11); String str = tm.Zdobądź (40);
System.na zewnątrz.print (val + ","); System.na zewnątrz.print (str + "");
System.na zewnątrz.println ();

Wyjście to:

Jedenaście, Null

Publiczny zestaw keyset ()

Ta metoda zwraca na widok klawisze, które są w Treemapie. Aby wyświetlić klawisze, iterator należy użyć. Poniższy segment kodu dla poprzedniego TrereMap ilustruje to:

Ustawić ST = TM.zestaw kluczy();
Iterator ITER = ST.iterator ();
When (Iter.HASNEXT ())
System.na zewnątrz.Wydrukuj (ITER.następny () + ",");

System.na zewnątrz.println ();

Wyjście to:

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

Lista powrotna jest całkowicie posortowana (rosnąca), chociaż Treemap ma częściowe sortowanie wewnętrzne.

Publiczne wartości kolekcji ()

Zwraca to widok kolekcji (lista) wszystkich wartości w Treemapie, bez klawiszy. Aby wyświetlić wartości, należy użyć iteratora. Poniższy segment kodu dla poprzedniego TrereMap ilustruje to:

Kolekcja col = tm.wartości ();
Iterator ITER = col.iterator ();
When (Iter.HASNEXT ())
System.na zewnątrz.Wydrukuj (ITER.następny () + ",");

System.na zewnątrz.println ();

Wyjście to:

jeden, sześć, osiem, jedenaście, trzynaście, piętnaście, siedemnaście, dwadzieścia dwa, dwadzieścia pięć, dwadzieścia siedem lat,

Wartości zostały wyświetlone w oparciu o ich pełne posortowane klucze (rosnące), chociaż Treemap ma częściowe sortowanie wewnętrzne.

Zestaw publiczny Entymet ()

Zwraca zestaw par kluczy/wartości. Aby wyświetlić klawisze i odpowiednie wartości, iterator musi być użyty. Poniższy segment kodu powyższego TrereMap ilustruje to:

Ustawić> pary = tm.EntrySet ();
Iterator> ITER = pary.iterator ();
When (Iter.HASNEXT ())
Mapa.Wejście Etry = ITER.Następny();
int in = etry.Weź klucz(); String Str = Etry.getValue ();
System.na zewnątrz.println (in + "=>" + str);

Wyjście to:

1 => jeden
6 => sześć
8 => ósme
11 => Jedenaście
13 => trzynaście
15 => piętnaście
17 => siedemnaście
22 => dwadzieścia dwa
25 => dwadzieścia pięć
27 => Dwadzieścia siedem

Pary zostały wyświetlone w oparciu o ich pełne sortowane klucze (rosnące), chociaż Treemap ma częściowe sortowanie wewnętrzne.

Wniosek

W Javie treemapa jest czerwono-czarnym drzewem, które jest samowystarczalnym drzewem binarnym. Powszechnie stosowane metody i konstrukcja Java Treemap zostały omówione w tym artykule. Mamy nadzieję, że ta informacja była pomocna. Sprawdź inne artykuły w Linux, aby uzyskać więcej wskazówek i samouczków.