# Curso Livre de Estruturas de Dados/Árvores de Busca
## Árvores de Busca (Estrutura de Dados)

Á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. Além disso, ainda segundo Ascencio & De Araújo (2010, p. 278), nem todos os elementos possuem encadeamento.
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

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

### Árvore binária

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).

#### Percursos

Nas árvores binárias existem quatro possibilidades de percorrer a árvore, sendo estes:
* Pré-ordem.
* Em ordem (simétrica).
* Pós-ordem.
* Em nível

##### Pré-ordem

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

##### Em ordem (simétrica)

No percurso simétrico, é percorrido a subárvore esquerda, seguindo para a raiz, após isso percorre a subàrvore direita. 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.

##### Pós-ordem

No percurso de pós-ordem, é percorrido a subárvore esquerda, com isso segue para a subárvore direita e por último a raiz. 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.

##### Em-nível

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:

#### Busca

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

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

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.

##### Tipos de árvores n-árias

* 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

* 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

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

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

* 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 ⌊ i−1/m ⌋{\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

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

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.
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.
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.
Abaixo, a implementação de uma árvore AVL na linguagem C.

### Árvore Rubro-Negra

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.
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.
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:

#### Inserção em Árvore Rubro-Negra

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.
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:
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.
O código abaixo mostra um exemplo de implementação, com destaque para o método de inserção:

### Árvore Heap

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.
Uma árvore binária se caracteriza justificada à esquerda quando possuir 2$^n$ 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

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.
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:

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ó.

#### Remoção em Trie:

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.

#### Implementação em C

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

#### Implementação em Java

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