- LeonardoFariaAdmin
- Mensagens : 4
Pontos : 19
Reputação : 1
Data de inscrição : 05/05/2017
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.
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.
Permissões neste sub-fórum
Não podes responder a tópicos
|
|