Estruturas de Dados 2005/2006
62
Propriedades de Árvores Binárias
Propriedade 1:Uma árvore binária com N nós internos tem, no máximo, N+1 folhas
Demonstração: (Indução Matemática no número de nós)
N=0 : Trivial!
N = m : Hipótese de indução – Uma árvore binária com m nós internos tem, no
máximo, m + 1 folhas
N > 0 : Uma árvore binária, T , com N nós internos terá k deles na sub–árvore esquerda
(0 ≤ k ≤ N − 1) e N − k − 1 na sub–árvore direita.
Usando a hipótese de indução, a sub–árvore esquerda possui 0 ≤ ne ≤ k + 1 folhas e a
sub–árvore direita possui 0 ≤ nd ≤ N − k.
Assim, temos, para o número de folhas de T ,
nt = ne + nd ⇐⇒ 0 ≤ nt ≤ (k + 1) + (N − k) ⇐⇒ 0 ≤ nt ≤ N + 1
Estruturas de Dados 2005/2006
63
Propriedades de Árvores Binárias – Cont.
Propriedade 2: Uma árvore binária completa de altura h tem, exactamente, 2h+1 − 1 nós
Demonstração: (Indução Matemática na altura)
Propriedade 3: O número máximo de nós de uma árvore binária de altura h é 2h+1 − 1.
Demonstração: 1 + 2 + 22 + . . . + 2h = 2h+1 − 1
q.e.d.
Estruturas de Dados 2005/2006
64
Propriedades de Árvores Binárias – Cont. da cont.
Qual a altura mı́nima de uma árvore binária com N nós?
Seja h t.q. N ≤ 2h+1 − 1
1. Nenhuma árvore binária com altura inferior a h pode ter N nós.
2. Existe uma árvore binária de altura h com, exactamente, N nós.
3. Logo, h assim definido é a altura mı́nima para uma árvore binária possuir N nós:
N ≤ 2h+1 − 1 =⇒ h ≥ log2 (N + 1) − 1
Propriedade 4:
A altura mı́nima para uma árvore binária com N nós é blog2 (N + 1)c
Estruturas de Dados 2005/2006
65
Árvores Binárias de Pesquisa
#ifndef _SearchBTree_h
#define _SearchBTree_h
typedef struct elemSBT{
Item valor;
struct elemSTB *fesq, *fdir;
} ElemArvP, *ArvPesq;
ArvPesq criar();
ArvPesq procura(Item X, ArvPesq T);
ArvPesq minimo(ArvPesq T);
ArvPesq maximo(ArvPesq T);
void
inserir(Item val, ArvPesq *T);
void
remover(Item val, ArvPesq *T);
Item
consulta(ArvPesq T);
#endif
Estruturas de Dados 2005/2006
Árvores Binárias de Pesquisa – continuação
ArvPesq criar()
{/* Cria uma arv. de pesq. vazia */
return NULL;
}
int vazia(ArvPesq T)
{/* devolve True(1) sse T e’ vazia */
return T ? 0 : 1;
}
ArvPesq procura(Item X, ArvPesq T)
{/* procura em T vertice com X */
if( vazia(T) )
return NULL;
if( X < T->valor)
return procura(X, T->fesq);
if( X > T->valor)
return procura(X, T->fdir);
else return T;
}
66
Estruturas de Dados 2005/2006
Árvores Binárias de Pesquisa – parte III
ArvPesq minimo(ArvPesq T)
{/* procura o vertice com valor minimo */
if( vazia(T) )
return NULL;
else if( vazia(T->fesq) )
return T;
else return minimo(T->fesq);
}
ArvPesq maximo(ArvPesq T)
{/* procura o vertice com valor maximo */
if( !vazia(T) )
while( !vazia(T->fdir) )
T = T->fdir;
return T;
}
67
Estruturas de Dados 2005/2006
Árvores Binárias de Pesquisa – Inserir
void inserir(Item val, ArvPesq *T);
{/* insere o vertice com valor val (se nao existir) */
if( vazia(*T) )
*T = novo_no(val); // novo no’ com valor val e ponts nulos
else if( val < (*T)->valor )
inserir(val, &(*T)->fesq);
else if( val > (*T)->valor )
inserir(val, &(*T)->fdir);
// senao val ja’ existe em T
}
68
Estruturas de Dados 2005/2006
69
Árvores Binárias de Pesquisa – Remover
void remover(Item val, ArvPesq *T);
{ ArvPesq aux, minimo();
Item consulta();
/* remove o vertice com valor val */
if(!vazia(*T))
if(val < (*T)->valor)
remover(val, &((*T)->fesq));
else if(val > (*T)->valor)
remover(val, &((*T)->fdir));
else
// encontrou
if( !vazia((*T)->fesq) && !vazia((*T)->fdir) )
{
aux = minimo((*T)->fdir);
(*T)->valor = consulta(aux);
remover((*T)->valor, (*T)->fdir);
}
else{
aux = *T;
if(vazia((*T)->fesq))
*T = (*T)->fdir;
else *T = (*T)->fesq;
Libertar(aux);
}
}