A Árvore Binaria de Busca

Universidade Paulista – Unip

Campus – Manaus

Instituto de Ciências Exatas e Tecnologicas - ICET

Ciência da Computação

Árvore Binaria de Busca

Manaus

2017

Grupo:

Jamison Lopes Rossete Moraes - RA: D12975-9

Paulo Oliveira Siqueira Júnior - RA: D001GB-3

Matheus Alves Barros - RA: D11800-5

Marconi Gama - RA: D080644

Árvore Binaria de Busca

Trabalho solicitado pelo Professor Rildo Nogueira para a obtenção de nota na Atividade Pratica Supervisionada, do Curso de Ciência da Computação, da Universidade Paulista.

Manaus

2017

Introdução

Em Ciência da computação, uma árvore binária de busca (ou árvore binária de pesquisa) é uma estrutura de dados de árvore binária baseada em nós, onde todos os nós da subárvore esquerda possuem um valor numérico inferior ao nó raiz e todos os nós da subárvore direita possuem um valor superior ao nó raiz (esta é a forma padrão, podendo as subárvores ser invertidas, dependendo da aplicação), além disso, as árvores são um tipo especial de Grafo, ou seja, qualquer par de vértices esta conectado a apenas uma aresta, somado a isso, os grafos são conexos (existe exatamente um caminho entre quaisquer dois de seus vértices) e acíclicos (não possui ciclos).

[pic 1]

As arvores são representadas de duas formas, como a já citada, forma de grafos, que é a mais comum, e no formato de um diagrama de Venn, que usa círculos sobrepostos ou outras formas para ilustrar as relações lógicas entre dois ou mais conjuntos de itens.

[pic 2]

Existem vários tipos de Árvores em ciência da computação, desenvolvidas para diferentes tipos de aplicações, entre elas: árvore avl, árvore rubo-negra, árvore B+, árvore 2-3,2-3-4, quadtree, octree etc.

Em nosso trabalho trabalharemos com o tipo de Árvore AVL, e falaremos sobre a rotação simples.

ROTAÇÃO SIMPLES

        A operação básica em uma árvore AVL geralmente envolve os mesmos algoritmos de uma árvore de busca binária desbalanceada. A rotação na árvore AVL ocorre devido ao seu desbalanceamento, uma rotação simples ocorre quando um nó está desbalanceado e seu filho estiver no mesmo sentido da inclinação, formando uma linha reta.

Rotação para esquerda ocorre quando pelo menos três nós estiverem inclinados para a direita, pois todos os valores para a direita são maiores do que o pai:

Exemplo1:

     [pic 3]

Exemplo2:

[pic 4]

Ou seja, o valor do meio terá o pai sendo menor que ele, o pai terá que ser movido para a esquerda dele.

Enquanto a rotação para direita ocorre justamente o contrario, quando pelo menos três nós estiverem inclinados para a esquerda, todos os valores serão menores que o pai:

Exemplo3:

 [pic 5]

Exemplo4:

[pic 6]

Ou seja, o valor do meio terá o pai sendo maior que ele, o pai terá que ser movido para a direita dele.

BIBLIOGRAFIA

http://www.ufjf.br/jairo_souza/files/2009/12/5-Indexa%C3%A7%C3%A3o-Arvore-AVL.pdf

...