Uma árvore é uma estrutura de dados não linear formada por nós (ou vértices) conectados por arestas, que possuem uma relação de hierarchicalidade. Possui um nó especial chamado raiz (quando a árvore não é vazia) a partir do qual todas as outras estruturas se ramificam. Não há ciclos em uma árvore, o que a diferencia de grafos.
Exemplo simples de árvore (representação textual):
Raiz
├─ A
│ ├─ B
│ └─ C
└─ D
Observações importantes: - Existem árvores vazias (sem nós) e árvores não vazias (com raiz). - Subárvore de um nó é a árvore formada pelo nó e todos os seus descendentes. - Árvores são estruturas úteis para organizar dados hierárquicos, como diretórios de arquivos, organização de itens, síntese de expressões, entre outros.
Diferença entre árvore e grafo: - Árvore: não possui ciclos; cada nó (exceto a raiz) tem exatamente um pai; existe uma raiz única. - Grafo: pode ter ciclos; cada par de nós pode ter mais de uma relação direta e não há necessidade de raiz única.
Cada nó pode ter vários filhos. O nó pai de um nó é o nó que o conecta à raiz; nós que são descendentes diretos de um nó são seus filhos. Um nó que não tem filhos é chamado de folha. Nós que possuem filhos são chamados de nós internos. Um conjunto de nós que não está mais subdividido é uma subárvore de um nó.
Grau de saída de um nó: número máximo de filhos desse nó. Grau da árvore: maior grau de saída entre todos os nós da árvore.
Exemplo: se o nó A tem 3 filhos, seu grau de saída é 3. Se nenhum outro nó tiver mais que 3 filhos, o grau da árvore é 3.
Nível de um nó: distância da raiz medida em número de arestas (em algumas convenções, contar-se números de nós). Na abordagem do conteúdo apresentado, a raiz está no nível 1, seus filhos no nível 2, e assim por diante.
Altura de um nó: quantidade de nós no caminho mais longo partindo desse nó até uma folha (contando a partir do próprio nó). A altura da árvore é a altura da raiz (ou seja, o caminho mais longo da raiz até uma folha). Exemplo: se o caminho mais longo da raiz até uma folha tem 3 vértices, a altura da árvore é 3.
Para problemas de busca, a altura da árvore é crucial: menores alturas significam menos comparações para encontrar um elemento. Em árvores bem balanceadas, a altura é aproximadamente log2(n), onde n é o número de nós.
Árvore binária é uma árvore em que cada nó tem, no máximo, dois filhos: filho esquerdo e filho direito. Além disso, cada nó armazena um dado (a informação). Um nó pode ter apenas o filho esquerdo, apenas o filho direito, ou nenhum filho.
Uma ABB é uma árvore binária com uma propriedade adicional de ordenação: para cada nó R, todos os elementos na subárvore da esquerda são menores que a chave de R, e todos os elementos na subárvore da direita são maiores que a chave de R. Essa ordenação facilita buscas eficientes.
Exemplo simples (com valores representados por letras, mantendo a ideia de ordem alfabética):
D
/ \
A F
\ / \
B E G
\
C
Observação: a ABB apresentada no exemplo acima é apenas ilustrativa; uma ABB válida deve respeitar a relação: para cada nó, esquerda < nó < direita. Em alguns casos, um BST pode se tornar desbalanceado, levando a buscas menos eficientes. Balanceamento automático (ex.: AVL, árvores rubro-negras) é uma técnica comum para manter a altura baixa.
A busca em ABB começa pela raiz e, a cada comparação, decide ir para a subárvore da esquerda (se o alvo for menor) ou para a da direita (se for maior). Esse processo elimina grande parte dos nós a cada passo, resultando em buscas eficientes, especialmente quando a árvore está balanceada.
Exemplo de busca pela chave E na ABB do exemplo acima:
Se a ABB fica muito desequilibrada (ex.: quase uma lista), o número de comparações pode crescer para O(n). Existem variantes que mantêm o balanceamento automaticamente, como AVL e árvores rubro-negras, mas esses algoritmos vão além deste conteúdo introdutório.
Para uma ABB balanceada com altura h, o número de comparações na busca é no máximo h, e h é aproximadamente log2(n). Em árvores não balanceadas, essa relação pode degradar para O(n).
Qual é a característica essencial que diferencia uma árvore de um grafo?
Resposta correta: C) Não pode haver ciclos; há uma raiz única ou raiz vazia
Observação: árvores não possuem ciclos e, exceto pela raiz, cada nó tem exatamente um pai. O grafo pode possuir ciclos e várias raízes.
Qual é a definição correta de uma árvore binária de busca (ABB)?
Resposta correta: C) É uma árvore binária onde, para cada nó, todas as chaves da subárvore esquerda são menores que a chave do nó e todas as chaves da subárvore direita são maiores
Essa é a definição fundamental de ABB, que facilita buscas eficientes ao manter a ordem entre esquerdo e direito.
Em uma ABB balanceada, qual é o número máximo de comparações necessárias para encontrar um elemento, dado que a altura é h?
Resposta correta: B) h
Em ABB balanceadas, a busca requer no máximo uma quantidade de comparações igual à altura h, pois cada passo desce para uma metade (esquerda ou direita) da árvore.
Considere as afirmações sobre árvores binárias de busca balanceadas. Assinale a alternativa que descreve corretamente por que os algoritmos de balanceamento mantêm a eficiência de busca e mencione dois métodos comuns de balanceamento.
Resposta correta: B) Balanceamento reduz a altura para manter buscas em O(log n); métodos comuns: AVL e árvores rubro-negras
Explicação: manter a altura logarítmica garante que o pior caso de busca permaneça eficiente. AVL e RB-tree são técnicas populares de balanceamento automático.
O lápizson albeem vindo novamente a nossa disciplina de algoritmos e programação de computadores 2 aqui para um IDSP.
Essa é a nossa videoaula de número 10.
A nossa aula sobre estruturas de dados mais conhecidas e mais importantes para a área de computação.
Na última estresse, a gente nos vê os conceitos de pilhas, filas e listas.
Na última que foi sobre listas, eu apresentei para vocês algumas variações dessas listas.
Um dos tópicos que eu falei ali era a questão de listas lineares e não lineares.
A gente vai ver hoje um pouquinho sobre as listas não lineares, que é o nome que a gente dá para o conceito de árvores.
Então, a árvores, pessoal, é uma estrutura de dados da ira da computação, que é bem conhecida e bem utilizada para resolver diferentes problemas computacionais.
Então, no caso das listas que a gente estava vendo até as últimas aulas, a gente tem uma linearidade dos elementos.
Os nossos arjacentes e você tem uma identificação do sucessor que ele não e do antecessor também.
Mas, por outro lado, existem diversas aplicações em que você precisa destuturas que sejam mais complexas do que listas lineares, que, ao caso, por exemplo, de das listas não lineares que envolvem a árvores, envolvem grafos entre outras estruturas.
Então, hoje a gente vai ver um pouquinho sobre os conceitos relacionados com árvores.
Olha aqui um exemplo bem simples do que é uma árvore.
Então, na verdade, não é uma árvore como a gente vê na natureza.
A gente imagina como se fosse uma árvore de ponta-cabeça, onde você vai ter a raiz desta árvore e você vai ter ramificações, como se fosse também os galhos desta árvore, dando origem também a folhas, a nós internos.
Então, essa é a ideia de árvore que, como eu falei, é uma lista não linear, ou seja, você tem bifurcações aqui de um noo para o outro.
Então, você não tem mais esse conceito de antecessor e sucessor.
Mais por outro lado, você tem outros conceitos aí que estão relacionados com o azarva.
Está que a gente vai ver daqui a pouco.
Bom, como a motivação para uso de árvores existem em números problemas que podem ser tratados por meio delas.
Então, as árvores existem um tratamento computacional eficiente.
Quando a gente compara com estruturas mais complexas e mais genéricas, como no caso de grafos, qualquer diferença entre uma árvore e um grafo, é que, no caso de grafo, você pode ter um ciclo entre os elementos.
Então, esse ciclo, o que ocorre aqui, é o que caracteriza um grafo ao invés de uma árvore.
No caso de uma árvore, você não pode ter esse ciclo, não pode ter um caminho se fechando entre os elementos.
Por conta disso, as árvores são mais fáceis de manipular do que os grafos.
Nem por isso que elas sejam menos eficientes do que grafos.
Então, no caso, é possível utilizar essas estruturas de árvores para resolver vários problemas aí computacionais.
Um desses problemas é o problema de busca.
Então, a gente vai ver daqui a pouco que existem tipos específicos de árvores que podem ser usados de uma maneira bastante eficiente para fazer buscas por elementos de um determinado conjunto.
Vamos ver um pouquinho aqui alguns conceitos sobre árvores.
Então, uma árvore T é um conjunto finito de elementos que a gente vai denominar de nós ou de nós, que nós temos que ter uma árvore vazia, que é dizer, você não tem nenhum nó ali naquela árvore, ou então existe um nó especial chamado de R, então, você vai ter um nó, você vai chamar esse nó aqui de R, que é a raiz desta árvore e os nossos restantes desta árvore vão constituir um único conjunto vazio, que é dizer, só vai ter o nó raiz, ou você vai dividir esses nossos restantes em um conjunto, em M um juntos, que não são vazios que a gente chama de sub árvores de R, e cada sub árvore dessa é também considerada uma árvore, então você aplica esse mesmo, essa mesma definição que eu estou falando para vocês.
Então, olha aqui, a gente tem o nó raiz, que é o R que está aqui, e nesse caso, a gente tem os outros elementos formando M juntos, onde cada subconjunto desse daqui é uma sub árvore de R, e que, por sua vez, cada um desse que tem a considerada uma árvore que também possui suas sub árvores, e assim por diante.
Vamos ver alguns conceitos sobre árvores, então, a gente tem um conceito de nossos filhos, pares, tios, irmãos e avô, se a gente olhar aqui para esta árvore e imaginar que é como se fosse uma árvore geneológica, a gente tem aqui que o nó raiz, ele é pai dos elementos B, C e D, que, por sua vez, são irmãos entre C, a gente tem um conceito de avô, então, o A é um avô, por exemplo, do elemento E, a gente tem também que o elemento C, ele é Tio do elemento E, e então, quer dizer, você não tem manho que é só pai, então você só vai ter o elemento pai, de um determinado nó, que é o seu ancestral, e a gente tem outros conceitos também, no caso, tem um grau de saída de um nó e o grau da árvore, então, no caso, o grau de saída de um nó é quanto, os coca-números máximo de filhos desse nó, então, por exemplo, aqui o nó C, tem grau de saída igual a 3, porque tem os elementos H e E, e j, e considerando a árvore inteira, o grau da árvore é, o grau daquele nó que tem maior número de filhos, então, nesse caso, aqui tanto B quanto C, tanto B, tanto B quanto C, e quanto A, eles possuem grau 3, que é o máximo, então, a árvore tem grau de, ela tem grau 3 também, a gente também tem o conceito de nó folha e nó interior, no caso, nó folha são aqueles nós que não possuem filhos, e nós, interiores são aqueles que possuem filhos, e o nível e altura de um nó, que é, no caso, o nível, a gente conta de cima para baixo, então, no A, o nó A, ele está no nível 1, os nós B, C e D estão no nível 2, aqui, eles estão no nível 3, e esses daqui estão no nível 4, tá? A altura de um nó é a quantidade de nó que você tem, desse nó até a sua folha com o caminho mais longo, né? Então, olha só um exemplo, então, aqui esse nó C, o nosso altura dele é a quantidade de nó até chegar no nó N, que é aquela folha que tem o maior caminho, né? De partir do C até chegar nela, tá? Então, olha só, por exemplo, aqui o nó A, que é também a raiz, tem a altura igual a 1, 2 e 3, tá? Então, a altura do No A é 3, porque o maior caminho até chegar numa das folhas, tudo bem? E a altura da árvore em si é a altura da raiz, tá? Como eu a gente viu aqui, é a altura 3, tá? Essa árvore que a gente está usando como exemplo.
Bom, então, dado essa definição de árvores, a gente pode instanciar ela para um conceito um pouco mais específico, que é a ideia de árvores binárias, o que é o marbre binária? O marbre binária, pessoal, são árvores que possuem grau 2, quer dizer, a hora no A só pode ter no máximo 2 filhos.
Então, repare aqui que eu tenho o No A, ele vai ter o filho da esquerda e o filho da direita, o No B vai ter o filho da esquerda e da direita, tá? E pode ser que você tenha também só de um lado, né? Por exemplo, você vai ter o no A C só tem o filho da direita, tudo bem? Além então, da ideia de filho esquerdo e filho direito, a gente também tem a informação que é o dado, né? O aquilo que você vai armazenar em cada No.
E especificando um pouco mais essas árvores binárias, existe também uma outra definição de árvores, um outro tipo de árvores que são as árvores binárias de busca.
As árvores binárias de busca, pessoal, são árvores binárias também, quer dizer, você tem também essa, o grau da árvore igual a 2, né? E só que além disso, você tem também uma certa ordem da informação que você está armazenando nesses nós.
Então, a gente tem que achar ou a informação de cada No, da subi árvore da esquerda, vai ser menor do que a chave do No R, que é da raiz, né? E a chave de cada No, da subi árvore da direita de R, né? Dessa No raiz, é maior do que a chave do No R, tá? Então, olha só que um exemplo, eu tenho esta na área, eu tenho, por exemplo, esse No com a informação que é o elemento D de dado, né? E reparem que todos os filhos de lado esquerdo de D são menores do que D.
Então, o D é menor do que D, o A é menor do que D, o C é menor do que D pensando numa ordem alfa-bética, tá? E do lado direito, todos os nós são maiores do que o elemento D, tá? Então, F é maior do que D, E, e o G também são maiores do que D.
Então, você tem esta ordem das chaves que estão na árvore, e além disso, a árvore é binária, tá? Então, você só pode ter no máximo dois filhos, que é o lado esquerdo, e lá direi.
E além disso, você também tem esta ordem em relação a subi árvores.
Então, por exemplo, o elemento F, os filhos do No F vão ter chaves menores do que F, por exemplo, aqui, que é o E, e do lado direito, vão ser maiores do que F que é o G, nesse caso, tudo bem? Aqui, apesar de se tomar a árvore binária, ela não é de busca, porque você tem aqui o No B, que é um filho esquerdo do No A, só que B é maior do que A, e ele está lá do esquerdo de A.
Então, por isso que não é uma árvore binária de busca, ela só é uma árvore binária, tá? Sem ser de busca, tá? Por que essas árvores binárias de busca são eficientes? Por que eu estou apresentando esse tipo específico para vocês? Por que, pessoal, para se buscar em uma árvore binária de busca, isso acaba sendo bem eficiente? Por que? Porque você vai ter poucas comparações para se realizar até encontrar um elemento nestarbre.
Então, você começa sempre a fazer a busca por uma determinada chave a partir da raiz, se o elemento que você está buscando é menor do que o elemento que está armazenado na raiz, você começa a fazer a busca do lado esquerdo, se não, você faz a busca do lado direito.
E quando você faz esse teste, de por lado esquerdo ou de direito, você acaba eliminando boa parte dos elementos para comparar com a chave que você está buscando.
Então, olha só, por exemplo, supongo que eu queira fazer a busca pelo elemento E nesta árvore que está aí.
Então, eu não comecei no pelo arraí, a gente sabe que E é maior do que D, então, a gente vai pro lado direito desta árvore, aqui, esta seta que está aqui.
Agora, o elemento E, a gente vai comparar com o próximo nó, que é o F, como E é menor do que F, a gente vai pro lado esquerdo.
Então, a gente segue o caminho esquerdo até chegar no próximo nó, e nesse caso é o elemento que a gente busca, estava buscando, no caso, ele existe aí nesse conjunto.
Então, repare que eu fiz três consultas para encontrar o elemento E.
Nesse conjunto, aí, que eu tenho 4, 5, 6, 7 elementos, então, dos 7 elementos, eu fiz apenas três consultas.
Bom, aí, pessoal, olha só, se a gente começa a expandir esta árvore de busca binária, ao longo de N-levels desta árvore, então, reparem que aqui eu tenho esta aqui a minha árvore binária de busca.
E aqui, eu estou contando quantos elementos eu consigo armazenar até determinado nível.
Então, por exemplo, até o nível 2, eu estou armazenando três nós.
N-level 2, eu tenho três nós, que é este, este, e este está aqui.
Tudo bem? Para o nível 3, eu estou armazenando 4, 5, 6, 7 nós.
E quando chega lá no nível N, eu vou ter uma fórmula que a gente pode encontrar, que é 2n-1.
Então, se eu tiver, por exemplo, um nível 30, que é dizer, se eu descer aqui até o nível 30, eu vou ter essa quantidade de nós que está aqui sendo armazenada na minha árvore.
Só que, tendo aquela ideia de você ir para o lado esquerdo, ou para o lado direito, neste árvore de busca para encontrar um elemento, reparem que eu vou precisar fazer, para este caso, aqui, de nível 30, eu vou fazer no máximo 30 comparações.
Porque, supondo que aqui eu vou encontrar, supondo que este é o elemento que eu quero fazer a busca, que eu faço.
Eu vou por lado direito, depois eu vou por lado direito de novo, depois eu vou por lado esquerdo, depois eu vou por lado esquerdo.
Então, eu vou ter 5 comparações, neste caso, onde 5 é igual ao nível do nó que eu estou encontrando.
Então, para essa quantidade enorme aqui de 1 bilhão de elementos, mais de 1 bilhão de elementos, eu só vou precisar fazer 30 comparações.
Por isso, que as árvores binárias de busca são extremamente eficientes para se realizar a busca.
É claro que é importante que esta árvore, pessoal, ela esteja balanciada, porque se você tiver mais elementos por lado esquerdo, do que por lado direito, essa quantidade de comparações, igual ao nível, ela não vai ser mais verdadeira.
Para isso, existem outros tipos de árvores de binárias de busca que fazem este balanciamento de uma maneira automatizada para você, com as árvores AVL ou rubro negras, entre outras, que tão fora do escopo dessa disciplina, que são mais avançadas, mas que o pessoal da computação, pelo menos, vai aprender isso certamente.
Tudo bem, gente? Muito bem, então, essa foi a nossa visuala sobre árvores.
A gente aprendeu, então, o conceito mais geral, a id de árvores, que são listas não-linearres.
Vimos as árvores binárias, que são árvores que têm grau 2, e vimos as árvores binárias de busca que, além do grau 2, você também tem essa ordem das chaves entre raiz, lado esquerdo, lado direito.
A gente viu que é um tipo de aplicação, a busca para árvores que é bastante interessante.
Então, eu agradeço a atenção de vocês, espero que vocês possam ter compreendido um pouco sobre essa estrutura árvores, e a gente se vê numa próxima oportunidade.
Obrigado.