• Árvore Patrícia

  • Entrada:

  • HUB

  • 1/1

Informações da Estrutura
Estrutura de Dados

EstruturaPatricia

{

  Palavra : String;

  Direita : EstruturaPatricia;

  Abaixo : EstruturaPatricia;

  PalavraFinal : booleano;

}

Descrição
"A árvore Patricia (uma sílaba de "Practical Algorithm To Retrieve Information Coded In Alphanumeric") também conhecida como Árvore Radix, é uma uma árvore de busca para dicionário de palavras baseada na árvore Trie, porém em vez de armazenar uma letra em cada nó, armazena-se a maior quantidade possível de letras juntas (chamadas de sílabas). Toda vez que é adicionada uma nova palavra ocorre uma fragmentação de outras palavras já inseridas, reaproveitando os caracteres inicialmente similiares.


Mais informações
Implementação: Realizada por meio de registros (em C, struct)

Regras: Cada nó aponta somente para o primeiro filho de uma lista de silabas, e para os outros filhos do seu mesmo pai.

Aplicação: Dicionário de interpretadores, compiladores, geometria computacional, implementação de conjuntos, entre outros.

Requisitos para aplicação: O armazenamento não deve ser realizado em arquivo (problemas de fragmentação).

Em relação a outras formas de implementação de Árvore
  • Vantagem: Teoricamente, a árvore possui um número ilimitado de filhos, e em relação a Trie economiza memória.
  • Desvantagem: Implementação mais complexa, causa fragmentação quando implementada em arquivo.
FUNÇÃO
Insere(No,Palavra)

i,compPalavra,compPalavraNo : inteiro;

i := 0;

compPalavra := Comprimento(Palavra);

compPalavraNo := Comprimento(No.Palavra);

 

Enquanto i < compPalavraNo e i < compPalavra e No.Palavra[i] == Palavra[i] faça

i := i + 1;

 

Se i < compPalavraNo e i < compPalavra então

INICIO

Se i == 0 então

INICIO

Se Palavra[0] > No.Palavra[0] então

INICIO

Se No.Direita != nulo então

Insere(No.Direita,Palavra);

Senão

INICIO

No.Direita := alocar();

No.Direita.PalavraFinal := Verdadeiro;

No.Direita.Palavra := Palavra;

No.Direita.Direita := nulo;

No.Direita.Abaixo := nulo;

FIM

FIM

Senão

INICIO

novo : EstruturaPatricia;

novo := alocar();

novo.Direita := No;

novo.Abaixo := nulo;

novo.Palavra := Palavra;

novo.PalavraFinal := Verdadeiro;

No := novo;

FIM

FIM

Senão

INICIO

primeira_parte : String;

segunda_parte : String;

primeira_parte := SubPalavra(No.Palavra,0,i);

segunda_parte := SubPalavra(No.Palavra,i,compPalavraNo);

 

novo: EstruturaPatricia;

novo := alocar();

novo.Palavra := segunda_parte;

novo.Abaixo := No.Abaixo;

novo.Direita := nulo

 

No.Abaixo := novo;

No.Palavra := primeira_parte;

 

Se No.PalavraFinal == Verdadeiro então

INICIO

No.PalavraFinal := Falso;

novo.PalavraFinal := Verdadeiro;

FIM

 

Insere(novo,SubPalavra(Palavra,i,compPalavra));

FIM

Retonar;

FIM

 

Se compPalavra == compPalavraNo então

No.PalavraFinal := Verdadeiro;

Senão

INICIO

Se i == compPalavraNo então

INICIO

Se No.Abaixo != nulo então

Insere(No.Abaixo,SubPalavra(Palavra,i,compPalavra));

Senão

INICIO

No.Abaixo := alocar();

No.Abaixo.PalavraFinal := Verdadeiro;

No.Abaixo.Palavra := SubPalavra(Palavra,i,compPalavra);

No.Abaixo.Direita := nulo;

No.Abaixo.Abaixo := nulo;

FIM

FIM

Senão

INICIO

novo : EstruturaPatricia;

novo := alocar();

novo.Abaixo := No.Abaixo;

No.Abaixo := novo;

No.Direita := nulo;

novo.Palavra := SubPalavra(No.Palavra,i,compPalavraNo);

No.Palavra := SubPalavra(No.Palavra,0,i);

No.PalavraFinal := Verdadeiro;

novo.PalavraFinal := Verdadeiro;

FIM

FIM

FUNÇÃO
SubPalavra(Palavra,inicio,fim)
RETORNA
Parte de uma Palavra

saida : String tamanho fim - inicio;

j : inteiro;

j := inicio;

Para i:inteiro de inicio até fim passo 1 faça

INICIO

saida[j-inicio] := Palavra[i];

j := j + 1;

FIM

Retornar saida;

FUNÇÃO
Comprimento(Palavra)
RETORNA
Total de letras possui a Palavra

i : inteiro;

i := 0;

Enquanto Palavra[i] == nulo ou Palavra[i]=='' faça

i := i + 1;

Retornar i;

FUNÇÃO
Remove(No,Palavra,Anterior,UltimoPai)

Se Palavra[0] == No.Info[0] então

INICIO

Se Comprimento(Palavra) > Comprimento(No.Info) então

INICIO

Se IniciaCom(Palavra,No.Info) então

INICIO

Palavra := SubPalavra(Palavra,0,Comprimento(No.Info));

Se No.Abaixo != nulo então

Remove(No.Abaixo,Palavra,No,No);

FIM

FIM

Senão se Palavra == No.Info e No.PalavraFinal então

INICIO

Se Anterior == nulo então

INICIO

Se No.Abaixo == nulo então

No := No.Direita;

Senão

INICIO

Se No.Abaixo.Direita != nulo então

No.FinalPalavraFinal := Falso;

Senão

INICIO

No.Info := Concatenar(No.Info,No.Abaixo.Info);

No.Abaixo := No.Abaixo.Abaixo;

FIM

FIM

FIM

Senão se Anterior.Abaixo == No então

INICIO

Se No.Abaixo == nulo então

INICIO

Anterior.Abaixo := No.Direita;

Se No.Direita != nulo e No.Direita.Direita == nulo

INICIO

Anterior.Info := Concatenar(Anterior.Info,No.Direita.Info);

Anterior.PalavraFinal := Verdadeiro;

No.Abaixo := nulo;

FIM

FIM

Senão

INICIO

Se No.Abaixo.Direita != nulo então

No.PalavraFinal := Falso;

Senão se No.Abaixo != nulo e No.Abaixo.Direita == nulo então

INICIO

No.Info := Concatenar(No.Info,No.Abaixo.Info);

No.Abaixo := No.Abaixo.Abaixo;

FIM

FIM

FIM

Senão se Anterior.Direita == No então

INICIO

Se No.Abaixo == nulo então

INICIO

Se UltimoPai.Abaixo == Anterior e Anterior.Direita == nulo então

INICIO

Anterior.PalavraFinal := UltimoPai.PalavraFinal || Anterior.PalavraFinal;

ultimoPai.info := Concatenar(ultimoPai.info,ultimoRelevante.info);

ultimoPai.abaixo := nulo;

FIM

FIM

Senão

INICIO

Se No.Abaixo.Direita == nulo então

INICIO

No.Info := Concatenar(No.Info,No.Abaixo.Info);

No.Abaixo := No.Abaixo.Abaixo;

FIM

Senão

No.PalavraFinal := Falso;

FIM

FIM

FIM

FIM

Senão se No.Direita != nulo e Palavra[0] > No.Info[0] então

Remove(No.Direita,Palavra,No,UltimoPai);

FUNÇÃO
IniciaCom(PalavraA,PalavraB)
RETORNA
Se a PalavraA inicia com PalavraB

tamanhoA,tamanhoB : inteiro;

tamanhoA := Comprimento(PalavraA);

tamanhoB := Comprimento(PalavraB);

 

Se tamanhoB > tamanhoA então

Retornar Falso;

Senão

INICIO

i : inteiro;

i := 0;

Enquanto i < tamanhoB faça

INICIO

Se PalavraA[i] != PalavraB[i] então

Retornar Falso;

i := i + 1;

FIM

FIM

Retornar Verdadeiro;

FUNÇÃO
Concatenar(PalavraA,PalavraB)
RETORNA
Retornar a concatenação das palavras

tamanhoA,tamanhoB : inteiro;

tamanhoA := Comprimento(PalavraA);

tamanhoB := Comprimento(PalavraB);

j : inteiro;

j := 0;

saida : String tamanho [tamanhoA + tamanhoB]

Para i:inteiro de 0 até PalavraA[i] == nulo ou PalavraA[i]=='' passo 1 faça

INICIO

saida[j] := PalavraA[i];

j := j + 1;

FIM

Para i:inteiro de 0 até PalavraA[i] == nulo ou PalavraA[i]=='' passo 1 faça

INICIO

saida[j] := PalavraB[i]

j := j + 1;

FIM

Retornar saida;

FUNÇÃO
SubPalavra(Palavra,inicio,fim)
RETORNA
Parte de uma Palavra

saida : String tamanho fim - inicio;

j : inteiro;

j := inicio;

Para i:inteiro de inicio até fim passo 1 faça

INICIO

saida[j-inicio] := Palavra[i];

j := j + 1;

FIM

Retornar saida;

FUNÇÃO
Comprimento(Palavra)
RETORNA
Total de letras possui a Palavra

i : inteiro;

i := 0;

Enquanto Palavra[i] == nulo ou Palavra[i]=='' faça

i := i + 1;

Retornar i;

FUNÇÃO
Busca(No,INFO)
RETORNA
Se o valor está na Árvore

compBusca,compBuscaNo : inteiro;

compBusca := Comprimento(INFO);

compBuscaNo := Comprimento(No.Palavra);

 

Se compBusca < compBuscaNo então

INICIO

Se INFO[0] > No.Palavra[0] então

INICIO

Se No.Direita != nulo então

Retornar Busca(No.Direita,INFO);

Senão

Retornar Falso;

FIM

FIM

 

b : vetor de caracteres;

b := SubPalavra(busca,0,compBuscaNo);

 

Se b[0] > No.Palavra[0] então

INICIO

Se No.Direita != nulo então

Retornar Busca(No.Direita,busca);

Senão

Retornar Falso;

FIM

 

Se Igual(b,No.Palavra) então

INICIO

Se compBusca == compBuscaNo então

Retornar No.PalavraFinal;

Senão Se No.Abaixo != nulo então

Retornar Busca(No.Abaixo,SubPalavra(INFO,compBuscaNo,compBusca));

FIM

 

FUNÇÃO
SubPalavra(Palavra,inicio,fim)
RETORNA
Parte de uma Palavra

saida : String tamanho fim - inicio;

j : inteiro;

j := inicio;

Para i:inteiro de inicio até fim passo 1 faça

INICIO

saida[j-inicio] := Palavra[i];

j := j + 1;

FIM

Retornar saida;

FUNÇÃO
Comprimento(Palavra)
RETORNA
Total de letras possui a Palavra

i : inteiro;

i := 0;

Enquanto Palavra[i] == nulo ou Palavra[i]=='' faça

i := i + 1;

Retornar i;

Última animação

Nenhuma animação disponível para revisar!

Executando animação ...

Aguarde encerrar !

Última animação que foi executada:

# Descrição
Entradas Programadas

Configurações

Entradas

Limpar entrada ao final da animação

Chance de gerar número negativo na entrada aleatória:

50%

Estrutura

Ocultar Ponteiros Nulos

Impedir inserção de valores repetidos

Mostrar Descritores

Cor do componente primário

Cor do componente secundário

Código

Usar delimitador em chaves

Contar linhas brancas

Configurações serão salvas para este navegador
Histórico
    • #
    • INFO
    • Vazio
Principal
Menu das Estruturas

  • Pseudo-código

  • Informações da Estrutura

  • Entradas Programadas

  • Rever Passos

  • Histórico

Árvore Patrícia

  • Vazio
Logo

Estruturas

Listas

Sem ordenação

Simples

Dupla

Com ordenação

Simples

Dupla

Estática

Cruzada

Filas

Estáticas

Simples

Circular

Dinâmicas

Normal

Com Prioridade

Circular

Pilhas

Estáticas

Simples

Múltipla

Dinâmicas

Simples

Hashing

Sem Tratamento

Simples

Com Tratamento

Listas Encadeadas

Área de Overflow

Árvores

Balanceadas

AVL

Rubro-Negra

B

Não Balanceadas

Binária

Trie

Patricia
Histórico

Lista Ordenada Simples

Lista Ordenada Estática

Lista Ordenada Dupla

Lista Sem Ordenação Simples

Lista Sem Ordeneção Dupla

Lista Cruzada

Fila Estática

Fila Estática Circular

Fila com Prioridade

Fila Dinâmica

Fila Circular

Pilha Estática

Pilha Múltipla

Pilha Dinâmica

Hash sem Tratamento

Hash com Tratamento

Hash com Overflow

Árvore AVL

Árvore B

Árvore RubroNegra

Árvore Binária

Árvore Trie

Árvore Patricia

Estrutura não encontrada