Arvore Binaria

Árvore Binária de Busca

319

Árvore Binária de Busca


construída de tal forma que, para cada nó:






nós com chaves menores estão na sub-árvore esquerda nós com chaves maiores (ou iguais) estão na sub-árvore direita

a inserção dos nós da árvore deve satisfazer a essa propriedade
320

Árvore Binária de Busca


para a busca de uma chave v na árvore binária de busca:
 primeiro compare com a raiz





se menor, vá para a sub- árvore esquerda se maior, para a sub-árvore direita

aplique o método recursivamente

321

Árvore Binária de Busca
6
4
3

9
5

8

10

2

322

Árvore Binária de Busca




a cada passo, garante-se que nenhuma outra parte da árvore contém a chave sendo buscada o procedimento pára quando



o nó com v é encontrado senão, chega-se a NULL

323

Árvore Binária de Busca busca_arvore_nao_recursivo (v, pt)
{
do { if (v < pt->info) pt = pt-> esq; else pt = pt-> dir;
}while (pt != NULL) && (v != pt->info); return(pt); }
324

Inserindo em Árvore Binária de Busca


Para inserir um nó na árvore:




fazer uma busca com insucesso alocar um novo nó é necessário saber por qual nó se chegou a NULL
 será o pai do novo nó

325

Inserindo em Árvore Binária de Busca
6
4
3

2

9
5

8

10

Inserindo o 9

326

Inserindo em Árvore Binária de Busca
6
4
3

9
5

8

10

7
2

Inserindo o 7

327

Inserção Árvore Binária de Busca insere_árvore (int valor, tipo_nó * pt)
{ tipo_nó * pai; do{ pai = pt ; if (valor < pt->chave) pt = pt ->esq ; else if ( valor > pt-> chave) pt = pt->dir;
} while(pt != NULL) && (pt->chave != valor); if (pt == NULL){ pt = aloca(); pt ->chave = valor; pt->esq = NULL; pt->dir = NULL; if (v < pai->chave) pai ->esq = pt ; else pai ->dir = pt ; return(pt); }
}
328

Inserção Árvore Binária de Busca


a árvore está classificada se percorrida da
forma