Aula 9 - abb

INE5408 Estruturas de Dados
Árvores Binárias de Busca - Características - Algoritmos
- Inserção, deleção e pesquisa

Introdução
Árvores (binárias) são muito utilizadas para se representar um grande conjunto de dados onde se deseja encontrar um elemento de acordo com a sua chave. Definição - Árvore Binária de Busca (Niklaus Wirth): “Uma árvore que se encontra organizada de tal forma que, para cada nodo ti, todas as chaves (info) da subárvore à esquerda de ti são menores que (ou iguais a) ti e à direita são maiores que ti”. Termo em Inglês: Search Tree.

Características
Em uma árvore binária de busca é possível encontrar-se qualquer chave existente descendo-se pela árvore:
– sempre à esquerda toda vez que a chave procurada for menor do que a chave do nodo visitado; – sempre à direita toda vez que for maior.

Características
A escolha da direção de busca só depende da chave que se procura e da chave que o nodo atual possui. A busca de um elemento em uma árvore balanceada com n elementos toma tempo médio < log(n), sendo a busca então O(log n). Graças à estrutura de árvore a busca poderá ser feita com apenas log(n) comparações de elementos.

Exemplo de árvore binária de busca
8 5 15 6

2

11 7

19

1

3

9

13

21

Algoritmo de busca tNodo* FUNÇÃO busca (chave: tInfo, ptr: *tNodo)

início enquanto (ptr ~= NULO E ptr->info ~= chave) faça // Esquerda ou direita. se (ptr->info < chave) então ptr <- ptr->filhoÀDireita senão ptr <- ptr->filhoÀEsquerda; fim se fim enquanto retorne ptr; fim

Algoritmo de inserção tNodo* FUNÇÃO inserção (raiz: *tNodo, info: tInfo) oNovo: *tNodo; início se (info < raiz->info) então // Inserção à esquerda. se (raiz->filhoÀEsquerda = NULO) então oNovo <- aloque(tNodo); oNovo->info <- info; oNovo->filhoÀEsquerda <- NULO; oNovo->filhoÀDireita <- NULO; raiz->filhoÀEsquerda <- oNovo; senão raiz <- inserção(raiz->filhoÀEsquerda, info); fim se senão // Inserção à direita. se (raiz->filhoÀDireita = NULO) então oNovo <- aloque(tNodo); oNovo->info <-