Curso Livre de Estruturas de Dados/Árvores de Busca

Árvores de Busca (Estrutura de Dados) editar

Exemplo gráfico de uma árvore binária de busca.

Árvores são estruturas de dados que organizam seus elementos de forma hierárquica. Uma árvore possui um conjunto finito de elementos chamados de nós ou nodos. Entre as características deste tipo de estrutura de dados está o armazenamento não linear, conforme afirma Ascencio & De Araújo (2010, p. 278), pois seus elementos não são inseridos na memória de maneira sequencial^[1]. Além disso, ainda segundo Ascencio & De Araújo (2010, p. 278), nem todos os elementos possuem encadeamento^[1].

O primeiro nó de uma árvore fica localizado no topo e é chamado de raiz da árvore, os demais nós estão dispostos hierarquicamente abaixo da raiz e são chamados de filhos ou ramos. Cada ramo pode estar ligado a outros elementos que podem possuir outros ramos, criando assim a estrutura hierárquica da árvore. O nó filho ou ramo que não possuir outros ramos é conhecido como folha. Existem diversos tipos de Árvores de Busca que, de diferentes formas, garante uma eficiente inserção e remoção dos elementos.

Tipos de Árvores editar

Árvores Binárias
Árvores N-árias
Árvores AVL
Árvores Rubro-Negras
Árvores B
Árvores Heap
Árvores Digitais (Tries)

Árvore binária editar

A árvore binária se baseia na ideia de nós, no qual de modo padrão, os valores que são inferiores ao nó raiz ficam ao lado esquerdo, enquanto os valores superiores ao nó raiz ficam ao lado direito, com isso, sabe-se que os nós em sua estrutura lógica para a programação contam com um ponteiro para cada direção (direita e esquerda), como também deve conter o dado a ser armazenado (chave).

estrutura no_arvore
{
    chave valor
    no_arvore *esquerdo
    no_arvore *direito
}

Percursos editar

Exemplo gráfico de uma árvore binária.

Nas árvores binárias existem quatro possibilidades de percorrer a árvore, sendo estes:^[2]

Pré-ordem.
Em ordem (simétrica).
Pós-ordem.
Em nível

Pré-ordem editar

Nesta categoria de percurso é visitado primeiramente a raiz, para assim poder seguir na subárvore esquerda e por último percorrer a subárvore direita.^[2] Onde ao usar a imagem de exemplo da árvore binária, pode-se obter o seguinte resultado: 10, 5, 7, 6, 8, 50, 25.

funcao pre_ordem(arvore atual)
    se(atual!=vazio)
    {
        imprima(atual)
        pre_ordem(atual->esquerda)
        pre_ordem(atual->direita)
    }
    senao
        retorne

Em ordem (simétrica) editar

No percurso simétrico, é percorrido a subárvore esquerda, seguindo para a raiz, após isso percorre a subàrvore direita.^[2] Este percurso basicamente ordena os valores em ordem crescente.

Ao percorrer no exemplo de árvore proporcionado da imagem anterior, pode-se obter como resultado: 5, 6, 7, 8, 10, 25, 50.

funcao ordem(arvore atual)
    se(atual!=vazio)
    {
        ordem(atual->esquerda)
        imprima(atual)
        ordem(atual->direita)
    }
    senao
        retorne

Pós-ordem editar

No percurso de pós-ordem, é percorrido a subárvore esquerda, com isso segue para a subárvore direita e por último a raiz.^[2] E usando a mesma imagem de todos os percursos anteriores, pode-se obter o seguinte resultado de percurso: 6, 8, 7, 5, 25, 50, 10.

funcao pos_ordem(arvore atual)
    se(atual!=vazio)
    {
        pos_ordem(atual->esquerda)
        pos_ordem(atual->direita)
        imprima(atual)
    }
    senao
        retorne

Em-nível editar

Esse percurso é feito com o intuito de realizar operações sobre todos os elementos de cada nível da árvore, da esquerda para a direita. Para que seja possível acessar todos os elementos de um determinado nível de uma árvore binária, utiliza-se de outra estrutura de dado, sendo essa a fila. O pseudo-algoritmo que representa o processo do percurso em nível pode ser descrito do seguinte modo:

inicia em_nivel

    instanciar fila;

    fila = no_raiz

    inicia_enquanto (tamnho_da_fila != 0)
        elemento_retirado = retira_elemento_da_fila;
    
        realizar_processo_desejado;
    
        se (filho_esquerda != null)
            fila = filho_esquerda;
        if (filho_direita != null)
            fila = filho_direita;
    finaliza_enquanto
    
finaliza em_nivel;

Busca editar

O processo de busca utiliza-se a propriedade da relação de valores entre os nós, navega-se pelos nós comparando se o valor buscado é menor, igual ou maior ao valor do nó atual, e assim orientando uma navegação à esquerda, um retorno de valor encontrado ou uma navegação à esquerda, respectivamente, realizando esse processo até conseguir o retorno positivo ou terminar em uma folha vazia, realizando um retorno de valor não encontrado nesse caso.

Inserção editar

Para garantir a validade das regras de ordem entre os nós o método de inserção em árvores binárias de busca é restrito, onde ao se inserir um nó se realiza um procedimento similar ao de busca, navegando-se pelos nós para a direita ou esquerda com base na relação entre os valores do nó à ser inserido e o nó atual na busca, até encontrar uma folha disponível.

Árvore n-ária editar

Na teoria dos grafos, uma árvore n-ária (também conhecida como m-ária, k-ária ou arvore k-way) é uma árvore enraizada na qual cada nó não tem mais do que n filhos. Uma árvore binária é o caso especial em que n = 2, e uma árvore ternária é outro caso com n = 3 que limita seus filhos a três.

Representação de uma árvore n-ária com 3 níveis e m = 4

Tipos de árvores n-árias editar

Uma árvore n-ária completa é uma árvore onde dentro de cada nível cada nó possui 0 filhos ou n.
Uma árvore n-ária completa é uma arvore n-ária que é extremamente eficiente no espaço. Deve ser completamente preenchido em todos os níveis, exceto no ultimo nível. No entanto, se o último nível não estiver completo, todos os nós da árvore devem ser o “mais à esquerda possível”.
Uma árvore n-ária perfeita é uma árvore completa, onde todos os nós das folhas devem estar na mesma profundidade.

Propriedades das árvores n-árias editar

Para uma árvore n-ária com altura h, o limite superior para o número máximo de folhas é $m^{h}$ .
A altura h de uma árvore n-ária não inclui o nó raiz, com uma árvore contendo apenas um nó raiz com uma altura de 0.
A altura de uma árvore é igual à profundidade máxima D de qualquer nó na árvore.
O número total de nós n em uma árvore n-ária perfeita é $\sum _{i=0}^{h}m^{i}$ = ${\frac {m^{h+1}-1}{m-1}}$ enquanto a altura h é

${\frac {m^{h+1}-1}{m-1}}$ $\geq$ N $>$ ${\frac {m^{h}-1}{m-1}}$ .

$m^{h+1}\geq (m-1)\cdot N+1>m^{h}$

$h+1\geq \log _{m}\left((m-1)\cdot N+1\right)>h$

$h\geq \left\lceil \log _{m}((m-1)\cdot N+1)-1\right\rceil .$

Pela definição de Big-O, temos que a profundidade máxima é

$=h\geq \left\lceil \log _{m}((m-1)\cdot N+1)-1\right\rceil =O(\log _{m}n)=O(\log n/\log m)$

A altura máxima de uma árvore n-ária completa com n nodos é $\lfloor \log _{m}((m-1)\cdot n)\rfloor$ .
O número total de árvore n-árias possível com n nós é $C_{n}={\frac {1}{(m-1)n+1}}\cdot {\binom {m\cdot n}{n}}$ .

Métodos de travessia para árvores n-árias editar

Atravessar por uma árvore n-ária é muito semelhante à travessia de árvores binárias. A travessia de pré-ordenação vai para o pai, subárvore esquerda e a subárvore direita, e para atravessar por pós-ordenação passa pela subárvore da esquerda, subárvore da direita e nó pai. Para atravessar em ordem, uma vez que há mais de dois filhos por nó para n > 2, é preciso definir a noção de subávores à esquerda e direita. Um método comum para estabelecer subávores esquerda/direita é dividir a lista de nós filhos em dois grupos. Ao definir uma ordem sobre os filhos n de um nó, os primeiros $\{1,\dots ,\lfloor {\frac {m}{2}}\rfloor \}$ nós irão constituir a subárvore da esquerda e os $\{\lceil {\frac {m}{2}}\rceil ,\dots ,m\}$ nós constituirão a subárvore da direita.

Conversão de uma árvore n-ária em uma árvore binária editar

Usar uma matriz/arranjo para representar uma árvore n-ária é ineficiente, porque a maioria dos nódulos em aplicações práticas contêm menos de n filhos. Como resultado, este fato leva a uma matriz esparsa com grande espaço não utilizado na memória. Converter uma árvore n-ária arbitrária em uma árvore binária só aumentaria a altura da árvore por um fator constante e não afetaria a complexidade geral do pior dos casos. Em outras palavras, $O(\log _{m}n)\equiv O(\log _{2}n)$ visto que $\log _{2}m\cdot \log _{m}n={\frac {\log m}{\log 2}}\cdot {\frac {\log n}{\log m}}=\log _{2}n$ .

Primeiro, vinculamos todos os nós dos filhos imediatos de um determinado nó dos pais, para assim formar uma lista de links. Em seguida, mantemos o vínculo do pai com o primeiro (ou seja, o filho mais à esquerda) e removemos todos os outros links para o resto dos filhos. Repetimos esse processo para todos os filhos (caso possua) até que tenhamos processado todos os nós internos, e depois giramos a árvore em 45 graus no sentido horário. A árvore obtida é a árvore binária desejada obtida da árvore n-ária dada.

Métodos para armazenar árvores n-árias editar

Arranjos

Árvores n-árias também podem ser armazenadas em ordem de busca em largura como uma estrutura de dados implícita em arranjos, e caso a árvore seja uma árvore n-ária completa, este método não desperdiça espaço. Nesta disposição compacta, se um nó tem um índice i, seu c-ésiimo filho na distância {1,…,m} é encontrado no índice $m\cdot i+c$ , enquanto seu pai (se houver) é encontrado no índice ${\textstyle \left\lfloor {\frac {i-1}{m}}\right\rfloor }$ (presumindo que a raíz possua índice zero, ou seja, tratando-se de um arranjo com índice baseado em 0). Este método apresenta como vantagens um armazenamento mais compacto e melhor localidade de referência, particularmente durante uma travessia em pré-ordenada. A complexidade em espaço desde método é $O(m^{n})$ .

Baseado em ponteiros

Cada nó teria um arranjo para armazenar ponteiros para cada um dos seus $m$ filhos: Comparada à implementação baseada em arranjo, este método de implementação tem uma complexidade de espaço superior de $O(m\cdot n)$ .

Aplicação editar

Uma das aplicações de árvores n-árias é a criação de um dicionário para validação de cadeias de caracteres (strings) aceitáveis. Para isso, seja m igual ao número de alfabetos válidos (i.e., o número de letras do alfabeto em inglês) com a raíz da árvore representando o ponto de partida. Similarmente, cada um dos filhos pode possuir até m filhos, os quais representam o próximo possível caractere na string. Portanto, caracteres ao longo dos caminhos podem representar chaves válidas através da marcação do último caractere das chaves como um "nó terminal”. Nós terminais podem armazenar informação extra a ser associada a uma chave específica. Há formas parecidas de se construir um dicionário assim usando árvores B, Octrees e/ou tries (árvores de prefixo).

Árvore AVL editar

Esta árvore usa o conceito da árvore binária de busca, porém ela é altamente balanceada, buscando minimizar o número de operações realizadas para ser encontrado um determinado elemento. O conceito de balanceamento desta árvore se baseia onde as alturas das subárvores esquerda e direita de cada nó diferem no máximo por uma unidade.^[3]

A árvore AVL usufrui do conceito de fator de balanceamento, que pode ser definido como a operação h_E- h_D, sendo h_E e h_D as alturas das subárvores esquerda e direita do nó respectivamente. O fator de uma árvore AVL assume o valor de -1, 0 ou 1, no qual o balanceamento de uma folha é igual à zero e sendo necessário balancear quando seu fator for superior a 1 ou inferior a -1.^[4]

Na implementação de uma Árvore AVL, o balanceamento é feito de forma recursiva junto ao algoritmo de inserção de uma chave. Desta forma todas as subárvores tem seu fator de balanceamento verificado e rotações à direita ou à esquerda são realizadas para balancear caso necessário.

estrutura no_arvore
{
    chave valor
    no_arvore *esquerdo
    no_arvore *direito
    inteiro fator_balanceamento
}

Abaixo, a implementação de uma árvore AVL na linguagem C.

#include <stdio.h>
#include <stdlib.h>

typedef struct
{
	int dado;
}tData;

typedef struct tNode
{
	struct tNode *left;		// ponteiro para o filho esquerdo
	struct tNode *right;	// ponteiro para o filho direito
	tData *info; 			// chave armazenada no nó
	int alt; 				// altura da arvore
} tNode;

//compara dois inteiros e retorna o maior
int maior(int a ,int b)
{
	if (a>=b)
		return a;
	else	
		return b;
}

//retorna a altura a partir do nodo passado
int altura(tNode *root)
{
	tNode *aux=root;
	int a,b;
	if (aux == NULL)
		return 0;
	else 
	{
		a=altura(aux->left);
		b=altura(aux->right);
		return (1+maior(a,b));
	}
}

tNode* rotation_right(tNode *k2)
{
	tNode *k1;
	
	k1 = k2->left;
	k2->left = k1->right;
	k1->right = k2;

	k2->alt = altura(k2);
	k1->alt = altura(k1);

	return k1;
}

tNode* rotation_left(tNode *k2)
{
	tNode *k1;

	k1 = k2->right;
	k2->right = k1->left;
	k1->left = k2;

	k2->alt = altura(k2);
	k1->alt = altura(k1);

	return k1;
}

tNode* balanceAVL (tNode *root)
{
	int L,R;
	if(root == NULL)
		return root;
	else
	{
		root->right = balanceAVL(root->right);
		root->left = balanceAVL(root->left);
		L = altura(root->left);
		R = altura(root->right);
		
		if((modulo (L - R)) >= 2)
		{
			if(R > L) //Lado direito maior
				root = rotation_left(root);
			else //Lado esquerdo maior
				root = rotation_right(root);
		}
		return root;
	}
}

//insere um nodo em uma árvore binária de busca balanceada do tipo AVL
tNode* insertAVL (tNode *root, tData info)
{
	tNode *new;
	tData *d;
	
	//Verifica se a raiz é nula
	if (root == NULL)
	{
		new = (tNode*)malloc(sizeof(tNode));
		d = (tData*)malloc(sizeof(tData));

		if (new==NULL || d==NULL)
		{
			printf("Erro ao alocar!\n");
			return NULL;
		}
		else
		{
			new->info = d;
			new->info->dado = info.dado;
			new->alt = altura(new);
			new->left = NULL;
			new->right = NULL;
			return new;
		}
	}

	//inserção a esquerda
	else if (info.dado < root->info->dado)
	{
		root->left = insert(root->left,info);
		root->alt = altura(root);
		root = balanceAVL(root);
		return root;
	}
	//inserção a direita
	else
	{
		root->right = insert(root->right,info);
		root->alt = altura(root);
		root = balanceAVL(root);
		return root;
	}	
}

//Exemplo de inserção
int main()
{
	tData d;
	tNode *root=NULL;
	int i;

	for(i=1 ; i<=7 ; i++)
	{
		d.dado=i;
		root = insertAVL(root,d);
	}
	return 0;
}

Árvore Rubro-Negra editar

As árvores Rubro-Negras são árvores binárias de busca também conhecidas como Vermelho-Preto ou Red-Black Tress. Foram criadas por Rudolf Bayer com o nome “Árvores Binárias Simétricas” em 1972, 10 anos após a criação das árvores AVL. Apenas em 1978 ela adquiriu o nome de Árvore Rubro-Negra devido à um artigo escrito por Leonidas J. Guibas e Robert Sedgewick, em que as cores preta e vermelha foram escolhidas porquê eram as cores de caneta disponíveis enquanto desenhavam as árvores.^[5]

Esta árvore possui um bit extra para armazenar a cor de cada nó, que pode ser vermelho ou preto. Além do atributo de cor, cada nodo é composto pelos seguintes campos:

valor (dado do nodo)
filho esquerdo
filho direito
pai

A árvore Rubro-Negra possui as seguintes propriedades:

Para todo nodo, todos os caminhos até uma folha contém o mesmo número de nodos negros.
Se um nodo for rubro, então ambos os filhos são negros.
A raiz é negra.
Toda folha é negra. Folhas são somente os nodos vazios (ponteiros nulos).
Todo nodo ou é rubro ou é negro.

Essas propriedades garantem uma característica fundamental das árvores rubro-negras: o caminho mais longo da raiz até qualquer folha não excede o dobro do caminho mais curto da raiz até qualquer outra folha da árvore. Isso faz com que a árvore seja quase balanceada. Uma vez que as operações de inserção, remoção e valor requerem tempo no pior caso proporcional à altura da árvore, ao contrário das árvores de pesquisa binárias, essa restrição proporcional à altura permite que as árvores vermelhas e pretas sejam eficazes no pior caso.

Representação simples de uma Àrvore Rubro-Negra.

Uma árvore Rubro-Negra com n nodos internos tem uma altura máxima de 2log(n+1). Por ser uma árvore semi-balanceada, possui complexidade logarítmica em suas operações: O (log n).

Implementação da estrutura de uma árvore Rubro-Negra:

estrutura nodoRB {

info:tipo_info;
esq: *nodoRB;
dir: *nodoRB;
pai: *nodoRB;
cor: {rubro, negro};
};

Inserção em Árvore Rubro-Negra editar

O código de inserção da árvore Rubro-Negra é complicado, pois ele depende de operações de rotação.

A inserção substitui um nó sentinela (preto) por um novo nó interno vermelho x contendo o valor novo inserido. Este nó aponta, por sua vez, a dois nós sentinela (preto), à esquerda e à direita.

Há três casos a considerar quando x e pai[x] são vermelhos. Existe pai[pai[x]] pois pai[x] sendo vermelho não pode ser a raiz.

Caso 1: x tem um tio y vermelho.

Caso 2: x tem um tio y preto e x é filho direito.

Caso 3: x tem um tio y preto e x é filho esquerdo.

Durante uma operação de inserção, é possível ter, temporariamente, um link rubro inclinado para a direita ou dois links rubros incidindo no mesmo nó. Para corrigir isso, é feita a utilização de rotações.

Para a rotação esquerda (ou anti-horária) em torno de um nó h, o filho direito de h sobe e adota h como seu filho esquerdo. Então, continua-se tendo uma BST com os mesmos nós, mas raiz diferente.

O algoritmo de rotação (left-rotate e right-rotate) muda alguns ponteiros da árvore, preservando a propriedade de árvore binária de busca.

Node rotateLeft(Node h) {
            Node x = h.right;
            h.right = x.left;
            x.left = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + size(h.left) + size(h.right);
            return x;
         }

Para a rotação direita (ou horária) em torno de um nó h, o filho esquerdo dehsobe e adota h como seu filho direito. Então, continua-se tendo uma BST com os mesmos nós, mas raiz diferente:

Node rotateRight(Node h) {
            Node x = h.left;
            h.left = x.right;
            x.right = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + size(h.left) + size(h.right);
            return x;
         }

As operações de rotação são locais (só envolvem um nó e seus vizinhos). Depois de uma rotação, continuamos tendo uma BST com balanceamento negro perfeito, mas a operação pode ter criado um link rubro inclinado para a lado errado ou dois links rubros seguidos. ^[6]

O código abaixo mostra um exemplo de implementação, com destaque para o método de inserção:

public class RedBlackBST<Key extends Comparable<Key>, Value> {

   private Node root;
   
   private class Node               

   private boolean isRed(Node h)    

   private Node rotateLeft(Node h)  

   private Node rotateRight(Node h) 

   private void flipColors(Node h)  

   private int size()               

   public void put(Key key, Value val) { 
      root = put(root, key, val);
      root.color = BLACK;
   }

   private Node put(Node h, Key key, Value val) {
      if (h == null) 
         return new Node(key, val, 1, RED);

      int cmp = key.compareTo(h.key);
      if      (cmp < 0) h.left  = put(h.left, key, val);
      else if (cmp > 0) h.right = put(h.right, key, val);
      else              h.val   = val;

      if (isRed(h.right) && !isRed(h.left))      h = rotateLeft(h);
      if (isRed(h.left)  &&  isRed(h.left.left)) h = rotateRight(h);
      if (isRed(h.left)  &&  isRed(h.right))     flipColors(h);
      h.N = size(h.left) + size(h.right) + 1;
      return h;
   }
}

^[6]

Árvore Heap editar

A árvore heap é um tipo de árvore binária balanceada e justificada à esquerda, onde cada nó possui valor que o valor de seu pai. Essa estrutura foi proposta por J.W.J Williams, tendo como destaque sua utilização para a construção de filas com prioridades^[7].

Uma árvore binária se caracteriza justificada à esquerda quando possuir 2ⁿ nós de profundidade n ou possuir 2^k nós de profundidade k para todo k < n e todas as folhas no nível n estão mais à esquerda possível.

Para realizar inserções em uma árvore heap, segue-se a seguinte lógica:

Se o nível mais profundo da árvore não estiver preenchido, adiciona-se um novo nó à direita do nó mais à direita do nível mais profundo.

Se o nível mais profundo da árvore estiver completo, inicia-se um novo nível na árvore adicionando o novo nó à esquerda do nó mais à esquerda da árvore.

Ao realizar esse processo de inserção, pode-se destruir a propriedade de heap do nó (ser maior do que todos os filhos). Assim, para corrigir este problema, realiza-se o processo de "peneirar para cima" (sifting up).

Esse processo consiste em trocar o nó inserido pelo seu nó pai, caso o valor deste seja menor que o o valor do nó inserido. Ao realizar esse processo, pode-se acabar destruindo a propriedade heap do nó imediatamente acima. Logo é necessário realizar o sifting up novamente. As trocas são realizadas enquanto o valor do nó inserido for maior que o valor do nó pai.

Existe dois tipos de árvore Heap, como a Max Heap e Min Heap:

A Max Heap tem o conceito de ordenação decrescente, ou seja, os pais dispõem de um valor mais elevado que de seus filhos.
A Min Heap, tem um sistema de ordenação oposta ao da Max Heap, sendo assim, os pais tem um valor menos significativo que seus filhos.

Árvore Trie editar

A estrutura Trie é um tipo de árvore utilizada para busca e inserção de chaves sequenciais. Seu nome vem do conceito em inglês reTRIEval, que significa recuperação, um nome que sumariza perfeitamente o seu uso na computação.^[8]

Os nós de uma Trie possuem múltiplos ramos, onde cada um destes expressa uma chave de caracteres. Para inserir uma chave em uma Trie, usa-se um nó para cada caractere presente na chave, dessa forma, o caracter-chave atua como índice para os filhos da matriz, caso seja uma nova chave ou uma extensão para uma existente, é necessário criar novos nós e nestes é necessário indicar o final da chave, para representar o fim de uma chave, é necessário identificar seu último nó como um terminal. A busca em uma chave é semelhante a inserção, mas nesse caso, apenas será comparado o caracter e caso este não seja um nó terminal, ele segue para o próximo nó.

O que torna a estrutura Trie eficiente para busca e obtenção de chaves é a sua complexidade linear O(N), tanto no caso médio de uso onde nem toda a chave é testada, quanto no pior caso onde toda a chave é comparada para se obter o resultado, para inserções segue a mesma complexidade. A critério de comparação, a busca na Árvore Binária de busca possui complexidade M * log(N) onde M é o tamanho máximo das chaves e N é a quantidades de nós na árvore. Assim, para grandes quantidades de elementos a Trie se torna muito mais interessante. Entretanto, como possivelmente cada nó da Trie pode ter W filhos, onde W é o tamanho do alfabeto suportado pela estrutura, em alguns casos a complexidade de espaço pode chegar a O(N*W), se tornando um problema.

Inserção em Trie: editar

Para a inserção, é feita uma busca pela palavra a ser inserida e, caso ela já exista na TRIE, nada é feito. Caso contrário, é recuperado o nó até onde acontece a maior substring da palavra a ser inserida. Então, o restante dos seus caracteres são adicionados na TRIE a partir daquele nó. ^[9]

Remoção em Trie: editar

Para a remoção, busca-se o nó que representa o final da palavra a ser removida e então são removidos os nós que possuem apenas um filho pelo caminho ascendente. A remoção é concluída quando se encontra um nó com mais de um filho. ^[9]

Implementação em C editar

O trecho de código a seguir contém a implementação de uma árvore trie e um exemplo de uso.

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TAMANHO_ALFABETO 256 // Para todas posições na tabela ASCII

#define CHAR_EM_INDICE(c)                                                      \
  ((int)c -                                                                    \
   (int)'a') // Converter o caracter de busca atual para a
             // representação suportada (caso alfabeto seja 'a' - 'z')

#define TAMANHO_ARRAY(a) sizeof a / sizeof(char *)

// Nó da estrutura Trie
typedef struct notrie {
  struct notrie *filhos[TAMANHO_ALFABETO]; // Para cada nó há a possibilidade de
                                           // TAMANHO_ALFABETO filhos

  bool noterminal; // Flag que indica se é o nó terminal, indicando o final de
                   // uma palavra dentro da árvore
} notrie;

notrie *criarnodo() {
  // Reserva e aloca {(void*) 0} para todas as posições possíveis deste nó
  notrie *novono = malloc(sizeof *novono);

  for (int i = 0; i < TAMANHO_ALFABETO; ++i) {
    novono->filhos[i] = NULL;
  }

  novono->noterminal = false;

  return novono;
}

bool inserenodo(notrie **raiz, const char *chavesinalizada) {
  // Permitindo a criação de uma raíz nula e tratando este caso
  if (*raiz == NULL)
    *raiz = criarnodo();

  // Tratando também caso onde seja passado um caracter de valor negativo
  unsigned const char *chave = (unsigned const char *)chavesinalizada;

  notrie *aux =
      *raiz; // Nó temporário efêmero às funções para percorrer a árvore
  unsigned int tamanho = strlen(chavesinalizada);

  int pos;

  // Percorre preenchendo no tamanho da palavra
  for (int i = 0; i < tamanho; i++) {
    // pos = CHAR_EM_INDICE(chave[i]); // Caso seja usado alfabeto a-z
    pos = (chave[i]);

    if (aux->filhos[pos] == NULL)
      aux->filhos[pos] =
          criarnodo(); // Cria um novo nó caso nesta posição ainda não exista

    aux = aux->filhos[pos]; // Caminha para o próximo nó
  }

  if (aux->noterminal)
    return false; // Encontrou essa palavra dentro da árvore

  aux->noterminal = true;
  return true; // Realizou a inserção com sucesso
}

bool buscarno(notrie *raiz, const char *chavesinalizada) {
  // Caso a raíz seja nula não há como realizar a busca
  if (raiz == NULL)
    return false;

  // Tratando também caso onde seja passado um caracter de valor negativo
  unsigned const char *chave = (unsigned const char *)chavesinalizada;

  notrie *aux =
      raiz; // Nó temporário efêmero às funções para percorrer a árvore
  unsigned int tamanho = strlen(chavesinalizada);

  int pos;

  for (int i = 0; i < tamanho; i++) {
    // pos = CHAR_EM_INDICE(chave[i]); // Caso seja usado alfabeto a-z
    pos = chave[i];

    // Caso não haja um dos caracteres na sequência significa que essa palavra
    // não está compreendida na árvore
    if (aux->filhos[pos] == NULL)
      return false;

    aux = aux->filhos[pos]; // Caminha para o próximo nó
  }

  return aux->noterminal;
}

// Exemplo de uso
int main() {
  const char *chaves[3] = {"arvore", "tries", "estrutura"};
  const char *testes[5] = {"pesquisa", "arvore", "incrivel", "tries",
                           "estrutura"};

  notrie *raiz = NULL;

  for (int i = 0; i < TAMANHO_ARRAY(chaves); i++) {
    inserenodo(&raiz, chaves[i]);
  }

  for (int i = 0; i < TAMANHO_ARRAY(testes); i++) {
    printf("%s %s\n", testes[i],
           buscarno(raiz, testes[i]) ? "está presente" : "NÃO está presente");
  }

  return 0;
}

^[8]

^[10]

A saída dessa implementação é mostrada a seguir.

$ gcc trie.c -o trie && ./trie
>   pesquisa NÃO está presente
>   arvore está presente
>   incrivel NÃO está presente
>   tries está presente
>   estrutura está presente

Implementação em Java editar

O trecho de código a seguir contém a implementação de uma árvore trie em Java.

import java.util.Scanner;

public class ArvoreTrie 
{  
        private char palavraChar[];
	protected Nodo raiz;
        protected int numDeNodos;
	public boolean isDebug;
        protected Scanner leitor;
        
	
	public static void main(String args[] )
	{
                
		ArvoreTrie trie = new ArvoreTrie(26);
		trie.setIsDebug(false);
		trie.iniciar();
		trie.finalizar();
	}
	
	public ArvoreTrie(int numDeNodos)
	{
                this.numDeNodos = numDeNodos;
		raiz = new Nodo(numDeNodos);
		raiz.isFinal = false;
		raiz.numeroDePrefixo = 0;
		raiz.prev = null;
		setIsDebug(false);
                leitor = new Scanner(System.in);
	}
	
	/**
	 * Método que retorna se esse código
	 * 	está em modo de debug
	 * @return Boolean { true - se está em debug | false - se não está debugando }
	 */
	public boolean isDebug()
	{
		return this.isDebug;
	}
	
	/**
	 * Recebe um booleando para informar se o código quando
	 * 	for executado será debugado ou não
	 * @param isdebug
	 */
	private void setIsDebug(boolean isdebug)
	{
		this.isDebug = isdebug;
	}
	
	/**
	 * Método que inicia e executa as ações sobre a árvore
	 */
	public void iniciar()
	{
		
		StringBuilder stringAcaoPalavra = new StringBuilder();
		String stringLida = leitor.nextLine();
		
		do{
			/*
			 * Pega a string e a converte para um array de char
			 */
			stringAcaoPalavra.append(stringLida);
			palavraChar = new char[stringAcaoPalavra.length()];
			palavraChar = stringAcaoPalavra.toString().toCharArray();
			
			/*
			 * De acordo com cada comando que se encontra na primeira
			 * 	posicao executa a ação.
			 * 	Ententendo: a palavra é passada para o inserir que retorna
			 * 	 um boolean sobre a ação que é repassado para o gerador de
			 * 	 saída que grava arquivo saida.txt
			 */
                        switch(palavraChar[0])
                        {
                            case 'i':
                                        geradorDeSaida( inserirString( palavraChar ) );
                                        break;
                            case 'b':
                                        geradorDeSaida( buscarString( palavraChar ) );
                                        break;
                            case 'r':
                                        geradorDeSaida( removerString( palavraChar ) );
                                        break;
                            default:
                                         finalizar();   
                        }
                        
			/*
			 * Limpa o StringBuiler e faz a leitura da próxima linha
			 */
			stringAcaoPalavra.delete(0, stringAcaoPalavra.length());
			stringLida = leitor.nextLine();
		}while( stringLida != null );
		
	}
	
	
	public void finalizar()
	{
                raiz = null;
                System.gc();
                System.runFinalization();;
                System.exit(0);
	}
        
	/**
	 * Método que insere uma string dentro da trie
	 * @param Char[] string
	 * @return Boolean {true - se inseriu ou há o elemento já inserido | false - se não pode inserir na árvore }
	 */
	protected boolean inserirString(char[] string)
	{
		Nodo nodo = raiz;
		nodo.numeroDePrefixo++;	//Diz que ali tem mais um nodo

		for( int a = 2; a < string.length; a++)
		{			
			int intChar = this.posicaoDoChar(string[a]);
			if( nodo.nodos[ intChar ] == null )
			{	
                            try
                            {
                                nodo.nodos[ intChar ] = new Nodo(numDeNodos);
                            }
                            catch(Exception erro)
                            {
                                System.gc();
                                System.runFinalization();
                            }

                           /*
                            * 	O nodo tem seus nodos vazios e acima diz que um dos nodos do nodo
                            * 	agora deve ser instanciado. Abaixo então o que fizemos:
                            * 	SE o nodos que criamos no nodo tal é nulo é pq ele não alocou
                            * 	nenhum dos seus nodos internos, logo faltou memória
                            */
                            if( nodo.nodos[ intChar ].nodos == null )
                            {
                                    return false;
                            }
                            nodo.nodos[ intChar ].prev = nodo;
			}
			nodo.nodos[ intChar ].numeroDePrefixo++;
			nodo = nodo.nodos[ intChar ];
		}
		nodo.isFinal = true;
		return nodo.isFinal;
	}
	
	/**
	 * Método para remover uma string dentro da trie
	 * 	Primeiro ele procura pela string, é o mesmo algoritmo do
	 * 	buscar, porém com um passo a mais.
	 * @param Char[] string
	 * @return boolean { true - se removeu | false - se não removeu }
	 */
	protected boolean removerString(char[] string)
	{
		Nodo nodo = raiz;
		/*
		 * Primeiro passo do remover é buscar a string até o final. 
		 * Isso faz com que o nodo esteja no nodo mais distante da string
		 * 	para que se possa voltar deletando
		 */
		int a;
		for( a = 2; a < string.length; a++)
		{
			if( nodo.nodos[ this.posicaoDoChar( string[a] ) ] != null )
			{
				nodo = nodo.nodos[ this.posicaoDoChar( string[a] ) ];
			}
			else
			{
				return false;
			}
		}
                
		/*
		 * Segundo passo é marcar esse nodo como não final, pois
		 * 	estaremos removendo a palavra que está até aqui. Depois
		 * 	enquanto ele não tiver prev null (raiz)
		 */
                if( nodo.isFinal != true)
                {
                    return false;
                }
		nodo.isFinal = false;
		Nodo temp;
		
		while( nodo.prev != null)
		{
			if( nodo.numeroDePrefixo <= 0)
			{
				temp = nodo;
				nodo = nodo.prev;
				nodo.numeroDePrefixo--;
				temp.finalize();
			}
			else
			{
				nodo = nodo.prev;
			}
		}
                /**
                 * Se o nodo é igual a raiz, então houve sucesso
                 *  no retornar
                 */
		if( nodo.equals(raiz))
		{
			return true;
		}
		else
		{
			return false;
		}
		
	}
	
	/**
	 * Método para realizar busca da string dentro
	 * 	da árvore trie
	 * 
	 * @param Char[] string
	 * @return boolean { true - se achou | false - se não achou }
	 */
	protected boolean buscarString(char[] string)
	{
		Nodo nodo = raiz;
		
		for( int a = 2; a < string.length; a++)
		{
			if( nodo.nodos[ this.posicaoDoChar( string[a] ) ] != null)
			{
				nodo = nodo.nodos[ this.posicaoDoChar( string[a] ) ];
			}
			else
			{
				return false;
			}
		}
		return nodo.isFinal;
	}
	
	/**
	 * Recebe um boolean que faz com que seja imprimido
	 *  V ou F de acordo com o seu valor
	 * @param boolean saida
	 */
	protected void geradorDeSaida(boolean saida)
	{
		if(saida)
		{
			System.out.println("v");
		}
		else
		{
			System.out.println("f");
		}
	}
	
	/**
	 * O método retorna o código que representa o char
	 * 	de 0 a 25 que será a sua posição na árvore trie
	 * @param char letra
	 * @return int{0 - 25}
	 */
	public int posicaoDoChar(char letra)
	{
		return (int)letra - 97;
	}
	
	/**
	 * Método de debugar o código no terminal
	 * 	recebe a mensagem que deve ser impressa no terminal
	 * @param mensagem
	 */
	protected void showDebug(String mensagem)
	{
		System.out.printf("%s", mensagem);
	}
}

^[11]

Referências editar

↑ ^1,0 ^1,1 ASCENCIO, Ana Fernanda Gomes; DE ARAÚJO, Graziela Santos. Estruturas de Dados: Algoritmos, Análise da Complexidade e Implementações em Java e C C++. São Paulo: Pearson Prentice Hall, 2010.
↑ ^2,0 ^2,1 ^2,2 ^2,3 http://coral.ufsm.br/beltrame/arquivos/disciplinas/graduacao_estrutura_de_dados/Estrutura-de-Dados_Aula-19_Arvores.pdf
↑ https://www.ufjf.br/jairo_souza/files/2009/12/5-Indexa%c3%a7%c3%a3o-Arvore-AVL.pdf
↑ https://docente.ifrn.edu.br/robinsonalves/disciplinas/estruturas-de-dados-nao-lineares/arvoreAVL.pdf
↑ SOUZA, Jairo. Árvore Vermelho-Preta. Disponível em: https://www.ufjf.br/jairo_souza/files/2012/11/5-Indexa%c3%a7%c3%a3o-Arvore-Vermelho-Preta.pdf. Acesso em: 04 jul. 2021.
↑ ^6,0 ^6,1 https://www.ime.usp.br/~pf/estruturas-de-dados/aulas/st-redblack.html
↑ FEOFILOFF, Paulo. A estrutura heap. 2020. Disponível em: https://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/heap.html. Acesso em: 03 jul. 2021.
↑ ^8,0 ^8,1 https://www.geeksforgeeks.org/trie-insert-and-search/
↑ ^9,0 ^9,1 https://www.ufjf.br/jairo_souza/files/2009/12/6-Strings-Pesquisa-Digital.pdf
↑ https://www.youtube.com/watch?v=3CbFFVHQrk4
↑ https://github.com/glaucomunsberg/try_a_trie/blob/master/trie/ArvoreTrie.java

[:1-1] 1,0 ^1,1 ASCENCIO, Ana Fernanda Gomes; DE ARAÚJO, Graziela Santos. Estruturas de Dados: Algoritmos, Análise da Complexidade e Implementações em Java e C C++. São Paulo: Pearson Prentice Hall, 2010.

[:0-2] 2,0 ^2,1 ^2,2 ^2,3 http://coral.ufsm.br/beltrame/arquivos/disciplinas/graduacao_estrutura_de_dados/Estrutura-de-Dados_Aula-19_Arvores.pdf

[3] ttps://www.ufjf.br/jairo_souza/files/2009/12/5-Indexa%c3%a7%c3%a3o-Arvore-AVL.pdf

[4] ttps://docente.ifrn.edu.br/robinsonalves/disciplinas/estruturas-de-dados-nao-lineares/arvoreAVL.pdf

[5] SOUZA, Jairo. Árvore Vermelho-Preta. Disponível em: https://www.ufjf.br/jairo_souza/files/2012/11/5-Indexa%c3%a7%c3%a3o-Arvore-Vermelho-Preta.pdf. Acesso em: 04 jul. 2021.

[:4-6] 6,0 ^6,1 https://www.ime.usp.br/~pf/estruturas-de-dados/aulas/st-redblack.html

[7] FEOFILOFF, Paulo. A estrutura heap. 2020. Disponível em: https://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/heap.html. Acesso em: 03 jul. 2021.

[:2-8] 8,0 ^8,1 https://www.geeksforgeeks.org/trie-insert-and-search/

[:3-9] 9,0 ^9,1 https://www.ufjf.br/jairo_souza/files/2009/12/6-Strings-Pesquisa-Digital.pdf

[10] ttps://www.youtube.com/watch?v=3CbFFVHQrk4

[11] ttps://github.com/glaucomunsberg/try_a_trie/blob/master/trie/ArvoreTrie.java

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]