Nesta aula, exploramos a árvore de decisão no contexto de busca, incluindo busca sequencial, busca binária, e a organização de dados com árvores binárias de busca (BST). Também discutimos a ordenação através de árvores e a complexidade envolvida.
Conceitos-chave: árvore de decisão, busca sequencial, busca binária, BST, ordenação por árvore e limites de complexidade de ordenação por comparação.
Árvore de decisão: uma árvore onde os nós internos representam decisões/pregões e os arcos representam resultados. Folhas representam estados finais ou resultados. Em um contexto de ações como "jogar moeda", cada caminho da raiz até uma folha representa uma sequência de resultados (cara/coroa) para as ações tomadas.
Busca sequencial: percorre uma lista sem considerar organização. A cada posição, compara o valor procurado com o elemento atual. No pior caso, percorre toda a lista e não encontra o valor.
Busca binária: aplica-se a listas ordenadas. Compara-se o valor com o elemento do meio, reduzindo o intervalo pela metade a cada passo. Se o valor for menor, busca na metade esquerda; se maior, na metade direita. Esse processo continua até encontrar o valor ou concluir que ele não está presente.
Árvore binária de busca (BST): estrutura de dados onde, para cada nó, todos os valores na subárvore esquerda são menores que o nó, e os da subárvore direita são maiores. A inserção de dados é feita comparando com a raiz e, conforme o resultado, seguindo para filho esquerdo ou direito, repetindo-se até encontrar uma posição livre.
Exemplo de BST: dados 5, 8, 2, 12, 14, 10, 9 inseridos na ordem descrita geram uma árvore com distribuição específica. Duas formas de organização citadas mostram diferenças de altura (uma com altura maior, outra com distribuição mais uniforme, até uma árvore aproximadamente cheia). A altura influencia a eficiência de buscas.
Ordenação usando árvore (tree sort): ao ordenar valores usando estruturas BST, cada etapa de comparação pode ser visualizada como um caminho na árvore (nó raiz, decisões para esquerda/direita). O conjunto de ordenações possíveis é grande e, em termos de limites, qualquer algoritmo de ordenação baseado apenas em comparações tem limite inferior de complexidade no pior caso.
Limite de complexidade para ordenação por comparação: o pior caso para ordenação baseada em comparações exige, no mínimo, log2(n!) decisões (aproximadamente n log2 n). Isso decorre do fato de haver n! permutações possíveis dos n elementos, e cada comparação reduz o espaço de busca pela metade no pior caso. Logo, d ≥ log2(n!).
Observação: os exemplos ajudam a entender como uma árvore pode representar as decisões e como a organização de dados influencia na eficiência de busca e ordenação.
Resposta correta: B) Em uma BST, para todo nó, valores da esquerda são menores que o nó e valores da direita são maiores.
Observação: essa propriedade permite buscas eficientes, já que cada comparação reduz a área de pesquisa pela metade em média.
Resposta correta: D) log2(n!)
Justificativa: existem n! permutações possíveis; cada comparação pode dividir o espaço de possibilidades pela metade em média, levando a um limite inferior de ~ log2(n!).
Resposta correta: C) 4
Explicação: seguindo a ordem de inserção, a BST resultante terá altura 4 (níveis 0 a 3); a distribuição apresentada no enunciado demonstra essa altura.
Resposta correta: B) log2(n!)
Justificativa: como existem n! permutações, o espaço de decisões exige no mínimo log2(n!) passos para distinguir todas as ordenações possíveis.
Olá, alunas e alunos do Conselho de Fundamentos Matemáticos para a Computação.
Nesta video, eu vou falar de árvore de decisão.
Eu vou começar apresentando um aguentivo de busca no contexto de árvore de decisão, a árvore de busca binária, em seguida apresentar o grítimo de ordenação no contexto de árvore de decisão.
O grítimo de busca, uma árvore de decisão, é uma árvore onde os internos não representar ações e os arcos vão representar os resultados.
Como assim? Isso quer dizer o seguinte, se eu tenho, por exemplo, a ação representada por esse nó, de jogar uma moeda.
Se eu estou obtido, pode ser cara ou coroa.
Se eu repito essa ação, eu tenho uma, duas, novas possibilidades de resultados.
Cara, coroa.
E assim sucessivamente, quando ele se disparar, onde vamos que eu cheguei aqui no nofólio, onde eu não executei a ação, e se eu fizer o percurso da raiz, até esse nofólio, eu tenho a sequência de resultados possíveis.
Então, esses nossos folhas aqui representam os resultados finais obtidos a partir das ações executadas.
E a árvore de decisão é uma peia, todas as decisões possíveis, todas as combinações de decisões possíveis tomadas.
Se eu decidir para direito ou para esquerda, então eu teria que todas as sequências de decisões possíveis para cada um dos momentos em que eu decidia esse respeito.
Se eu tivesse um contexto de movimentar direitas esquerdas, se fosse um robô móvel.
Então, eu teria que a sequência de atitudes tomadas.
Nesse caso, essa é a coisa de resultados obtidos no lançamento da moeda.
Bom, vamos agora analisar essa ideia da árvore de decisão no contexto de algoritmo de busca.
Vamos começar pela busca sequencial.
O algoritmo não é simples de busca.
O que ele faz? Você percorre simplesmente toda a lista de valores comparando o valor procurado em cada posição.
E aí, se for igual, você vai retornar aquela posição.
Se não, você vai percorrer toda a lista.
Mas se você percorre toda a lista, o valor não foi encontrado, você vai retornar que ele não foi encontrado.
Então, aqui terem um algoritmo, um pseudo código bem simples.
Eu recego uma lista ele de valores, o tamanho dessa lista e o valor de x você pesca.
Percor cada posição comparando com x e vou retornar com o encontrado, ou vou retornar que não foi encontrado ao final.
Bom, como que fica isso? Então, não contestar árvore de decisão.
A minha ação é comparar o valor de x com aquela posição da lista que eu estou analisando.
Se for igual, eu retorno que foi encontrado.
Se não, eu vou comparar com a segunda posição.
Se for igual, retorn, se não, eu vou comparar com a terceira.
E assim sucessivamente.
No pior caso, observa que eu vou percorrer toda esta mãe da árvore, toda essa profundidade da árvore para chegar à conclusão que eu não encontrei o elemento.
Bom, agora vamos pensar, esse algoritmo de busca sequencial, observe que ele sempre se é comparando com todos os valores.
Mas eu poderia estar trabalhando com uma busca binária, onde eu tenho uma lista que eu suponho ordenada.
E aí, considerando que a lista está ordenada, vamos suponha de nada em ordem crescente, eu posso ter três resultados possíveis na minha busca.
Eu valorei igual, e eu termino, o valor é menor, e aí eu vou buscar na metade esquerda da lista, o valor é maior, e eu vou buscar na metade direita da minha lista.
Como ficaria isso? Então aqui nós temos um algoritmo que pega essa lista, ele ordenado de tamanho, en, valor x da busca.
E aí começa a calcular, primeiro você quebra essa lista, então eu tenho uma lista de tamanho en, aqui eu vou fazer a média do tamanho dessa lista, o valor médio da lista, como a minha posição atual, a posição tempo aqui é ser avaliada.
E aí, comparo com o x, se esse é o valor, se errou, se não, eu comparo se é o valor maior.
Se for maior, eu vou para a metade direita da lista, se não, eu vou para a metade esquerda, e se não encontra nada retorno, que não existe o valor.
Só que aí o que que acontece? Eu estou quebrando o meu problema em pedaços menores, então eu começo, por exemplo, numa lista de tamanho 7, então considerando um mais 7 dividido por 2, eu vou ter a posição 4, a primeira se comparada, essa é minha primeira ação.
Se não for igual, se for menor, eu venho para essa metade da lista, que vai de 1L3, o que me leva a uma posição intermediária, valendo 2, então eu vou com minha aproximação, é comparar x com a posição L2, o valor da posição L2.
Se for menor, eu vou comparar com L1, se for maior, vou comparar com L3, e assim eu começo a testinativas do valor de x, então esses nofolas estão me retornando que esse x da repente estava entre 1 ou outro valor.
Nessa busca, o mesmo vai acontecer para essa segunda metade da lista, se fosse maior que L4, eu iria percorrer para L6, iria percorrer para valores que vão de L5, L8, fazendo a só mais 5, mais 8, de 1,2, eu caíria aqui, não vou redondando, eu teria que o maior aproximado, eu teria uma posição 6, a primeira ser comparada, se fosse menor, eu compararia com a posição 5, se não iria com a posição 7, e assim sucessivamente, dessa maneira eu vou quebrando a minha lista, fazendo as comparações e chegando ao final, por exemplo, se eu parasse aqui nesse nof na conclusão de que o valor de x é maior que o meu L8, ou que está entre L4 e L5, L5 e L6, e assim sucessivamente.
Bom, esses dados, como são arbitrados, eles podem ser organizados em uma estrutura, é uma chamada de árvore binária de busca, que sobre a qual podemos fazer uma pesquisa usando o algoritmo de busca em árvore binária, então, como se dessa organização em árvore binária? Primeiro, temos a construção dessa árvore, isso é feito da seguinte forma, o primeiro dado que você obtém, então lembre-se, nós estamos considerando dados arbitrados, então, o primeiro dado, eu vou consumir que é a raiz da árvore, e aí eu começo a usar aquela ideia de comparações, novos dados são inseridos, comparamos com os valores com o nó já existente, a começar pela raiz, então, o que eu faço? Se o dado for menor do que o nó, se o dado for menor do que o nó, o próximo nó se atestado é o filho esquerdo, se não o filho direito é testado, então, eu comparo com o nó, então, eu vou inserir um dado arbitrado, bom, primeiro é a raiz, aí eu vou inserir o próximo, ele é menor que a raiz, então, ele vai passar seu meu nó esquerdo, se ele for maior que a raiz, ele vai passar seu meu nó direito da raiz, e aí eu já começo a ter a lista arvore popular, o próximo nó eu vou comparar, se ele for menor que a raiz eu vou comparar com o filho esquerdo da raiz, e assim, sucessivamente, então, quando o nó não tem filho, o novo dado, torna seu filho, vamos ver isso com esse exemplo aqui que vai ficar bem claro, eu começo a estruturar, então, em árvore binária de busca, pegando o primeiro dado simplesmente, e assumindo, ele vai ser a minha raiz, nesse ponto que eu faço, o próximo dado é oito, ele é maior que 5, ele vai ser meu filho direito, o 2 vai ser meu filho esquerdo, o 12 eu comparo com 5, bom, ele é maior, comparo com 8, ele é maior, então, ele vai ser o filho direito do 8, o 14, a mesma coisa, eu comparo com 5, eu comparo com 8, eu conto com 12, e aí chega a conclusão que ele tem que ser o filho direito do 12, já o 10 eu faço a mesma comparação, só que quando chega no 12 eu vejo que ele vai ser o filho esquerdo, ele é maior que 5, maior que 8, menor que 12, o 9, ele é maior que 5, maior que 8, menor que 12, menor que 10, então, ele fica aqui, então nesse caso, reparem que a altura da minha árvore, eu fiquei com uma árvore com a altura, 1, 2, 3, 4, bom, o bicem vem agora, que eu vou ter, os mesmos dados, os mesmos valores, só que eles vão ser processados em uma ordem diferente, então, eu começo pelo 9, ele é maior, para se ser minha raiz, quando eu comparo 12, 12, passa ser o filho direito, entrando com o valor 5, filho esquerdo, quando eu entro com o valor 10, ele é maior que o 9, mas menor que o 12, então ele vai cair aqui, o 8 é menor que o 9, mais maior que o 5, então fica quando o filho direito do 5, o 2 como o filho esquerdo do 5, e o 14 como o filho direito do 12, reparem que nesse caso os meus dados ficaram com a distribuição mais gerando uma árvore, inclusive uma árvore cheia, uma árvore binária cheia, com a altura, 2, bom, com essa ideia de comparações com o filho esquerdo direito, vamos então mostrar como que o algoritmo de ordenação pode ser modelado, usando a árvore de decisão, então suponha que se eu tenho, eu quero ordenar valores numa lista, se eu tenho que a posição é li, eu vou prosseguir para o meu filho esquerdo, como a gente tinha que acabar de ver, se não, se ali for maior que ele, eu vou para o filho direito, dessa forma eu consigo ter uma representação desse tipo, se eu quisesse, por exemplo, ordenar uma lista com 3 valores, então eu comparo ele 1, ele 2, se ele é 1, fome menor que ele 2, eu comparo ele 2 com ele 3, se ele 2 com o menor que ele 3, eu vou ter que comparar o ele 1 com o no ele 3, se ele é 1, fome menor que ele 3, então dessa forma, todos os nossos termos, nós eles vão me dar ordenações possíveis, claro, aquelas ordenações que fogem a lógica estão representadas aqui por x, mas todas as ordenações possíveis estão representadas aqui, como esse caso, onde ele 1 era maior que ele 2, então eu comparava se ele 1 era maior, nesse caso ia para o filho direito, se ele 1 era maior que ele 3, eu também continuava no filho direito, e aí eu precisava redese de 2 era maior que ele 3, para obterça a sequência, ele 3 é menor que ele 2, menor que ele 1, então temos um teorena que diz que qualquer algoritmo que ordena uma lista de enelementos comparando pares de enelementos na lista, tem que fazer pelo menos logo em inifatorial comparações no pior caso, vamos ver isso, mas temos que o número de combinações possíveis dos resultados finais, numa lista por exemplo de enelementos, vai ser inifatorial, então e o último nível da árvore, ele tem 2 elevado a d, considerando o d a profundidade da árvore, nós foi, né, d da altura da árvore, então vamos ter 2 elevado a d, nós foi ok, então seja p o número de folhas, nós temos que p vai ser menor e igual a 2 elevado a d, que é o número de folhas naquela profundidade, continuando com esse raciocínio, o que nós vamos ter aqui, o número de nós folhas, ele tem que ser pelo menos, p tem que ser maior e igual a inifatorial, que é o número de combinações possíveis, e aí o que o cai? Eu cai na situação em que, no pior caso a ordenação a ser obtida, considerando p menor e igual a 2 d, vai me levar aplicando o log dos dois lados, a log de p menor e igual a log de 2 elevado a d, e aí fazendo as contas, nós temos o de d do lado direito, log de p aqui, o que me leva a d, maior e igual a log de p, que é a maior e igual a log de nifatorial, já que p tem que ser maior ou igual a nifatorial.
Bom, assim, encerramos a parte de árvore de decisão, espero que vocês, recomendo que vocês leiam a sessão 6.
4 do material base e nos vermos na próxima aula.
Muito obrigado.