Arvore de Decisão e Busca Binaria - Conceitos e Aplicações

1 Conceitos Gerais sobre Árvores Algoritmos de Alta Performance PROFa PATRÍCIA MAGNA profpatriciamagnafiapcombr 2 Definição Árvores são estruturas de dados bidimensionais que são usadas para armazenar dados de forma a permitir a busca e recuperação de informação mais eficiente do que em listas lineares A B C D G F E 3 Aplicação de Árvore machine learning Árvores de Decisão As Árvores de Decisão são um dos modelos mais práticos e mais usados em inferência indutiva Este método representa funções como árvores de decisão Estas árvores são treinadas de acordo com um conjunto de treino exemplos previamente classificados e posteriormente outros exemplos são classificados de acordo com essa mesma árvore 4 httpswwwvoooproinsightsfundamentosdosalgoritmosdemachinelearningcomcodigopythoner Aplicação de Árvore machine learning 5 httpswwwvoooproinsightsfundamentosdosalgoritmosdemachinelearningcomcodigopythoner Aplicação de Árvore Busca Binária 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 6 Como utilizar Árvores na computação Inicialmente precisamos convencionar termos usados para manipular o tipo de dado ÁRVORES A B C D G F E 7 Árvores Definição Conjunto finito e não vazio de elementos no qual um elemento é chamado de RAIZ e os elementos restantes são particionados em m0 subconjuntos disjuntos cada um dos quais sendo uma árvore em si mesmo Cada elemento numa árvore é chamado NÓ Um nó sem subárvores chamase FOLHA Exemplo Árvore A B C D E F G 9 Árvores Conceitos Cada nó pode ser a raiz de uma árvore com zero ou mais subárvores Se X é a raiz de uma árvore e Y é a raiz de sua subárvore direita ou esquerda então X é o PAI de Y e Y é o FILHO de X 10 Árvores Exemplo 1 A B C D G F E RAIZ da árvore Nós A B C D E F G FOLHAS EFCG FILHOS DE A FILHOS DE B FILHO DE D 11 Árvores Conceitos O nó X é um ANCESTRAL do nó Y e Y é DESCENDENTE de X se X for o PAI de Y ou então se X for o PAI de algum ANCESTRAL de Y Dois nós são IRMÃOS se forem filhos do mesmo pai Os nós Y1 Y2 Yj são irmãos e se o nó Z é filho de Y1 então Y2Yj são TIOs de Z 12 Árvores Exemplo 2 A C D B G E F NÓS IRMÃOS DESCENDENTES DE A ANCESTRAIS DE G TIOS de F e E 13 Árvores Conceitos O NÍVEL de um nó X é definido como segue a RAIZ tem nível 1 o nível de qualquer outro nó é um nível a mais que o nível de seu PAI A PROFUNDIDADE de uma árvore significa o nível máximo de qualquer FOLHA na árvore equivale ao tamanho do percurso mais distante da RAIZ até qualquer FOLHA 14 Árvores Exemplo 3 D C B E I G F J H K L N M O P PROFUNDIDADE 5 NÍVEL 1 NÍVEL 2 NÍVEL 3 NÍVEL 4 NÍVEL 5 A 15 Árvores Conceitos O GRAU ou GRAU DE SAÍDA de um nó numa árvore é o número de seus FILHOS O GRAU da árvore é o máximo entre os graus de seus nós 16 Árvores Exemplo 3 D C B E I G F J H K L N M O P GRAU DE A 4 GRAU DE B 3 GRAU DE C 0 GRAU DE M 1 Grau da arvore4 A 17 Árvores Exemplo 4 D I PROUNDIDADE 4 NÍVEL 1 NÍVEL 2 NÍVEL 3 NÍVEL 4 GRAU DE A 3 GRAU DE B 4 GRAU DE C 1 GRAU DE E 0 Grau da arvore4 A B G F J H K L E C REFERÊNCIAS TENENBAUM AM E outros Estruturas de Dados usando C Makron Books do Brasil Editora Ltda SP PEREIRA S L Estrutura de Dados Fundamentais São Paulo Érica FORBELLONE ALV EBERSPÄCHER HF Lógica de Programação A Construção de Algoritmos e Estruturas de Dados Makron Books São Paulo SP ASCENCIOAFG e ARAÚJO GS Estruturas de Dados Algoritmos Análise da Complexidade e Implementação em JAVA e CC 19 Copyright 2023 Profa Patrícia Magna Todos direitos reservados Reprodução ou divulgação total ou parcial deste documento é expressamente proibido sem o consentimento formal por escrito dos professores