Árvores binárias de pesquisa

Árvores de Pesquisa
● Estrutura de dados muito eficiente para armazenar informação.

● Adequada quando existe necessidade de considerar todos ou alguma combinação de: o o o o Acesso direto e sequencial eficientes. Facilidade de inserção e retirada de registros. Boa taxa de utilização de memória. Utilização de memória primária e secundária.

Anna Tostes | annatostes at gmail.com

LC2 | Árvores Binárias de Pesquisa

Árvores de Pesquisa
● Para qualquer nó que contenha um registro:

● Tem-se a relação invariante:

o Todos os registros com chaves menores estão na sub árvore à esquerda. o Todos os registros com chaves maiores estão na sub árvore à direita.

Anna Tostes | annatostes at gmail.com

LC2 | Árvores Binárias de Pesquisa

Árvores de Pesquisa sem balanceamento

● O nível do nó raiz é 0. ● Se um nó está no nível i então a raiz de suas sub árvores estão no nível i + 1. ● A altura de um nó é o comprimento do caminho mais longo deste nó até um nó folha. ● A altura de uma árvore é a altura do nó raiz.
Anna Tostes | annatostes at gmail.com LC2 | Árvores Binárias de Pesquisa

TAD Dicionário usando Árvore Binária de Pesquisa
● Estrutura de dados: o Contém as operações

 Inicializa  Pesquisa  Insere  retira. o A operação inicializa é implementada pelo construtor da classe ArvoreBinaria.

Anna Tostes | annatostes at gmail.com

LC2 | Árvores Binárias de Pesquisa

TAD Dicionário usando Árvore Binária de Pesquisa class ArvoreBinaria { private class No { public int reg; public No esq, dir; } private No raiz; public ArvoreBinaria() { this.raiz = null; } public int pesquisa(int reg) { return this.pesquisa(reg, this.raiz); }
Anna Tostes | annatostes at gmail.com LC2 | Árvores Binárias de Pesquisa

public void insere(int reg) { this.raiz = this.insere(reg, this.raiz); } public void retira(int reg) { this.raiz = this.retira(reg, this.raiz); }

Método para Pesquisar na Árvore
● Para encontrar um registro com uma chave reg: