Compartilhe
Ver o tópico anteriorIr em baixoVer o tópico seguinte
Admin
Admin
Mensagens : 4
Pontos : 19
Reputação : 1
Data de inscrição : 05/05/2017
Ver perfil do usuário

Arvore Binária de Busca

em Sab 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.  










Ver o tópico anteriorVoltar ao TopoVer o tópico seguinte
Permissão deste fórum:
Você não pode responder aos tópicos neste fórum