Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » Algoritmos e Estruturas de Dados - Curso Intermediário » Árvores binárias de pesquisa

Navigation

Table of Contents

  • Árvores balanceadas

    • Árvores binárias de pesquisa

Recently Viewed

This feature requires Javascript to be enabled.
 

Árvores binárias de pesquisa

Module by: Andre Campos. E-mail the author

Summary: Este módulo apresenta os conceitos iniciais de árvores binárias de pesquisa. Ele inclui algoritmos de busca, inserção e remoção.

Árvores de pesquisa

Ah! este parágrafo é necessário para que a seção tenha algo a dizer. Vejam! e a fonte é diferente!

Suponha que você tenha um conjunto de elementos a armazenar no seu computador, de forma que possa realizar inúmeras buscas sobre esses elementos. Suponha agora que você utilize, como estrutura de dados para armazenar esses elementos, uma lista encadeada. Como vocês devem lembrar, a complexidade de busca em uma lista encadeada é (no pior caso) O(n), onde n é o número de elementos da lista. Isso ocorre porque precisamos percorrer a lista, no pior caso (caso onde o elemento a ser procurado se encontra no final da lista), do início (cabeça da lista) até o final. E se pudéssemos dar “saltos” nessa procura?

Claro que podemos dar “saltos” em uma procura. Alias, essa é a forma natural de otimizar processos. Para melhor visualizar esse processo, imagine uma busca de um número no intervalo de 0 a 100. Ao invés de iniciar sua busca no 0 e se estender até o 100, você pode testar o médio, 50, e verificar se o número a ser encontrado é maior ou menor. Se for menor, podemos então desprezar todos os números acima de 50 e recomeçar a busca no intervalo de 0 a 50. Esse procedimento deverá se repetir até que o número correspondente seja encontrado. Esse procedimento gerou implicitamente uma árvore de busca, conforme ilustrado na figura .

Figure 1
para todo vértice além-mar faça com

Responda a pergunta do exercício para melhor fixar seu conteúdo.

Glossary

Árvore binária estrita:
Árvore binária onde cada nó não-folha possui os dois filhos

References

  1. André Campos. (2002). Algoritmos e estruturas de dados em Java.

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks