Qu'est-ce qu'un Treemap à Java?

La valeur d'un nœud dans un arbre est appelée la clé. Un arbre binaire est un arbre, où chaque nœud n'a pas plus de deux enfants. Un arbre de recherche binaire (BST) est un arbre, où pour chaque nœud, l'enfant droit est supérieur ou égal à l'enfant gauche. Cela conduit à la moitié droite de l'arbre ayant des valeurs généralement supérieures à celles de la moitié gauche à chaque niveau. Cela signifie qu'un arbre de recherche binaire est partiellement trié (un type de tri incomplet). Un BST peut être conservé dans une structure semblable à un tableau, le nœud racine étant la première valeur.

Un arbre binaire peut être transformé en différents arbres d'auto-équilibrage avec différents ensembles de conditions supplémentaires, tels que l'AVL et l'arbre rouge-noir.

Le Treemap en Java est un arbre rouge-noir. Cependant, chaque nœud se compose d'une clé et d'une valeur correspondante (paire de clés / valeur) au lieu d'une simple clé. Chaque paire de touches / valeur serait un élément d'une structure en forme de tableau. Cet article explique comment utiliser un Treemap en Java, en commençant par un arbre de recherche binaire, suivi de l'arbre rouge-noir, puis du Java Treemap.

Contenu de l'article

• Arbre de recherche binaire
• Arbre noir
• Paies de clé / valeur pour Java Treemap
• Construction de Java Treemap
• Méthodes Java Treemap
• Conclusion

Arbre de recherche binaire

Ce qui suit est un exemple d'arbre de recherche binaire:

Chaque nœud a une clé. La clé (valeur) pour le nœud racine est 8. L'enfant gauche est 3 et l'enfant droit est 10 (10> = 3). On peut voir que pour tout nœud qui a deux enfants, l'enfant droit est supérieur ou égal à l'enfant gauche. De plus, la moitié droite de l'arbre a des valeurs supérieures à celles de la moitié gauche de l'arbre pour chaque niveau.

Toutes les valeurs de l'arbre ci-dessus peuvent être placées dans un tableau, comme suit:

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

Notez que le tableau (arbre) commence à 8; descend à 3, puis monte au-delà de 8 à 10; descend à 1, atteint 6, puis a des nuages, jusqu'à 14 ans; descend à 4; s'élève à 7; Nils encore; puis 13 et le dernier nil.

8 est la première valeur à l'index 0. C'est le nœud racine (parent racine). Ce n'est pas nécessairement la plus grande valeur parmi toutes les valeurs. Son premier enfant (3) est à l'indice 1, dont l'indice est égal à 2 (0) + 1, où 0 est l'index du parent. Son deuxième enfant (10) est à l'indice 2, qui est égal à 2 (0) + 2, où 0 est l'index du parent.

3 est à l'index 1. C'est un parent. Son premier enfant (1) est à l'indice 3, qui est égal à 2 (1) + 1, où 1 est l'indice du parent. Son deuxième enfant (6) est à l'indice 4, qui est égal à 2 (1) + 2, où 1 est l'indice du parent.

6 est à l'index 4. C'est un parent. Son premier enfant (4) est à l'indice 9, qui est égal à 2 (4) + 1, où 4 est l'indice du parent. Son deuxième enfant (7) est à l'indice 10, qui est égal à 2 (4) + 2, où 4 est l'indice du parent.

10 est à l'index 3. C'est un parent. Il n'a pas d'enfant premier (à gauche), qui était censé être à l'indice 7, qui est égal à 2 (3) + 1, où 3 est l'indice du parent. Son deuxième enfant (14) est à l'indice 8, qui est égal à 2 (3) + 2, où 3 est l'indice du parent.

14 est à l'index 8. C'est un parent. Son premier enfant (13) est à l'indice 17, qui est égal à 2 (8) + 1, où 8 est l'indice du parent. Il n'a pas d'enfant droit (deuxième), qui était censé être à l'indice 18, qui est égal à 2 (8) + 2, où 8 est l'indice du parent.

En général, alors que le comptage des index commence à partir de 0. Que je représente l'indice d'un parent du tableau; Et donc, le (premier) enfant gauche d'un parent à l'index I, est à l'index 2i + 1; et son (deuxième) enfant droit, est à l'index 2i + 2. Certaines cellules du réseau peuvent être vides; Ils ne doivent pas avoir de valeurs.

Arbre noir

Un arbre rouge-noir est un arbre de recherche binaire, qui est équilibré. Ce qui suit est un arbre rouge-noir déjà équilibré:

Un arbre équilibré est un arbre à une courte hauteur. Les positions de nœud sont modifiées et marquées de couleurs rouges et bleues pour avoir la hauteur de l'arbre la plus courte possible dans son développement.

En utilisant les formules, 2i + 1 et 2i + 2, les valeurs peuvent être placées dans une structure en forme de tableau comme suit:

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

Notez que le tableau commence à 13, descend à 8 puis atteint 17. Il descend alors au-delà de 8 à 1 puis monte à 11, puis 15, puis 25; à partir de laquelle il y a un nil, puis il descend à 6. Nils suivent avant 22 et 27.

Le tableau d'un arbre équilibré, comme l'arbre rouge-noir ci-dessus, a moins de Nils que son arbre de recherche binaire correspondant qui n'est pas équilibré. La longueur du tableau d'un arbre équilibré est plus courte que l'arbre correspondant qui n'est pas équilibré.

Un arbre rouge-noir est un arbre partiellement ordonné.

Paies de clé / valeur pour Java Treemap

L'arbre rouge-noir précédent n'a que des clés comme valeurs de nœud. Chaque clé entière peut recevoir une valeur de chaîne correspondante. La liste suivante a les mêmes clés avec les valeurs correspondantes:

13 / treize, 8 / huit, 17 / sept, 1 / un, 11 / onze, 15 / quinze, 25 / vingt-cinq, 6 / six, 22 / vingt-deux, 27 / vingt-sept

Ce sont des paires clés / valeur adaptées à un java treemap. Chaque clé sera mappée à sa valeur correspondante. Une paire de clés / valeur est appelée une entrée de carte en java. Pour le Java Treemap, la disposition des nœuds est faite par des clés (pas des valeurs des paires de clés / valeur). Chaque clé est mappée à sa valeur.

Construction de Java Treemap

En Java, Treemap est une classe dans le Java.user.* package, qui doit être importé. Cette classe compte quatre constructeurs, et deux constructeurs sont illustrés dans cet article.

Public Treemap ()

Cela construit un Treemap vide. Le segment de code suivant l'illustre:

Tramper TM = nouveau Treemap();
TM.put (13, "treize"); TM.put (8, "huit"); TM.put (17, "dix-sept"); TM.put (1, "un");
TM.put (11, "onze"); TM.put (15, "quinze"); TM.put (25, "vingt-cinq"); TM.put (6, "six");
TM.put (22, "vingt-deux"); TM.put (27, "vingt-sept");

La méthode put () comprend des paires de clés / valeur au Treemap. Après tout cela, le Treemap devient équilibré en interne.

Public Treemap (carte M)

Cette méthode de constructeur crée une carte à partir d'une autre carte déjà créée, comme dans le segment de code suivant:

Tramper TM = nouveau Treemap();
TM.put (13, "treize"); TM.put (8, "huit"); TM.put (17, "dix-sept"); TM.put (1, "un");
TM.put (11, "onze"); TM.put (15, "quinze"); TM.put (25, "vingt-cinq"); TM.put (6, "six");
TM.put (22, "vingt-deux"); TM.put (27, "vingt-sept");
Tramper TM1 = nouveau Treemap(TM);

TM1 est créé à partir de TM. Après tout cela, les deux Treemaps sont équilibrés en interne; avec le premier équilibré en premier. L'équilibrage se déroule car les clés incluent les paires.

Méthodes Java Treemap

Public v put (ke key, v valeur)

À strictement parler, la méthode put () n'ajoute pas de paire clé / valeur. Il associe une valeur particulière à une clé particulière. Si la clé existait déjà dans le Treemap avec une valeur différente, la valeur est remplacée par la nouvelle. Cette méthode renvoie l'ancienne valeur ou null s'il n'y avait pas de valeur ancienne. L'utilisation de cette méthode a été démontrée ci-dessus.

Public int size ()

Cette méthode renvoie le nombre de mappages de clés / valeur (paires) dans le Treemap. Le segment de code suivant montre comment l'utiliser:

int it = tm.taille();
Système.dehors.println (it);

La sortie est 10, indiquant qu'il y a 10 paires de touches / valeur dans cet objet Treemap.

Public v get (clé d'objet)

Cette méthode renvoie la valeur correspondant à l'argument, qui est la clé. Il renvoie null si la clé n'existe pas. Le code suivant l'illustre pour la paire de clés / valeur: 11 / "onze", et pour la clé, 40, qui n'existe pas:

String val = tm.obtenir (11); String str = tm.obtenir (40);
Système.dehors.print (val + ","); Système.dehors.print (str + "");
Système.dehors.println ();

La sortie est:

onze, null

Public Set Keyset ()

Cette méthode renvoie une vision des clés qui se trouvent dans le Treemap. Pour afficher les touches, l'itérateur doit être utilisé. Le segment de code suivant pour le Treemap précédent l'illustre:

Ensemble st = tm.keyset ();
Itérateur iter = st.iterator ();
tandis que (iter.Hasnext ())
Système.dehors.Imprimer (iter.suivant () + ",");

Système.dehors.println ();

La sortie est:

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

La liste de retour est complètement triée (ascendant), bien que le Treemap ait un tri interne partiel.

Valeurs de collecte publique ()

Cela renvoie la carte de collection (liste) de toutes les valeurs du Treemap, sans les clés. Pour afficher les valeurs, l'itérateur doit être utilisé. Le segment de code suivant pour le Treemap précédent l'illustre:

Collection col = tm.valeurs();
Itérateur iter = col.iterator ();
tandis que (iter.Hasnext ())
Système.dehors.Imprimer (iter.suivant () + ",");

Système.dehors.println ();

La sortie est:

un, six, huit, onze, treize, quinze, dix-sept, vingt-deux, vingt-cinq, vingt-sept ans,

Les valeurs ont été affichées en fonction de leurs clés triées complètes (ascendant), bien que le Treemap ait un tri partiel en interne.

Ensemble public entryset ()

Cela renvoie un ensemble de paires de clés / valeur. Pour afficher les touches et leurs valeurs correspondantes, l'itérateur doit être utilisé. Le segment de code suivant pour le Treemap ci-dessus l'illustre:

Ensemble> paires = TM.entrySet ();
Itérateur> iter = paires.iterator ();
tandis que (iter.Hasnext ())
Carte.Entrée Etry = iter.suivant();
int dans = etry.Obtenir la clé(); String str = etry.getValue ();
Système.dehors.println (dans + "=>" + str);

La sortie est:

1 => un
6 => six
8 => huit
11 => onze
13 => treize
15 => quinze
17 => dix-sept
22 => vingt-deux
25 => vingt-cinq
27 => vingt-sept

Les paires ont été affichées en fonction de leurs clés triées complètes (ascendant), bien que le Treemap ait un tri partiel en interne.

Conclusion

En Java, un Treemap est un arbre rouge-noir, qui est un arbre de recherche binaire auto-équilibré. Les méthodes couramment utilisées et la construction Java Treemap ont été discutées dans cet article. Nous espérons que vous avez trouvé ces informations utiles. Découvrez les autres articles sur les conseils pour plus de conseils et de tutoriels.