O que é um treemap em java?

O valor de um nó em uma árvore é chamado de chave. Uma árvore binária é uma árvore, onde cada nó não tem mais de dois filhos. Uma árvore de busca binária (BST) é uma árvore, onde para cada nó, a criança certa é maior ou igual à criança esquerda. Isso leva à metade direita da árvore com valores geralmente maiores que os da metade esquerda em cada nível. Isso significa que uma árvore de pesquisa binária é parcialmente classificada (um tipo de classificação incompleta). Um BST pode ser mantido em uma estrutura semelhante a uma matriz, com o nó raiz sendo o primeiro valor.

Uma árvore binária pode ser transformada em diferentes árvores de auto-balanceamento com diferentes conjuntos de condições adicionais, como a árvore AVL e a árvore vermelha-preta.

O Treemap em Java é uma árvore vermelha-preta. No entanto, cada nó consiste em um valor de chave e correspondente (par de chaves/valores) em vez de apenas uma chave. Cada par de chave/valor seria um elemento em uma estrutura semelhante a uma matriz. Este artigo explica como usar um Treemap em Java, começando com uma árvore de busca binária, seguida pela árvore vermelha-preta e depois o Java Treemap.

Conteúdo do artigo

• Árvore de pesquisa binária
• Árvore-vermelha-preta
• Pares de chave/valor para Java Treemap
• Construção Java Treemap
• Métodos Java Treemap
• Conclusão

Árvore de pesquisa binária

A seguir, é apresentado um exemplo de uma árvore de pesquisa binária:

Cada nó tem uma chave. A chave (valor) para o nó raiz é 8. A criança esquerda é 3 e a criança direita é 10 (10> = 3). Pode -se observar que, para qualquer nó que tenha dois filhos, a criança certa é maior ou igual à criança esquerda. Além disso, a metade direita da árvore tem valores maiores que os da metade esquerda da árvore para cada nível.

Todos os valores da árvore acima podem ser colocados em uma matriz, como segue:

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

Observe que a matriz (árvore) começa às 8; desce para 3, depois sobe para além de 8 às 10; desce para 1, sobe para 6 e depois tem nilos até 14; desce para 4; sobe para 7; Nils novamente; então 13 e o último nulo.

8 é o primeiro valor no índice 0. É o nó raiz (pai raiz). Não é necessariamente o maior valor entre todos os valores. Seu primeiro filho (3) está no índice 1, cujo índice é igual a 2 (0) + 1, onde 0 é o índice do pai. Seu segundo filho (10) está no índice 2, que é igual a 2 (0) + 2, onde 0 é o índice do pai.

3 está no índice 1. É um pai. Seu primeiro filho (1) está no índice 3, que é igual a 2 (1) + 1, onde 1 é o índice do pai. Seu segundo filho (6) está no índice 4, que é igual a 2 (1) + 2, onde 1 é o índice do pai.

6 está no índice 4. É um pai. Seu primeiro filho (4) está no índice 9, que é igual a 2 (4) + 1, onde 4 é o índice do pai. Seu segundo filho (7) está no índice 10, que é igual a 2 (4) + 2, onde 4 é o índice do pai.

10 está no índice 3. É um pai. Não tem o primeiro filho (à esquerda), que deveria estar no índice 7, que é igual a 2 (3) + 1, onde 3 é o índice do pai. Seu segundo filho (14) está no índice 8, que é igual a 2 (3) + 2, onde 3 é o índice do pai.

14 está no índice 8. É um pai. Seu primeiro filho (13) está no índice 17, que é igual a 2 (8) + 1, onde 8 é o índice do pai. Não tem uma criança certa (segunda), que deveria estar no índice 18, que é igual a 2 (8) + 2, onde 8 é o índice do pai.

Em geral, quando a contagem de índice começa de 0. Deixe eu representar o índice de um pai da matriz; E assim, o filho da esquerda (primeiro) de um pai no índice I está no índice 2i + 1; e sua criança certa (segunda) está no índice 2i + 2. Algumas células na matriz podem estar vazias; Eles não devem ter valores.

Árvore-vermelha-preta

Uma árvore-vermelha é uma árvore de busca binária, que é equilibrada. A seguir, é uma árvore vermelha-preta já equilibrada:

Uma árvore equilibrada é uma árvore com uma altura curta. As posições do nó são alteradas e marcadas com cores vermelhas e azuis para ter a altura mais curta possível em seu desenvolvimento.

Usando as fórmulas, 2i + 1 e 2i + 2, os valores podem ser colocados em uma estrutura semelhante a uma matriz da seguinte forma:

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

Observe que a matriz começa aos 13 anos, desce para 8 e depois sobe para 17. Então desce além de 8 a 1 e depois sobe para 11, depois 15, depois 25; do qual há um nulo e depois desce para 6. Nils seguem antes de 22 e 27.

A matriz de uma árvore equilibrada, como a árvore vermelha-preta acima, tem menos nilos do que sua árvore de busca binária correspondente que não é equilibrada. O comprimento da matriz de uma árvore equilibrada é mais curta que a árvore correspondente que não é equilibrada.

Uma árvore-vermelha é uma árvore parcialmente ordenada.

Pares de chave/valor para Java Treemap

A árvore preta anterior tem apenas chaves como valores de nó. Cada chave inteira pode receber um valor de string correspondente. A lista a seguir possui as mesmas chaves com os valores correspondentes:

13/treze, 8/oito, 17/dezessete, 1/um, 11/onze, 15/quinze, 25/vinte e cinco, 6/seis, 22/vinte e dois, 27/vinte e sete

Estes são pares -chave/valor adequados para um Java Treemap. Cada chave será mapeada para o seu valor correspondente. Um par de chave/valor é chamado de entrada de mapa em java. Para o Java Treemap, o arranjo dos nós é feito por chaves (não valores dos pares de chave/valor). Cada chave é mapeada para o seu valor.

Construção Java Treemap

Em Java, Treemap é uma aula no Java.util.* pacote, que deve ser importado. Esta classe tem quatro construtores e dois construtores são ilustrados neste artigo.

TreeMap público ()

Isso constrói um Treemap vazio. O seguinte segmento de código ilustra o seguinte:

Treemap tm = novo Treemap();
tm.put (13, "treze"); tm.put (8, "oito"); tm.put (17, "dezessete"); tm.put (1, "um");
tm.put (11, "onze"); tm.put (15, "quinze"); tm.put (25, "vinte e cinco"); tm.put (6, "seis");
tm.put (22, "vinte e dois"); tm.put (27, "vinte e sete");

O método put () inclui pares de chave/valor para o Treemap. Depois de tudo isso, o Treemap fica equilibrado internamente.

TreeMap público (mapa m)

Este método construtor cria um mapa de outro mapa já criado, como no seguinte segmento de código:

Treemap tm = novo Treemap();
tm.put (13, "treze"); tm.put (8, "oito"); tm.put (17, "dezessete"); tm.put (1, "um");
tm.put (11, "onze"); tm.put (15, "quinze"); tm.put (25, "vinte e cinco"); tm.put (6, "seis");
tm.put (22, "vinte e dois"); tm.put (27, "vinte e sete");
Treemap tm1 = novo Treemap(tm);

TM1 é criado a partir da TM. Depois de tudo isso, ambos os Treemaps equilibrados internamente; com o primeiro equilibrado primeiro. O equilíbrio ocorre enquanto as chaves incluem pares.

Métodos Java Treemap

Public V put (K -Key, V Valor)

Estritamente falando, o método put () não adiciona um par de chaves/valor. Associa um valor particular a uma chave específica. Se a chave já existia no Treemap com um valor diferente, o valor é substituído pelo novo. Este método retorna o valor antigo ou nulo se não houvesse valor antigo. O uso deste método foi demonstrado acima.

Public int size ()

Este método retorna o número de mapeamentos de chave/valor (pares) no Treemap. O segmento de código a seguir mostra como usá -lo:

int it = tm.tamanho();
Sistema.fora.println (it);

A saída é 10, indicando que existem 10 pares de chave/valor neste objeto Treemap.

Public V Get (chave do objeto)

Este método retorna o valor correspondente ao argumento, que é a chave. Ele retorna nulo se a chave não existir. O código a seguir ilustra isso para o par de chaves/valor: 11/"Eleven", e para a chave, 40, que não existe:

String val = tm.obtenha (11); String str = tm.obtenha (40);
Sistema.fora.impressão (val + ","); Sistema.fora.impressão (str + "");
Sistema.fora.println ();

A saída é:

onze, nulo

Public Set Keyset ()

Este método retorna uma vista definitiva das chaves que estão no Treemap. Para exibir as chaves, o iterador deve ser usado. O segmento de código a seguir para o TreeMap anterior ilustra o seguinte:

Definir st = tm.conjunto de chaves();
Iterador iter = st.iterator ();
enquanto (iter.hasNext ())
Sistema.fora.impressão (iter.próximo () + ",");

Sistema.fora.println ();

A saída é:

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

A lista de retorno está completamente classificada (ascendente), embora o Treemap tenha classificação interna parcial.

Valores de coleção pública ()

Isso retorna a coleta-visualização (lista) de todos os valores no Treemap, sem as chaves. Para exibir os valores, o iterador deve ser usado. O segmento de código a seguir para o TreeMap anterior ilustra o seguinte:

Coleção col = tm.valores ();
Iterador iter = col.iterator ();
enquanto (iter.hasNext ())
Sistema.fora.impressão (iter.próximo () + ",");

Sistema.fora.println ();

A saída é:

um, seis, oito, onze, treze, quinze, dezessete, vinte e dois, vinte e cinco, vinte e sete,

Os valores foram exibidos com base em suas teclas de classificação completas (ascendentes), embora o Treemap tenha classificação parcial internamente.

Conjunto público Entryset ()

Isso retorna um conjunto de pares de chave/valor. Para exibir as chaves e seus valores correspondentes, o iterador deve ser usado. O seguinte segmento de código para o Treemap acima ilustra o seguinte:

Definir> pares = tm.entrada de entrada ();
Iterador> iter = pares.iterator ();
enquanto (iter.hasNext ())
Mapa.Entrada eTry = iter.próximo();
int in = ety.getKey (); String str = eTry.Obter valor();
Sistema.fora.println (in + "=>" + str);

A saída é:

1 => um
6 => seis
8 => oito
11 => onze
13 => Treze
15 => quinze
17 => dezessete
22 => vinte e dois
25 => vinte e cinco
27 => vinte e sete

Os pares foram exibidos com base em suas teclas de classificação completas (ascendendo), embora o Treemap tenha classificação parcial internamente.

Conclusão

Em Java, um Treemap é uma árvore vermelha-preta, que é uma árvore de busca binária auto-equilibrada. Os métodos comumente usados ​​e a construção Java Treemap foram discutidos neste artigo. Esperamos que você tenha achado essas informações úteis. Confira os outros artigos de dica do Linux para obter mais dicas e tutoriais.