• Árvore Binária de Busca

  • INFO:

  • HUB

  • 1/1

Informações da Estrutura
Estrutura de Dados

EstruturaArvore

{

  info : inteiro;

  direita : EstruturaArvore;

  esquerda : EstruturaArvore;

}

Raiz : EstruturaArvore;

Descrição
"Uma árvore binária é um conjunto finito de elementos que está vazio ou é particionado em três subconjuntos disjuntos. O primeiro subconjunto contém um único elemento, chamado raiz da árvore. Os outros dois subconjuntos são em si mesmos árvores binárias, chamadas subárvores esquerda e direita da árvore original. Uma subárvore esquerda ou direita pode estar vazia. Cada elemento de uma árvore binária é chamado nó da árvore. " (Tenenbaum)

Mais informações
Implementação: Realizada por meio de registros (em C, struct)

Regras: Elemento com valor maior ao do nó, é adicionado a subárvore da direita, caso o valor seja menor é adicionado a subárvore da esquerda.

Aplicação: Ilustração de problemas em estruturas implementadas em árvore, do algoritmo de busca binária e recursividade.

Requisitos para aplicação: A inserção não pode ser em ordem crescente, ou decrescente, pois a árvore ficará desbalanceada rapidamente e se tornará uma lista encadeada, e o armazenamento não deve ser realizado em arquivo (problemas de fragmentação).

Em relação a outras formas de implementação de Árvore
  • Vantagem: A implementação é a mais simples.
  • Desvantagem: A árvore não trata desbalanceamento, o que pode, no pior caso, se transformar em uma lista encadeada, onde a busca ocorre em ordem linear. Além disso, quando é implementado em arquivo pode resultar em fragmentação.
FUNÇÃO
Insere(INFO,ArvoreNo)

Se ArvoreNo != nulo então

INICIO

Se ArvoreNo.info > INFO então

Insere(INFO,ArvoreNo.esquerda);

Senão se ArvoreNo.info < INFO então

Insere(INFO,ArvoreNo.direita);

Senão

Retornar;

FIM

Senão

INICIO

ArvoreNo := alocar();

ArvoreNo.info := INFO;

ArvoreNo.esquerda := nulo;

ArvoreNo.direita := nulo;

FIM

FUNÇÃO
Remove(INFO,ArvoreNo)

Se ArvoreNo != nulo e ArvoreNo.info != INFO então

INICIO

Se ArvoreNo.info < INFO então

Remove(INFO,ArvoreNo.direita);

Senão se ArvoreNo.info > INFO então

Remove(INFO,ArvoreNo.esquerda);

FIM

Senão se ArvoreNo != nulo então

INICIO

Rem : EstruturaArvore;

Rem := ArvoreNo;

 

Se ArvoreNo.direita == nulo então

ArvoreNo := ArvoreNo.esquerda;

Senão se ArvoreNo.esquerda == nulo então

ArvoreNo := ArvoreNo.direita;

Senão

INICIO

Sucessor : EstruturaArvore;

Sucessor := ArvoreNo.direita;

 

Enquanto Sucessor.esquerda != nulo faça

Sucessor := Sucessor.esquerda;

 

ArvoreNo.info := Sucessor.info;

Sucessor := Sucessor.direita;

Rem := Sucessor;

FIM

 

Liberar(Rem);

FIM

FUNÇÃO
Busca(INFO,ArvoreNo)
RETORNA
Se o valor está na Árvore

Se ArvoreNo != nulo então

INICIO

Se ArvoreNo.info > INFO então

Busca(INFO,ArvoreNo.esquerda);

Senão se ArvoreNo.info < INFO então

Busca(INFO,ArvoreNo.direita);

Senão

Retornar Verdadeiro;

FIM

Senão

Retornar Falso;

Última animação

Nenhuma animação disponível para revisar!

Executando animação ...

Aguarde encerrar !

Última animação que foi executada:

# Descrição
Entradas Programadas

Configurações

Entradas

Limpar entrada ao final da animação

Chance de gerar número negativo na entrada aleatória:

50%

Estrutura

Ocultar Ponteiros Nulos

Impedir inserção de valores repetidos

Mostrar Descritores

Cor do componente primário

Cor do componente secundário

Código

Usar delimitador em chaves

Contar linhas brancas

Configurações serão salvas para este navegador
Histórico
    • #
    • INFO
    • Vazio
Principal
Menu das Estruturas

  • Pseudo-código

  • Informações da Estrutura

  • Entradas Programadas

  • Rever Passos

  • Histórico

Árvore Binária de Busca

  • Vazio
Logo

Estruturas

Listas

Sem ordenação

Simples

Dupla

Com ordenação

Simples

Dupla

Estática

Cruzada

Filas

Estáticas

Simples

Circular

Dinâmicas

Normal

Com Prioridade

Circular

Pilhas

Estáticas

Simples

Múltipla

Dinâmicas

Simples

Hashing

Sem Tratamento

Simples

Com Tratamento

Listas Encadeadas

Área de Overflow

Árvores

Balanceadas

AVL

Rubro-Negra

B

Não Balanceadas

Binária

Trie

Patricia
Histórico

Lista Ordenada Simples

Lista Ordenada Estática

Lista Ordenada Dupla

Lista Sem Ordenação Simples

Lista Sem Ordeneção Dupla

Lista Cruzada

Fila Estática

Fila Estática Circular

Fila com Prioridade

Fila Dinâmica

Fila Circular

Pilha Estática

Pilha Múltipla

Pilha Dinâmica

Hash sem Tratamento

Hash com Tratamento

Hash com Overflow

Árvore AVL

Árvore B

Árvore RubroNegra

Árvore Binária

Árvore Trie

Árvore Patricia

Estrutura não encontrada