Estrutura de Dados
Gostaria de reagir a esta mensagem? Crie uma conta em poucos cliques ou inicie sessão para continuar.

Ir para baixo
avatar
LeonardoFaria
Admin
Admin
Mensagens : 4
Pontos : 19
Reputação : 1
Data de inscrição : 05/05/2017

Arvore Binária de Busca Empty Arvore Binária de Busca

Sáb Nov 25, 2017 11:32 am
Árvores binárias de busca

Assim como árvores binárias generalizam a ideia de listas encadeadas, árvores binárias de busca (= binary search trees = BSTs) generalizam a ideia de listas encadeadas crescentes.

Definição:
Considere uma árvore binária cujos nós têm um campo chave de um tipo linearmente ordenado, um tipo (como int, char, string, etc.) que admite comparação. Suporemos que chaves são do tipo int e portanto os nós têm a seguinte estrutura:

typedef struct reg {
 int         chave;
 int         conteudo;
 struct reg *esq, *dir;
} noh; // nó

Uma árvore binária deste tipo é de busca se cada nó p tem a seguinte propriedade:
A chave de p é  maior ou igual à chave de qualquer nó na subárvore esquerda de p  e  menor ou igual à chave de qualquer nó na subárvore direita de p.   Em outras palavras, se p é um nó qualquer então

obs: p = é a raiz da arvoré

e->chave   ≤   p->chave   ≤   d->chave

para todo nó e na subárvore esquerda de p e todo nó d na subárvore direita de p.  

Arvore Binária de Busca 300px-10








Ir para o topo
Permissões neste sub-fórum
Não podes responder a tópicos