Árvores são muito importantes no mundo da ciência da computação. Uma árvore é um tipo específico de grafo. Para que um grafo seja classificado como uma árvore, ele deve: * Não tenha loops ou ciclos (caminhos onde os nós inicial e final são os mesmos). * Esteja conectado (cada nó pode ser alcançado a partir de qualquer outro nó). Árvores são estruturas de dados não lineares que organizam nós em uma hierarquia, onde os nós podem ter filhos, irmãos e nós pais. O nó raiz é o topo de uma árvore. É o único nó na árvore sem um nó pai. Este é o nó onde você começará a percorrer toda a estrutura de dados, geralmente com algoritmos como breadth-first search (BFS) ou depth-first search (DFS). Este é um exemplo gráfico de uma árvore: <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/what-are-trees-and-tries-and-how-do-they-work-1.png" alt="A tree diagram showing a hierarchical structure with node A at the root, nodes B and C as children of A, and nodes D and E as children of C. Node B is a leaf node."> Como os nós são organizados em uma hierarquia, eles têm relações entre si. Um nó pai é um nó que está imediatamente conectado a outros nós abaixo dele. No diagrama, o nó A é o nó pai dos nós B e C. Um nó filho é um nó que está imediatamente conectado a um nó acima dele. No diagrama, o nó D e o nó E são os nós filhos do nó C. Os nós D e E também são classificados como leaves. Uma leaf é um nó que não possui nós filhos. Você pode considerá-los como o fim dos "ramos" da árvore. Os nós da árvore também possuem propriedades importantes: * Profundidade: o comprimento do caminho da raiz até esse nó. Por exemplo, no diagrama, o nó D tem profundidade 2 porque se você começar na raiz, precisa passar por duas arestas para alcançá-lo. * Altura: o comprimento do caminho desse nó até uma folha. Por exemplo, o nó C tem altura 1 porque está um nível acima dos nós folha. * Grau: o número de nós filhos que cada nó possui. No diagrama, o nó B tem grau 0 porque é um nó folha, então não possui nós filhos. O nó C tem grau 2 porque possui dois nós filhos. Árvores também têm uma altura. A altura de uma árvore é a altura do seu nó raiz. Existem muitos tipos diferentes de árvores, incluindo Binary Trees, Binary Search Trees, AVL trees, Red-Black Trees e B-Trees.

Árvores Binárias e Árvores Binárias de Busca

Estes são dois dos tipos de árvores mais comumente usados. Uma árvore binária é um tipo de árvore na qual cada nó pode ter no máximo dois nós filhos, um nó filho à esquerda e um nó filho à direita. Sim, isso significa que o exemplo que você viu até agora é uma árvore binária! <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/what-are-trees-and-tries-and-how-do-they-work-1.png" alt="The same binary tree example highlighting that it's a binary tree, with each node having at most two children."> Uma árvore binária de busca é uma versão mais específica de uma árvore binária, com uma propriedade de ordenação muito particular. Para entender isso, primeiro você precisa entender subárvores. Uma subárvore é uma seção de uma árvore que é uma árvore por si só. No nosso exemplo de árvore, os nós C, D e E formam uma árvore por si só, então eles são considerados uma subárvore. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/what-are-trees-and-tries-and-how-do-they-work-3.png" alt="A diagram highlighting a subtree within the main tree, showing nodes C, D, and E forming their own tree structure."> A propriedade de ordenação das árvores binárias de busca (BST) estabelece que para cada nó, todos os valores em sua subárvore esquerda são menores que o valor do nó e todos os valores em sua subárvore direita são maiores que o valor do nó. As subárvores esquerda e direita também devem ser árvores binárias de busca. Essa ordenação torna as operações de busca, inserção e exclusão muito eficientes se a árvore estiver balanceada. Uma árvore balanceada é uma árvore na qual as alturas das subárvores esquerda e direita de qualquer nó são muito semelhantes para garantir que as operações permaneçam eficientes.

Tentativas

Agora que você sabe mais sobre árvores e árvores binárias de busca, vamos mergulhar em tries. Tries são estruturas de dados em árvore usadas para armazenar um conjunto de strings. Tries também são conhecidos como prefix trees porque são muito eficientes para operações que exigem encontrar strings com base em seus prefixos. Cada nó na trie representa um único caractere de uma string. O nó raiz não representa nenhum caractere específico, então você pode considerá-lo como representando uma string vazia. À medida que você percorre o trie a partir da raiz, o caminho até um nó define um prefixo específico. Para encontrar uma palavra, você segue esse prefixo até alcançar o nó com a palavra que está procurando. Nós que representam palavras completas são atribuídos marcadores de fim de palavra. Este é um exemplo de um trie com as palavras "top", "tea" e "ten". Observe como as palavras "tea" e "ten" compartilham o mesmo prefixo "te", então a estrutura de dados segue o mesmo caminho até o último caractere, que é marcado como um caractere de fim de palavra. Neste diagrama, isso é representado com uma borda vermelha ao redor do nó: <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/what-are-trees-and-tries-and-how-do-they-work-4.png" alt="A trie data structure showing the words 'top', 'tea', and 'ten'. The root node branches to 't', which then branches to 'o' (leading to 'top') and 'e' (leading to 'tea' and 'ten'). End-of-word nodes are marked with red borders."> A complexidade de tempo no pior caso para a operação de busca é O(L), onde L é o comprimento da string que você está procurando. A inserção também é eficiente. Esta operação requer apenas a criação de novos nós para os caracteres que ainda não existem no trie. A grande vantagem desta estrutura de dados é que quando múltiplas strings compartilham o mesmo prefixo, seus caminhos se sobrepõem, então o próprio prefixo é armazenado apenas uma vez. Essa eficiência torna as tries perfeitas para implementar recursos como autocomplete e verificadores ortográficos. No entanto, tries não são eficientes para todos os conjuntos de strings. Eles podem ser ineficientes se o conjunto de strings tiver muitos caracteres únicos. Isso exigiria armazenar muitos caracteres únicos como nós individuais. Esses nós teriam que ser percorridos para encontrar as palavras, o que não seria ideal. Agora que você está familiarizado com os diferentes tipos de árvores e para que elas são usadas, você pode começar a usá-las em cenários do mundo real. Saber como escolher a certa é uma habilidade valiosa para ter quando você precisa enfrentar desafios no seu trabalho diário.