Neste OVA vamos estudar sobre uma operação na árvore binária, a busca. Além de desenvolver esse conhecimento,
você poderá interagir e exercitar os conceitos aprendidos. Vamos em frente!
Conecte-se
Agora que você compreendeu sobre a operação de busca na árvore binária, chegou a hora
de conhecer alguns exemplos. Veja-os a seguir!
de conhecer alguns exemplos. Veja-os a seguir!
Por meio das imagens visualizadas você pôde compreender bem o assunto tratado, contudo, é relevante
complementar esse conhecimento para potencializar sua aprendizagem. Veja a seguir!
Muito aprendizado até aqui! A partir de agora vamos aplicar os conceitos aprendidos sobre a árvore binária.
Prossiga!
O estudo deste OVA permitiu compreender sobre essa estrutura
de dados: a árvore binária.
Agora é só aplicar esse conhecimento
em sua prática!
de dados: a árvore binária.
Agora é só aplicar esse conhecimento
em sua prática!
Pense a respeito!
SCHILDT, Herbert. C completo e total.
3. ed., rev., atualiz. São Paulo: Makron Books, 1996. 827 p.
TENENBAUM, Aaron M.; LANGSAM, Yedidyah; AUGENSTEIN, Moshe J. Estruturas de dados usando C. São Paulo: Pearson Education, 1995. 825 p. ISBN 85-346-0348-0.
TENENBAUM, Aaron M.; LANGSAM, Yedidyah; AUGENSTEIN, Moshe J. Estruturas de dados usando C. São Paulo: Pearson Education, 1995. 825 p. ISBN 85-346-0348-0.
Referências
Operação de busca
Assista ao vídeo a seguir para conhecer
mais sobre operação de busca.
Clique no play e confira!
mais sobre operação de busca.
Clique no play e confira!
Caso o CPF seja igual ao pesquisado, retorna o elemento Pessoa dentro do nó. Caso não, continuamos chamando as
funções de modo recursivo. É possível implementar as operações da Árvore de Busca de modo iterativo,
utilizando loops
Pessoa* busca(node * no, int cpf){"{"}
node * aux = no;
if (aux->pessoa.cpf == cpf)
return aux->pessoa;
if (valor < aux->pessoa.cpf)
return busca(no->esquerda, cpf);
if (valor > aux->valor)
return busca(no->direita, cpf);
return NULL;
}
node * aux = no;
if (aux->pessoa.cpf == cpf)
return aux->pessoa;
if (valor < aux->pessoa.cpf)
return busca(no->esquerda, cpf);
if (valor > aux->valor)
return busca(no->direita, cpf);
return NULL;
}
Não podemos inserir com base no identificador e remover com base no CPF, ou ainda, buscar com base no RG.
Por sinal, RG não seria um número ideal para isso, pois ele não é único no território nacional (pelo menos
ainda não).
Ao encontrar um elemento com o ID ou CPF desejado, eu retorno esse elemento do tipo Pessoa. Veja o código para entender como seria:
Ao encontrar um elemento com o ID ou CPF desejado, eu retorno esse elemento do tipo Pessoa. Veja o código para entender como seria:
Temos um registro com vários atributos como uma pessoa, e buscamos com um identificador ou um CPF. Basta que o
campo a ser pesquisado seja ordenável e utilizado para inserção, remoção e busca.
Logicamente que em um exemplo real não teremos árvores de número e pesquisamos números, salvo quando queremos
saber se um dado está na árvore ou não. Porém, de modo geral, considere esse exemplo:
node * busca(node * no, int valor){"{"}
node * aux = no;
if (aux->valor == valor)
return aux;
if (valor < aux->valor)
return busca(no->esquerda, valor);
if (valor > aux->valor)
return busca(no->direita, valor);
return NULL;
}
node * aux = no;
if (aux->valor == valor)
return aux;
if (valor < aux->valor)
return busca(no->esquerda, valor);
if (valor > aux->valor)
return busca(no->direita, valor);
return NULL;
}
Logo, na busca não precisamos ir para os dois lados à procura de um valor. Se a inserção foi implementada de
modo correto, sabemos para que lado devemos ir apenas comparando o valor desejado com o valor do nó atual.
Veja o código a seguir:
Veja o código a seguir:
Nó com valor maior fica à direita
Nó com valor menor fica à esquerda
Vamos analisar como funcionam as operações de busca dentro da árvore binária. Já sabemos o funcionamento da
árvore binária, que é:
Operação de
Busca na Árvore
Busca na Árvore
Seção interativa
Clique a seguir, leia as questões e indique se o que se afirma é verdadeiro ou falso. Desafie-se e sucesso!
Verifique seus conhecimentos sobre Árvore Binária!
Questão 1. A árvore binária só pode ser implementada de modo recursivo.
Questão 2. Em uma árvore binária, o método recursivo de busca tem o seu ponto de parada quando o nó atual
possui o valor pesquisado.
Questão 3. Quanto ao ponto de parada do método recursivo de busca, podemos dizer que - caso o item não
esteja na árvore - o ponto de parada ocorre ao chegar em um nó folha que não é o elemento desejado.
Verdadeiro
Falso
Verdadeiro
Falso
Verdadeiro
Falso
Muito bem! Neste caso, será retornado um valor NULL.
Não foi dessa vez! Analise o método e verifique em qual situação o valor NULL é retornado.
Muito bem! Na árvore binária, ao encontrar o nó com o valor pesquisado é retornado o próprio nó.
Não foi dessa vez! Na árvore binária, ao encontrar o nó com o valor pesquisado é retornado o próprio nó.
Não foi dessa vez! Os métodos da árvore binária podem ser implementados de modo iterativo.
Parabéns! Os métodos da árvore binária podem ser implementados de modo iterativo.
Início
Próximo
Voltar
Próximo
Voltar
Próximo
Voltar
Próximo
Voltar
Próximo
Voltar
Próximo
Voltar
Próximo
Voltar
Próximo
Voltar
Próximo
Voltar
Próximo
Voltar
Próximo
Voltar
Próximo
Voltar
Próximo
Voltar
Próximo
Voltar
Próximo
Voltar
Próximo
Voltar
Próximo
Voltar
Próximo
Voltar
Próximo
Voltar
Seção interativa
Classes assintóticas
A seguir você irá visualizar as classes assintóticas. Portanto, clique a seguir em “Começar”, leia a tela e
avance para visualizar as demais.
Começar
