Binario

Á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 5 9

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 5 9

8

10

2

Inserindo o 9

326

Inserindo em Árvore Binária de Busca
6 4 3 5 7 2 9

8

10

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 correta (pre, pos ou em-ordem?)


as chaves aparecem em