Árvore binária vermelho e preto

Árvores de Pesquisa Binária

e

Árvores Vermelho-Preto

ALUNO: Alessandro M. de Camargo

Trabalho da disciplina Estrutura de Dados do Programa de Pós-Graduação em Ciência da Computação, da Universidade Estadual Paulista ministrada pela professora Roberta Spolon.

Árvores de Pesquisa Binária

É uma estrutura de dados organizada que permitem operações de conjuntos dinâmicos.
A altura de uma árvore é uma medida do tempo necessário para encontrar um dado nó.
Numa árvore binária, cada nó tem zero, um ou dois filhos onde o nó raiz tem o campo pai NIL.
Cada nó pode conter estrutura de dados a esquerda e estrutura de dados a direita satisfazendo sempre à propriedade de árvore de pesquisa binária: filhos de menor valor ficam à esquerda do nó (pai) e os filhos de maior valor ficam à direita do nó (pai).

Exemplo da Estrutura:

[pic]

Exemplo de uma Arvore Binária
[pic]

Nota-se que os nós que estão a direita tem sempre número de chave maior e os nós ‘pai’ e os que estão na esquerda tem sempre numero de chave menor que a chave ‘pai’.

É possível executar várias operações em uma árvore de pesquisa binária, em operações de consulta, onde podemos percorrer a arvore em busca de uma determinada chave, é possível (através de algoritmos definidos), além de encontrar uma chave, retornar as chaves de menor valor, de maior valor, inserção e eliminação.

- Pesquisar: dado um ponteiro para a raiz da arvore e uma chave k, inicia-se a partir da raiz um caminho descendente. Para cada nó encontrado é comparado o valor e sua chave com k,se for igual a pesquisa termina, caso k seja maior a pesquisa continua na sub-árvore da direita e se for menor na sub-árvore da esquerda;

Valor mínimo: encontrado partindo da raiz e percorrendo as sub-árvores da esquerda até ser encontrado o valor NIL;

Valor mínimo: encontrado partindo da raiz e percorrendo as sub-árvores da direita até ser encontrado