Árvores Binárias de Pesquisa
Árvore Binária
• Definição:
– Estrutura de dados encadeada de nodos
– Acíclica
– Cada nodo pode apontar para 0, 1 ou 2 outros
nodos
– Em uma árvore não vazia existe um nodo
distinto chamado raiz.
Arvore Binária
• Definição
– Cada nodo de uma árvore binária inicia uma
nova árvore.
– As árvores apontadas pelo nodo raiz são
chamadas de sub-árvore esquerda e sub-árvore
direita
Árvore Binária
raiz
Árvore Binária
• Definições
– Os nodos para os quais um nodo (nodo pai)
aponta são ditos nodos filhos (esquerdo e
direito).
– Nodo Folha: Nodo da árvore que não possui
nenhum filho.
– A profundidade de um nodo é a distância deste
nodo até a raiz.
Árvore Binária
• Definições
– Um conjunto de nodos com a mesma
profundidade é denominado nível da árvore.
– Altura de uma árvore binária:
• Comprimento do caminho entre o nodo raiz e o
nodo folha mais distante da raiz.
• Ou seja é a profundidade do nodo mais profundo.
Árvore Binária de Busca
• Definição
– Árvore binária onde:
• Os nodos possuem uma chave de busca única.
• os elementos da sub-arvore esquerda são menores
que o elemento do nodo raiz e os elementos da subárvore direita são maiores que a do nodo raiz
(considerando a chave de busca) .
Árvore binária de Busca
raiz
5
3
2
7
4
6
8
O TAD Árvore binária de busca
• Operações:
– Inicializa: Cria a árvore vazia (a referência
para a raiz é NULL)
– Pesquisa: Tenta recuperar um elemento
existente na árvore dada uma chave de
pesquisa.
– Insere: Insere um elemento na árvore
– Remove: Remove um elemento da árvore dada
uma chave de pesquisa.
Implementação
// definição do tipo
typedef struct {
int valor;
int chave;
} registro;
typedef struct nodo {
registro reg;
struct nodo *esq,*dir;
}nodo;
typedef nodo* arvore;
Implementação
• Operações:
void inicializa(arvore *t);
void insere(arvore *t, registro r);
registro pesquisa(arvore *t, int x);
void retira(arvore *p, int x);
Implementação
Inicializa:
Faz a raiz apontar para nulo
void inicializa(arvore *t){
*t=NULL;
}
Implementação
void insere(arvore *t, registro r){
if (*t==NULL){
*t= malloc(sizeof(nodo));
(*t)->dir=NULL;
(*t)->esq=NULL;
(*t)->reg=r;
}
else
Implementação
if (r.chave<(*t)->reg.chave) {
insere(&(*t)->esq,r);
}
else
if (r.chave>(*t)->reg.chave)
{
insere(&(*t)->dir,r);
}
else
printf("Ja existe um nodo
com esta chave!");
}
Implementação
registro pesquisa(arvore *t, int x){
if (*t==NULL) {
printf("Não existe este elemento\n");
return (registro) {0,0};
}
if (x<(*t)->reg.chave) {
return pesquisa(&(*t)->esq,x);
}
if (x>(*t)->reg.chave) {
return pesquisa(&(*t)->dir,x);
}
return (*t)->reg;
}
Implementação
void antecessor(arvore q, arvore *r) {
if ( (*r)->dir != NULL) {
antecessor(q,&(*r)->dir);
}
else {
q->reg=(*r)->reg;
q = *r;
*r= (*r)->esq;
free(q);
}
}
Implementação
void retira(arvore *p, int x) {
arvore aux;
if ((*p) == NULL) {
printf(“registro não existente\n");
}
else
if ( x< (*p)->reg.chave) {
retira(&(*p)->esq,x);
}
else
if (x> (*p)->reg.chave) {
retira(&(*p)->dir,x);
}
Implementação
else
if ((*p)->esq==NULL){
aux = *p;
*p = (*p)->dir;
free(aux);
}
else
if ((*p)->dir==NULL){
aux = *p;
*p = (*p)->esq;
free(aux);
}
else {
antecessor(*p,&(*p)->esq);
}
}