Árvores binárias

FACULDADE PITÁGORAS DE LONDRINA

MATHEUS S. MENEGAZZO

TRABALHO DE PROGRAMAÇÃO

LONDRINA
2012

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. O objetivo desta árvore é estruturar os dados de forma flexível, permitindo pesquisa binária.

Nós - são todos os itens guardados na árvore;
Raiz - é o nó do topo da árvore (no caso da figura acima, a raiz é o nó 8);
Filhos - são os nós que vem depois dos outros nós (no caso da figura acima, o nó 6 é filho do 3);
Pais - são os nós que vem antes dos outros nós (no caso da figura acima, o nó 10 é pai do 14);
Folhas - são os nós que não têm filhos; são os últimos nós da árvore (no caso da figura acima, as folhas são 1, 4, 7 e 13).
A operação de busca em uma árvore binária por um determinado valor, pode ser feita de maneira recursiva ou interativa. (fiz a abordagem recursiva).
A busca inicia-se no nó raiz, se o valor contido na raiz não for o desejado, verificamos se o valor é maior ou menor que o nó raiz. Caso o valor seja menor que o nó raiz, a busca continua pelo seu filho menor, ou seja, pelo filho da esquerda, mas, caso o valor seja maior a busca continua pelo filho da direita, até que se encontre o valor desejado ou a busca chegue em um nó folha (valor não encontrado).
A inserção de um novo valor é praticamente uma busca na árvore pois, precisamos percorrer toda a árvore até chegarmos em um nó folha correspondente. Se o valor a ser inserido for maior que o raiz, seguimos pelo filho da direita, se for menor seguimos pelo filho da esquerda, até chegarmos em um nó que mantenha a ordenação da árvore.
A operação remoção começa a complicar um pouco. Temos 3 casos diferentes:
Exclusão de um nó folha;
Exclusão de um nó com 1 filho;