Árvores e suas Generalizações: árvores binárias, árvores de busca, árvores AVL
Saiba o que são árvores e suas generalizações: árvores binárias, árvores de busca, árvores AVL. Veja exemplos e aplicações desses tipos de árvores.
Técnologia em Alta
Uma árvore é uma estrutura de dados que representa uma coleção de elementos hierárquicos, chamados de nós, conectados por arestas. Cada nó pode ter zero ou mais filhos, que são outros nós que dependem dele. Um nó sem filhos é chamado de folha. Um nó sem pai é chamado de raiz. A altura de uma árvore é a distância máxima entre a raiz e qualquer folha. A frase-chave deste texto é árvores e suas generalizações.
Existem vários tipos de árvores, que se diferenciam pela forma como os nós são organizados e pelas propriedades que elas possuem. Neste texto, vamos falar sobre três tipos de árvores: árvores binárias, árvores de busca e árvores AVL. Esses tipos de árvores são generalizações de árvores, pois elas têm características específicas que as tornam úteis para diferentes aplicações.
Árvores binárias
Uma árvore binária é uma árvore em que cada nó tem no máximo dois filhos, chamados de filho esquerdo e filho direito. Uma árvore binária pode ser vazia, ou seja, sem nenhum nó, ou não vazia, ou seja, com pelo menos um nó. Uma árvore binária não vazia pode ser dividida em três partes: a raiz, a subárvore esquerda e a subárvore direita, que são também árvores binárias.
As árvores binárias são usadas para representar expressões aritméticas, operações lógicas, árvores de decisão, entre outras aplicações. Um exemplo de árvore binária que representa a expressão (a + b) * (c - d) é:
*
/ \
+ –
/ \ / \
a b c d
Árvores de busca
Uma árvore de busca é uma árvore binária em que cada nó armazena um valor e os valores seguem uma ordem. A ordem é definida por uma função de comparação, que determina se um valor é menor, igual ou maior que outro. A propriedade que define uma árvore de busca é que, para qualquer nó, os valores dos nós da subárvore esquerda são menores que o valor do nó, e os valores dos nós da subárvore direita são maiores que o valor do nó.
As árvores de busca são usadas para armazenar e recuperar dados de forma eficiente, pois elas permitem realizar operações como inserção, remoção e busca em tempo proporcional à altura da árvore. Um exemplo de árvore de busca que armazena os valores 1, 2, 3, 4, 5, 6 e 7 é:
4
/ \
2 6
/ \ / \
1 3 5 7
Árvores AVL
Uma árvore AVL é uma árvore de busca que tem uma propriedade adicional: o fator de balanceamento de cada nó é igual à diferença entre as alturas das subárvores esquerda e direita, e esse fator deve ser -1, 0 ou 1. Essa propriedade garante que a árvore esteja balanceada, ou seja, que as subárvores tenham alturas semelhantes. Uma árvore balanceada tem uma altura mínima, o que melhora o desempenho das operações de inserção, remoção e busca.
As árvores AVL são usadas para implementar dicionários, tabelas de símbolos, índices de bancos de dados, entre outras aplicações. Um exemplo de árvore AVL que armazena os valores 1, 2, 3, 4, 5, 6 e 7 é:
