Estrutura de Dados - Implementação de Arvores Binárias em C++ Orientado à Gambiarra

Prévia do material em texto

Estrutura de Dados
Implementac¸a˜o de A´rvores Bina´rias
em C++ Orientado a` Gambiarra
Ronildo Oliveira da Silva
ro.nildooliveira@hotmail.com
1 A´rvore Bina´ria de Busca
1.1 Definic¸a˜o
Em Cieˆncia da computac¸a˜o, uma a´rvore bina´ria de busca (ou a´rvore bina´ria
de pesquisa) e´ uma estrutura de dados de a´rvore bina´ria baseada em no´s, onde
todos os no´s da suba´rvore esquerda possuem um valor nume´rico inferior ao no´
raiz e todos os no´s da suba´rvore direita possuem um valor superior ao no´ raiz
(esta e´ a forma padra˜o, podendo as suba´rvores serem invertidas, dependendo
da aplicac¸a˜o). O objetivo desta a´rvore e´ estruturar os dados de forma flex´ıvel,
permitindo busca bina´ria.
No´s Sa˜o todos os itens guardados na a´rvore;
Raiz E´ o no´ do topo da a´rvore;
Filhos Sa˜o os no´s que vem depois dos outros no´s, que esta˜o a baixo;
Pais Sa˜o os no´s que vem antes dos outros no´s, que esta˜o acima;
Folhas Sa˜o os no´s que na˜o teˆm filhos.
1.2 Busca
A busca em uma a´rvore bina´ria por um valor espec´ıfico pode ser um processo
recursivo ou iterativo.
A busca comec¸a examinando o no´ raiz. Se a a´rvore esta´ vazia, o valor procu-
rado na˜o pode existir na a´rvore. Caso contra´rio, se o valor e´ igual a raiz,
a busca foi bem sucedida. Se o valor e´ menor do que a raiz, a busca segue
1
pela suba´rvore esquerda. Similarmente, se o valor e´ maior do que a raiz, a
busca segue pela suba´rvore direita. Esse processo e´ repetido ate´ o valor ser
encontrado ou a suba´rvore ser nula (vazia). Se o valor na˜o for encontrado
ate´ a busca chegar na suba´rvore nula, enta˜o o valor na˜o deve estar presente
na a´rvore.
1.3 Inserc¸a˜o
A inserc¸a˜o comec¸a com uma busca, procurando pelo valor, mas se na˜o for en-
contrado, procuram-se as suba´rvores da esquerda ou direita, como na busca.
Eventualmente, alcanc¸a-se a folha, inserindo-se enta˜o o valor nesta posic¸a˜o.
Ou seja, a raiz e´ examinada e introduz-se um no´ novo na suba´rvore da es-
querda se o valor novo for menor do que a raiz, ou na suba´rvore da direita
se o valor novo for maior do que a raiz.
1.4 Exclusa˜o
A exclusa˜o de um no´ e´ um processo mais complexo. Para excluir um no´ de
uma a´rvore bina´ria de busca, ha´ de se considerar treˆs casos distintos para a
exclusa˜o:
1.4.1 Exclusa˜o na folha
A exclusa˜o na folha e´ a mais simples, basta removeˆ-lo da a´rvore.
1.4.2 Exclusa˜o de um no´ com um filho
Excluindo-o, o filho sobe para a posic¸a˜o do pai.
1.4.3 Exclusa˜o de um no´ com dois filhos
Neste caso, pode-se operar de duas maneiras diferentes. Pode-se substituir
o valor do no´ a ser retirado pelo valor sucessor (o no´ mais a` esquerda da
suba´rvore direita) ou pelo valor antecessor (o no´ mais a` direita da suba´rvore
esquerda), removendo-se a´ı o no´ sucessor (ou antecessor).
1.5 Percusso
Em uma a´rvore bina´ria de busca podem-se fazer os treˆs percursos que se
fazem para qualquer a´rvore bina´ria (percursos em inordem, pre´-ordem e po´s-
ordem). E´ interessante notar que, quando se faz um percurso em ordem
em uma a´rvore bina´ria de busca, os valores dos no´s aparecem em ordem
2
crescente. A operac¸a˜o ”Percorre” tem como objetivo percorrer a a´rvore numa
dada ordem, enumerando os seus no´s. Quando um no´ e´ enumerado, diz-se
que ele foi ”visitado”.
1.5.1 Pre´-ordem (Em Profundidade)
1. Visita a raiz;
2. Percorre a suba´rvore esquerda em pre´-ordem;
3. Percorre a suba´rvore direita em pre´-ordem.
1.5.2 Ordem Sime´trica (Em Ordem)
1. Percorre a suba´rvore esquerda em ordem sime´trica;
2. Visita a raiz;
3. Percorre a suba´rvore direita em ordem sime´trica.
1.5.3 Po´s-ordem
1. Percorre a suba´rvore esquerda em po´s-ordem;
2. Percorre a suba´rvore direita em po´s-ordem;
3. Visita a raiz.
2 A´rvore AVL
2.1 Balanceamento
Uma a´rvore AVL e´ dita balanceada quando, para cada no´ da a´rvore, a difer-
enc¸a entre as alturas das suas sub-a´rvores (direita e esquerda) na˜o e´ maior do
que um. Caso a a´rvore na˜o esteja balanceada e´ necessa´rio seu balanceamento
atrave´s da rotac¸a˜o simples ou rotac¸a˜o dupla. O balanceamento e´ requerido
para as operac¸o˜es de inserc¸a˜o e remoc¸a˜o de elementos. Para definir o bal-
anceamento e´ utilizado um fator espec´ıfico para no´s.
O fator de balanceamento de um no´ e´ dado pelo seu peso em relac¸a˜o a sua
suba´rvore. Um no´ com fator balanceado pode conter 1, 0, ou -1 em seu fator.
Um no´ com fator de balanceamento diferente dos citados e´ considerado uma
a´rvore na˜o AVL e requer um balanceamento por rotac¸a˜o ou dupla-rotac¸a˜o.
Para garantirmos essa propriedade a cada inserc¸a˜o ou remoc¸a˜o a diferenc¸a de
3
altura dos no´s afetados e dos no´s superiores deve ser recalculada de modo que
a altura do no´ que esta´ sendo recalculado seja igual a altura do no´ esquerdo
menos a altura do no´ direito.
2.2 Busca
Para buscarmos um no´ basta comparar o seu valor com o valor do no´ que esta´
sendo analisado (raiz no caso da primeira iterac¸a˜o). Se o valor buscado for
menor que o valor do no´ que esta´ sendo analisado devemos efetuar a busca
no filho da esquerda do no´ atual, caso contra´rio deveremos efetuar a busca
no filho da direita do no´ atual. Se o no´ na˜o for encontrado com essa busca
podemos ter certeza que ele na˜o existe dentro da a´rvore.
2.3 Inserc¸a˜o
Para inserirmos um novo no´ de valor K em uma a´rvore AVL e´ necessa´ria
uma busca por K nesta mesma a´rvore. Apo´s a busca o local correto para a
inserc¸a˜o do no´ K sera´ encontrado. Depois de inserido o no´, a altura do no´
pai e de todos os no´s acima deve ser atualizada. Em seguida o algoritmo de
rotac¸a˜o deve ser acionado para o no´ pai e depois para todos os no´s superiores
caso um desses no´s caia em uma das condic¸o˜es de rotac¸a˜o.
2.4 Remoc¸a˜o
Para removermos um no´ de valor K na a´rvore, devemos buscar K nesta
a´rvore e, caso K seja folha da a´rvore, apenas deleta´-lo. Caso K pertenc¸a a`
a´rvore, mas na˜o seja uma folha da a´rvore devemos substituir o valor de K
com o valor mais pro´ximo poss´ıvel menor ou igual a K pertencente a` a´rvore.
Para encontrar este valor basta percorrer a suba´rvore da direita do filho da
esquerda de K, ate´ encontrarmos o maior valor M desta suba´rvore. O valor
de K sera´ substitu´ıdo por M , K sera´ deletado da a´rvore e caso M tenha um
filho a` esquerda esse filho ocupara´ sua antiga posic¸a˜o na a´rvore.
2.5 Rotac¸a˜o
A operac¸a˜o ba´sica em uma a´rvore AVL geralmente envolve os mesmos algo-
ritmos de uma a´rvore de busca bina´ria desbalanceada. A rotac¸a˜o na a´rvore
AVL ocorre devido ao seu desbalanceamento, uma rotac¸a˜o simples ocorre
quando um no´ esta´ desbalanceado e seu filho estiver no mesmo sentido da
inclinac¸a˜o, formando uma linha reta. Uma rotac¸a˜o-dupla ocorre quando um
no´ estiver desbalanceado e seu filho estiver inclinado no sentido inverso ao
4
pai, formando um ”joelho”.
Para garantirmos as propriedades da a´rvore AVL rotac¸o˜es devem ser feitas
conforme necessa´rio apo´s operac¸o˜es de remoc¸a˜o ou inserc¸a˜o. Seja P o no´ pai,
FE o filho da esquerda de P e FD o filho da direita de P podemos definir 4
tipos diferentes de rotac¸a˜o:
2.5.1 Rotac¸a˜o a` direita
Deve ser efetuada quando a diferenc¸a das alturas h dos filhos de P e´ igual
a 2 e a diferenc¸a das alturas h dos filhos de FE e´ igual a 1. O no´ FE deve
tornar o novo pai e o no´ P deve se tornar o filho da direita de FE.
• Seja Y o filho a` esquerda de X
• Torne o filho a` direita de Y o filho a` esquerda de X.
• Torne X o filho a` direita de Y
2.5.2 Rotac¸a˜o a` esquerda
Deve ser efetuada quando a diferenc¸a das alturas h dos filhos de P e´ igual a
-2 e a diferenc¸a das alturas h dos filhos de FD e´ igual a -1. O no´ FD deve
tornar o novo pai e o no´ P deve se tornar o filho da esquerda de FD.
• Seja Y o filho a` direita de X
• Torne o filho a` esquerda deY o filho a` direita de X.
• Torne X filho a` esquerda de Y
2.5.3 Rotac¸a˜o dupla a` direita
Deve ser efetuada quando a diferenc¸a das alturas h dos filhos de P e´ igual a 2
e a diferenc¸a das alturas h dos filhos de FE e´ igual a -1. Nesse caso devemos
aplicar uma rotac¸a˜o a` esquerda no no´ FE e, em seguida, uma rotac¸a˜o a`
direita no no´ P .
2.5.4 Rotac¸a˜o dupla a` esquerda
Deve ser efetuada quando a diferenc¸a das alturas h dos filhos de P e´ igual
a -2 e a diferenc¸a das alturas h dos filhos de FD e´ igual a 1. Nesse caso
devemos aplicar uma rotac¸a˜o a` direita no no´ FD e, em seguida, uma rotac¸a˜o
a` esquerda no no´ P .
5
3 A´rvore Rubro-Negra
3.1 Definic¸a˜o
1. Todo no´ e´ vermelho ou preto; A raiz e´ preta
2. Toda folha e´ preta
3. Se um no´ e´ vermelho, enta˜o os seus filhos sa˜o pretos
4. Para cada no´, todos os caminhos do no´ para folhas descendentes conte´m
o mesmo nu´mero de no´s PRETOS.
Se um no´ satisfaz as propriedades acima,ele e´ dito equilibrado.
3.2 Inserc¸a˜o
Um no´ e´ inserido sempre na cor vermelha, assim, na˜o altera a altura negra
da a´rvore. Se o nodo fosse inserido na cor preta, invalidaria a propriedade 5,
pois haveria um nodo preto a mais em um dos caminhos.
A operac¸a˜o de inserc¸a˜o em uma a´rvore rubro-negra comec¸a por uma busca
da posic¸a˜o onde o novo nodo deve ser inserido, partindo-se da raiz em direc¸a˜o
aos nodos que possuam o valor mais pro´ximo do qual vai ser inserido.
1. Caso esta inserc¸a˜o seja feita em uma a´rvore vazia, basta alterar a cor
do nodo para preto, satisfazendo assim a propriedade 2.
2. Ao inserir x, se o tio de x e´ vermelho, e´ necessa´rio fazer a recolorac¸a˜o
do av, tio e pai.
3. Suponha que o tio do elemento inserido e´ preto. Neste caso, para
manter o crite´rio 4 e´ preciso fazer rotac¸o˜es envolvendo av, tio, pai e x.
Ha´ 4 subcasos que correspondem a`s 4 rotac¸o˜es poss´ıveis:
Rotac¸a˜o a` Direita recolore o pai e o av.
Rotac¸a˜o a` Esquerda recolore o pai e o av.
Rotac¸a˜o Dupla Esquerda rotac¸a˜o simples a` direita seguida da
rotac¸a˜o simples a` esquerda e recolorac¸a˜o do x e o av.
Rotac¸a˜o Dupla Direita rotac¸a˜o simples a` esquerda seguida da
rotac¸a˜o simples a` direita e recolorac¸a˜o do x e o av.
3.3 Remoc¸a˜o
Leia o Cormen e o Szwarcfiter e vai na fe´!
6
4 Diagrama de Classes
Temos aqui um modo bem singelo de heranc¸a e composic¸a˜o que e´ bem sim-
ples. Toda A´rvore Rubro-Negra e´ uma A´rvore Bina´ria de Busca, assim como
uma A´rvore AVL tambe´m e´. E Toda A´rvore Bina´ria de Busca e´ formada por
0 ou mais no´s.
5 Implementac¸a˜o
5.1 Classe [No]
#include <iostream >
#include "No.h"
No::No(int elem)
{
this ->elemento = elem;
this ->setNoDir(NULL);
this ->setNoEsq(NULL);
this ->setNoPai(NULL);
this ->balanceamento = 0;
7
this ->altura = 0;
this ->vermelho = false;
}
No *No:: getNoDir ()
{
return this ->noDir;
}
void No:: setNoDir(No *no)
{
this ->noDir = no;
}
No *No:: getNoEsq ()
{
return this ->noEsq;
}
void No:: setNoEsq(No *no)
{
this ->noEsq = no;
}
int No:: getElemNo ()
{
if (this == NULL) {
return -1;
}else{
return this ->elemento;
}
}
void No:: setElemNo(int novoElem)
{
this ->elemento = novoElem;
}
No *No:: getNoPai ()
{
return this ->noPai;
}
8
void No:: setNoPai(No *no)
{
this ->noPai = no;
}
int No:: getBalanceamento ()
{
if (this != NULL) {
return this ->balanceamento;
}else{
return 0;
}
}
void No:: setBalanceamento(int bal)
{
this ->balanceamento = bal;
}
void No:: setAltura(int novaAltura)
{
this ->altura = novaAltura;
}
bool No:: ehVermelho ()
{
if (this != NULL) {
return this ->vermelho;
}else{
return false;
}
}
void No:: setVermelho(bool cor)
{
this ->vermelho = cor;
}
No::~No()
{
//dtor
9
}
5.2 Classe [ArvoreBinaria]
#include <iostream >
#include <iomanip >
#include "No.h"
#include "ArvoreBinaria.h"
using namespace std;
std::vector <No> lista;
ArvoreBinaria :: ArvoreBinaria(No *no)
{
this ->noRaiz = no;
}
No *ArvoreBinaria :: getRaiz ()
{
return this ->noRaiz;
}
void ArvoreBinaria :: setRaiz(No * no)
{
this ->noRaiz = no;
}
bool ArvoreBinaria :: inserirAB(int elem)
{
if (buscar(this ->getRaiz (),elem) != NULL) {
return false;
}else{
No *z = new No(elem);
No *y = NULL;
No *x = this ->getRaiz ();
while (x!= NULL) {
y = x;
if (z->getElemNo () < x->getElemNo ()) {
x = x->getNoEsq ();
} else {
x = x->getNoDir ();
10
}
}
if (y == NULL) {
this ->setRaiz(z);
} else if(z->getElemNo () < y->getElemNo ()){
y->setNoEsq(z);
}else{
y->setNoDir(z);
}
return true;
}
}
bool ArvoreBinaria :: removerNo(No *no,int elem)
{
if(no == NULL)
return false;
No* ant = NULL;
No* atual = no;
while(atual != NULL){
if(elem == atual ->getElemNo ()){
if(atual == no)
no = removeAtual(atual);
else{
if(ant ->getNoDir () == atual)
ant ->setNoDir(removeAtual(atual)
);
else
ant ->setNoEsq(removeAtual(atual)
);
}
return true;
}
ant = atual;
if(elem > atual ->getElemNo ())
atual = atual ->getNoDir ();
else
atual = atual ->getNoEsq ();
}
return false;
}
11
No *ArvoreBinaria :: removeAtual(No *no)
{
No *no1 , *no2;
if(no->getNoEsq () == NULL){
no2 = no->getNoDir ();
return no2;
}
no1 = no;
no2 = no->getNoEsq ();
while(no2 ->getNoDir () != NULL){
no1 = no2;
no2 = no2 ->getNoDir ();
}
if(no1 != no){
no1 ->setNoDir(no2 ->getNoEsq ());
no2 ->setNoEsq(no->getNoEsq ());
}
no2 ->setNoDir(no->getNoDir ());
return no2;
}
int ArvoreBinaria :: totalNos(No *no)
{
if (no == NULL)
return 0;
int nos_esq = totalNos(no->getNoEsq ());
int nos_dir = totalNos(no->getNoDir ());
return(nos_esq + nos_dir + 1);
}
int ArvoreBinaria :: altura(No *no)
{
if (no == NULL) {
return -1;
}
12
if (no->getNoEsq () == NULL && no->getNoDir () == NULL
) {
return 0;
}else if (no->getNoEsq () == NULL){
return 1 + altura(no->getNoDir ());
}else if(no->getNoDir () == NULL){
return 1 + altura(no->getNoEsq ());
}else{
return 1 + max(altura(no->getNoEsq ()),altura(no
->getNoDir ()));
}
}
int ArvoreBinaria :: balanceamentoNo(No *no)
{
int alturaDir = this ->altura(no->getNoDir ());
int alturaEsq = this ->altura(no->getNoEsq ());
return alturaDir - alturaEsq;
}
int ArvoreBinaria ::sucNo(No *no)
{
if (no->getNoDir () != NULL) {
return minimo(no->getNoDir ());
}else{
return -1;
}
}
int ArvoreBinaria ::antNo(No *no)
{
if (no->getNoEsq () != NULL) {
return maximo(no->getNoEsq ());
}else{
return -1;
}
}
No * ArvoreBinaria :: buscar(No *no, int valor)
{
if(no == NULL){
return NULL;
}
13
if(no->getElemNo () == valor){
return no;
}
if (valor < no->getElemNo ()) {
return buscar(no->getNoEsq (), valor);
}else{
return buscar(no->getNoDir (), valor);
}
}
int ArvoreBinaria :: minimo(No *no)
{
while(no->getNoEsq () != NULL)
no = no->getNoEsq ();
return no->getElemNo ();
}
int ArvoreBinaria :: maximo(No *no)
{
while (no ->getNoDir () != NULL)
no = no->getNoDir ();
return no->getElemNo ();
}
void ArvoreBinaria :: emOrdem(No *no)
{
if(no != NULL){
emOrdem(no ->getNoEsq ());
cout << " " << no->getElemNo () << " ";
emOrdem(no ->getNoDir ());
}
}
void ArvoreBinaria :: preOrdem(No *no)
{
if (no != NULL) {
cout << " " << no->getElemNo () << " ";
preOrdem(no->getNoEsq ());
preOrdem(no->getNoDir ());
}
}
void ArvoreBinaria :: posOrdem(No *no)
14
{
if (no != NULL) {posOrdem(no->getNoEsq ());
posOrdem(no->getNoDir ());
cout << " " << no->getElemNo () << " ";
}
}
std::vector <No> ArvoreBinaria :: vetorPosOrdem(No *no)
{
if (no != NULL) {
vetorPosOrdem(no->getNoEsq ());
vetorPosOrdem(no->getNoDir ());
lista.push_back (*no);
}
return lista;
}
ArvoreBinaria ::~ ArvoreBinaria ()
{
//dtor
}
5.3 Classe [AVL]
#include <iostream >
#include <cstdlib >
#include <algorithm >
#include "No.h"
#include "ArvoreBinaria.h"
#include "AVL.h"
using namespace std;
AVL::AVL(No *no):ArvoreBinaria(no)
{
this ->noRaiz = no;
}
void AVL:: inserirAVL(int elem)
{
No * no = new No(elem);
inserirABAVL(this ->getRaiz (), no);
15
}
void AVL:: setBalanco(No * no) {
no->setBalanceamento(altura(no->getNoDir ())-
altura(no->getNoEsq ()));
}
void AVL:: verificarBalanceamento(No * noAtual) {
setBalanco(noAtual);
int balanceamento = noAtual ->getBalanceamento ();
if (balanceamento == -2) {
if (altura(noAtual ->getNoEsq ()->getNoEsq ())
>= altura(noAtual ->getNoEsq ()->getNoDir ()
)) {
noAtual = rotacaoDireita(noAtual);
} else {
noAtual = duplaRotacaoEsquerdaDireita(
noAtual);
}
} else if (balanceamento == 2) {
if (altura(noAtual ->getNoDir ()->getNoDir ())
>= altura(noAtual ->getNoDir ()->getNoEsq ()
)) {
noAtual = rotacaoEsquerda(noAtual);
} else {
noAtual = duplaRotacaoDireitaEsquerda(
noAtual);
}
}
if (noAtual ->getNoPai () != NULL) {
verificarBalanceamento(noAtual ->getNoPai ());
} else {
this ->setRaiz(noAtual);
}
}
/** ROTACOES **/
No * AVL:: rotacaoEsquerda(No * inicial) {
16
No * direita = inicial ->getNoDir ();
direita ->setNoPai(inicial ->getNoPai ());
inicial ->setNoDir(direita ->getNoEsq ());
if (inicial ->getNoDir () != NULL) {
inicial ->getNoDir ()->setNoPai(inicial);
}
direita ->setNoEsq(inicial);
inicial ->setNoPai(direita);
if (direita ->getNoPai () != NULL) {
if (direita ->getNoPai ()->getNoDir () == inicial)
{
direita ->getNoPai ()->setNoDir(direita);
} else if (direita ->getNoPai ()->getNoEsq () ==
inicial) {
direita ->getNoPai ()->setNoEsq(direita);
}
}
setBalanco(inicial);
setBalanco(direita);
return direita;
}
No * AVL:: rotacaoDireita(No * inicial) {
No * esquerda = inicial ->getNoEsq ();
esquerda ->setNoPai(inicial ->getNoPai ());
inicial ->setNoEsq(esquerda ->getNoDir ());
if (inicial ->getNoEsq () != NULL) {
inicial ->getNoEsq ()->setNoPai(inicial);
}
esquerda ->setNoDir(inicial);
inicial ->setNoPai(esquerda);
17
if (esquerda ->getNoPai () != NULL) {
if (esquerda ->getNoPai ()->getNoDir () == inicial)
{
esquerda ->getNoPai ()->setNoDir(esquerda);
} else if (esquerda ->getNoPai ()->getNoEsq () ==
inicial) {
esquerda ->getNoPai ()->setNoEsq(esquerda);
}
}
setBalanco(inicial);
setBalanco(esquerda);
return esquerda;
}
No * AVL:: duplaRotacaoEsquerdaDireita(No * inicial) {
inicial ->setNoEsq(rotacaoEsquerda(inicial ->getNoEsq
()));
return rotacaoDireita(inicial);
}
No * AVL:: duplaRotacaoDireitaEsquerda(No * inicial) {
inicial ->setNoDir(rotacaoDireita(inicial ->getNoDir ()
));
return rotacaoEsquerda(inicial);
}
/** ROTACOES **/
void AVL:: inserirABAVL(No * aComparar , No * aInserir) {
if (aComparar == NULL) {
this ->setRaiz(aInserir);
} else {
if ((aInserir ->getElemNo ()) < (aComparar ->
getElemNo ())) {
if (aComparar ->getNoEsq () == NULL) {
aComparar ->setNoEsq(aInserir);
18
aInserir ->setNoPai(aComparar);
verificarBalanceamento(aComparar);
} else {
inserirABAVL(aComparar ->getNoEsq (),
aInserir);
}
} else if ((aInserir ->getElemNo ()) > (aComparar
->getElemNo ())) {
if (aComparar ->getNoDir () == NULL) {
aComparar ->setNoDir(aInserir);
aInserir ->setNoPai(aComparar);
verificarBalanceamento(aComparar);
} else {
inserirABAVL(aComparar ->getNoDir (),
aInserir);
}
} else {
//cout << "Elemento ja existe."<< endl;
}
}
}
int AVL:: altura(No *atual)
{
if (atual == NULL) {
return -1;
}
if (atual ->getNoEsq () == NULL && atual ->getNoDir ()
== NULL) {
return 0;
}else if (atual ->getNoEsq () == NULL){
return 1 + altura(atual ->getNoDir ());
}else if(atual ->getNoDir () == NULL){
return 1 + altura(atual ->getNoEsq ());
}else{
19
return 1 + max(altura(atual ->getNoEsq ()),altura(
atual ->getNoDir ()));
}
}
/** REMOCAO **/
void AVL:: removerAVL(int valor) {
removerABAVL(this ->getRaiz (), valor);
}
void AVL:: removerABAVL(No * atual , int valor) {
if (atual == NULL) {
return;
} else {
if (atual ->getElemNo () > valor) {
removerABAVL(atual ->getNoEsq (), valor);
} else if (atual ->getElemNo () < valor) {
removerABAVL(atual ->getNoDir (), valor);
} else if (atual ->getElemNo () == valor) {
removerNoEncontrado(atual);
}
}
}
void AVL:: removerNoEncontrado(No * aRemover) {
No * noTemp;
if (aRemover ->getNoEsq () == NULL || aRemover ->
getNoDir () == NULL) {
if (aRemover ->getNoPai () == NULL) {
this ->setRaiz(NULL);
aRemover = NULL;
return;
}
noTemp = aRemover;
} else {
noTemp = this ->sucessor(aRemover);
aRemover ->setElemNo(noTemp ->getElemNo ());
20
}
No * noReordena;
if (noTemp ->getNoEsq () != NULL) {
noReordena = noTemp ->getNoEsq ();
} else {
noReordena = noTemp ->getNoDir ();
}
if (noReordena != NULL) {
noReordena ->setNoPai(noTemp ->getNoPai ());
}
if (noTemp ->getNoPai () == NULL) {
this ->setRaiz(noReordena);
} else {
if (noTemp == noTemp ->getNoPai ()->getNoEsq ()
) {
noTemp ->getNoPai ()->setNoEsq(noReordena)
;
} else {
noTemp ->getNoPai ()->setNoDir(noReordena)
;
}
verificarBalanceamento(noTemp ->getNoPai ());
}
noTemp = NULL;
}
No *AVL:: sucessor(No * no)
{
if (no->getNoDir () != NULL) {
No * noR = no->getNoDir ();
while (noR ->getNoEsq () != NULL) {
noR = noR ->getNoEsq ();
}
return noR;
} else {
No * noP = no->getNoPai ();
while (noP != NULL && no == noP ->getNoDir ()) {
no = noP;
21
noP = no->getNoPai ();
}
return noP;
}
}
/** REMOCAO **/
AVL::~AVL()
{
//dtor
}
5.4 Classe [ArvoreRN]
#include <iostream >
#include <string >
#include <sstream >
#include <iomanip >
#include "No.h"
#include "ArvoreRN.h"
using namespace std;
/** FUNCAO PARA COLORIR NOS **/
/** DISPONIVEL EM: http :// stackoverflow.com/questions
/9943187/ colour -output -of-program -run -under -bash **/
enum Color
{
NONE = 0,
BLACK , RED , GREEN ,
YELLOW , BLUE , MAGENTA ,
CYAN , WHITE
};
static std:: string set_color(Color foreground = NONE ,
Color background = NONE)
{
std:: stringstream s;
s << "\033[";
if (! foreground && ! background){
s << "0";
}
22
if (foreground) {
s << 29 + foreground;
if (background) s << ";";
}
if (background) {
s << 39 + background;
}
s << "m";
return s.str();
}
/** FUNCAO PARA COLORIR NOS **/
ArvoreRN :: ArvoreRN(No *no):ArvoreBinaria(no)
{
this ->noRaiz = no;
}
void ArvoreRN :: inserirRN(int elem)
{
if(this ->buscar(this ->getRaiz (),elem)== NULL){
inserirABRN(elem , this ->getRaiz ());
}else{
return;
}
}
void ArvoreRN :: inserirABRN(int elem , No *no)
{
if(this ->getRaiz ()==NULL)
this ->setRaiz(new No(elem));
else{
if(elem >no->getElemNo ()){
if(no->getNoDir () == NULL){
No * noDir = new No(elem);
noDir ->setNoPai(no);
noDir ->setVermelho(true);
no->setNoDir(noDir);
balanco(no ->getNoDir ());
}else
23
inserirABRN(elem ,no->getNoDir ());
}else{
if(no->getNoEsq () == NULL){
No * noEsq = new No(elem);
noEsq->setNoPai(no);
noEsq ->setVermelho(true);
no->setNoEsq(noEsq);
balanco(no ->getNoEsq ());
}else
inserirABRN(elem , no->getNoEsq ());
}
}
}
void ArvoreRN :: balanco(No * no)
{
if (no->getNoPai () == NULL ||
no->getNoPai ()->getNoPai () == NULL ||
!(no->getNoPai ()->ehVermelho () == true
&& no->ehVermelho () == true)) {
return;
}
No * y;
No * z;
y=no->getNoPai ();
z=no->getNoPai ()->getNoPai ();
if(z->getNoEsq ()==y){
if(y->getNoEsq ()==no){
if(z->getNoDir ()==NULL || z->
getNoDir ()->ehVermelho ()==false){
rotacaoDireita(y,z);
z->setVermelho(true);
y->setVermelho(false);
}else{
z->setVermelho(true);
y->setVermelho(false);
24
z->getNoDir ()->setVermelho(false
);
if(z==this ->getRaiz ()){
z->setVermelho(false);
}
else{
balanco(z);
}
}
}else{
rotacaoEsquerda(no,y);
if(z->getNoDir ()==NULL || z->
getNoDir ()->ehVermelho ()==false){
rotacaoDireita(no,z);
z->setVermelho(true);
no->setVermelho(false);
}else{
z->setVermelho(true);
no->setVermelho(false);
z->getNoDir ()->setVermelho(false
);
if(z==this ->getRaiz ())
z->setVermelho(false);
else
balanco(z);
}
}
}else{
if(y->getNoDir ()==no){
if(z->getNoEsq ()==NULL || z->
getNoEsq ()->ehVermelho ()==false){
rotacaoEsquerda(y,z);
z->setVermelho(true);
y->setVermelho(false);
}else{
z->setVermelho(true);
y->setVermelho(false);
25
z->getNoEsq ()->setVermelho(false
);
if(z==this ->getRaiz ())
z->setVermelho(false);
else
balanco(z);
}
}else{
rotacaoDireita(no,y);
if(z->getNoEsq () == NULL || z->
getNoEsq ()->ehVermelho ()==false){
rotacaoEsquerda(no,z);
z->setVermelho(true);
no->setVermelho(false);
}else{
z->setVermelho(true);
no->setVermelho(false);
z->getNoEsq ()->setVermelho(false
);
if(z==this ->getRaiz ()){
z->setVermelho(false);
}
else{
balanco(z);
}
}
}
}
}
void ArvoreRN :: rotacaoDireita(No *no1 , No *no2)
{
no1 ->setNoPai(no2 ->getNoPai ());
if(no1 ->getNoPai ()== NULL)
this ->setRaiz(no1);
else if(no1 ->getNoPai ()->getNoEsq () == no2)
no1 ->getNoPai ()->setNoEsq(no1);
else
no1 ->getNoPai ()->setNoDir(no1);
26
no2 ->setNoEsq(no1 ->getNoDir ());
if(no2 ->getNoEsq () != NULL)
no2 ->getNoEsq ()->setNoPai(no2);
no1 ->setNoDir(no2);
no2 ->setNoPai(no1);
}
void ArvoreRN :: rotacaoEsquerda(No *no1 , No *no2)
{
no1 ->setNoPai(no2 ->getNoPai ());
if(no2 ->getNoPai () == NULL)
this ->setRaiz(no1);
else if(no2 ->getNoPai ()->getNoEsq ()==no2)
no1 ->getNoPai ()->setNoEsq(no1);
else
no1 ->getNoPai ()->setNoDir(no1);
no2 ->setNoDir(no1 ->getNoEsq ());
if(no2 ->getNoDir () != NULL)
no2 ->getNoDir ()->setNoPai(no2);
no1 ->setNoEsq(no2);
no2 ->setNoPai(no1);
}
void ArvoreRN :: removerABRN(No * no)
{
if(no==this ->getRaiz () && no->getNoEsq () == NULL &&
no->getNoDir () == NULL){
this ->setRaiz(NULL);
return;
}
No * y;
No * z;
bool unicoFilho = false;
27
if(no->getNoEsq () == NULL || no->getNoDir () == NULL)
{ // atleast one child
y = no;
unicoFilho = true;
}else{
No * noTemp = no->getNoDir ();
for(y=noTemp; y->getNoEsq ()!=NULL;y = y->
getNoEsq ());
}
bool estaNaEsquerda = false;
if(y->getNoEsq () != NULL)
z = y->getNoEsq ();
else
z = y->getNoDir ();
if(z != NULL)
z->setNoPai(y->getNoPai ());
if(y->getNoPai () == NULL)
this ->setRaiz(z);
else{
if(y == y->getNoPai ()->getNoEsq ()){
y->getNoPai ()->setNoEsq(z);
estaNaEsquerda = false;
}else{
estaNaEsquerda = true;
y->getNoPai ()->setNoDir(z);
}
}
no->setElemNo(y->getElemNo ());
No * a;
No * b;
No * c;
No * d;
int caso;
No * irmaoNo;
int i = 0;
do{
i++;
28
if(y->getNoPai () == NULL){
this ->setRaiz(y);
y->setVermelho(false);
return;
}
caso = 0;
bool ehVermelho = false;
if(y->getNoPai ()->ehVermelho ()){
if(estaNaEsquerda == false)
irmaoNo = y->getNoPai ()->getNoDir ();
else
irmaoNo = y->getNoPai ()->getNoEsq ();
ehVermelho = false;
if(irmaoNo != NULL){
if(irmaoNo ->getNoEsq () != NULL){
ehVermelho = irmaoNo ->getNoEsq ()->
ehVermelho ();
c = irmaoNo ->getNoEsq ();
}else if(irmaoNo ->getNoDir () != NULL){
ehVermelho = (ehVermelho || irmaoNo
->getNoDir ()->ehVermelho ());
c = irmaoNo ->getNoDir ();
}
}
if(irmaoNo ->ehVermelho () == false &&
ehVermelho == true)
caso = 1;
else if(irmaoNo ->ehVermelho () == false)
caso = 2;
}else{
if(estaNaEsquerda == false){
irmaoNo = y->getNoPai ()->getNoDir ();
}else{
irmaoNo = y->getNoPai ()->getNoEsq ();
}
ehVermelho = false;
if(irmaoNo != NULL){
if(irmaoNo ->ehVermelho () == true){
29
if(estaNaEsquerda && irmaoNo ->
getNoDir () != NULL){
c = irmaoNo ->getNoDir ();
if(irmaoNo ->getNoDir ()->getNoEsq
() != NULL){
ehVermelho = irmaoNo ->
getNoDir ()->ehVermelho ();
d = irmaoNo ->getNoDir ()->
getNoEsq ();
}if(ehVermelho)
caso = 3;
}else if(ehVermelho != true &&
irmaoNo ->getNoEsq () != NULL){
c = irmaoNo ->getNoEsq ();
if(irmaoNo ->getNoEsq ()->getNoDir
() != NULL){
ehVermelho = irmaoNo ->
getNoEsq ()->getNoDir ()->
ehVermelho ();
d = irmaoNo ->getNoEsq ()->
getNoDir ();
}if(ehVermelho)
caso = 4;
}
if(ehVermelho == false)
caso = 5;
}else{
bool continuaVermelho = false;
if(irmaoNo ->getNoEsq () != NULL){
ehVermelho = irmaoNo ->getNoEsq ()
->ehVermelho ();
}
if(irmaoNo ->getNoDir () != NULL){
continuaVermelho = irmaoNo ->
getNoDir ()->ehVermelho ();
}
if(continuaVermelho || ehVermelho )
{
caso = 6;
if(ehVermelho)
c = irmaoNo ->getNoEsq ();
else
c = irmaoNo ->getNoDir ();
30
cout << c->getElemNo () <<
endl;
}else
caso = 7;
}
}
}
b = irmaoNo;
switch(caso){
case 1:
a = y->getNoPai ();
b = irmaoNo;
b->setNoPai(a);
c->setNoPai(b);
if(a->getNoEsq () == b){
if(b->getNoEsq () == c){
rotacaoDireita(b,a);
}else{
rotacaoEsquerda(c,b);
rotacaoDireita(c,a);
}
}else{
if(b->getNoDir () == c){
rotacaoEsquerda(b,a);
}else{
rotacaoDireita(c,b);
rotacaoEsquerda(c,a);
}
}
break;
case 2:
a = y->getNoPai ();
b->setNoPai(a);
a->setVermelho(false);
b->setVermelho(true);
break;
case 3:
a = y->getNoPai ();
b->setNoPai(a);
c->setNoPai(b);
d->setNoPai(c);
31
if(a->getNoEsq () == b){
rotacaoDireita(b,a);
d->setVermelho(false);
c->setVermelho(true);
b->setVermelho(false);
}else{
rotacaoEsquerda(b,a);
rotacaoDireita(a,b);
d->setVermelho(false);
c->setVermelho(true);
b->setVermelho(false);
}
break;
case 4:
a = y->getNoPai ();
b->setNoPai(a);
c->setNoPai(b);
d->setNoPai(c);
if(a->getNoEsq () == b){
rotacaoEsquerda(c,b);
rotacaoDireita(c,a);
d->setVermelho(false);
}else{
rotacaoEsquerda(b,a);
b->setVermelho(false);
c->setVermelho(true);
d->setVermelho(false);
}
break;
case 5:
a = y->getNoPai ();
b->setNoPai(a);
c->setNoPai(b);
if(a->getNoEsq () == b){
rotacaoDireita(b,a);
b->setVermelho(false);
c->setVermelho(true);
}else{
rotacaoEsquerda(b,a);
b->setVermelho(false);
c->setVermelho(true);
}
32
break;
case 6:
a = y->getNoPai ();
b->setNoPai(a);
c->setNoPai(b);
if(a->getNoEsq () == b){
if(b->getNoEsq () == c){
rotacaoDireita(b,a);
b->setVermelho(false);
c->setVermelho(false);
a->setVermelho(false);
}else{
rotacaoEsquerda(c,b);
rotacaoDireita(c,a);
c->setVermelho(false);
}
}else{
if(b->getNoDir () == c){
rotacaoEsquerda(b,a);
b->setVermelho(false);
c->setVermelho(false);
a->setVermelho(false);
}else{
rotacaoDireita(c,b);rotacaoEsquerda(c,a);
c->setVermelho(false);
}
}
break;
case 7:
a = y->getNoPai ();
b->setNoPai(a);
b->setVermelho(true);
y = a;
if(y->getNoPai () == y)
estaNaEsquerda = false;
else
estaNaEsquerda = true;
break;
}
}while(caso == 7);
33
}
void ArvoreRN :: removerRN(int elem)
{
if(this ->buscar(this ->getRaiz (), elem)!= NULL){
No * aRemover = buscar(this ->getRaiz (), elem);
removerABRN(aRemover);
}else{
return;
}
}
void ArvoreRN :: posOrdemColorido(No *no)
{
if (no != NULL) {
posOrdemColorido(no->getNoEsq ());
posOrdemColorido(no->getNoDir ());
if (no->ehVermelho ()) {
cout << set_color(RED) << " " << no ->
getElemNo () << " " << set_color(NONE);
}else{
cout << set_color(BLUE) << " " << no->
getElemNo () << " " << set_color(NONE);
}
}
}
ArvoreRN ::~ ArvoreRN ()
{
}
5.5 Boˆnus - Classe [Impressao]
Para voceˆ amiguinho e amiguinha que quer ver o circo pegar fogo e va´rias
falhas de segmentac¸a˜o lind´ıssimas, a´ı vai o co´digo de como imprimir a a´rvore
no terminal do Linux (na˜o imprima muitos no´s, a coisa fica realmente feia):
34
#include <fstream >
#include <cmath >
#include <iostream >
#include <deque >
#include <iomanip >
#include <sstream >
#include <string >
#include "Impressao.h"
#include "ArvoreBinaria.h"
//using namespace std;
Impressao :: Impressao ()
{
}
// Maior altura Arvore Binaria
int Impressao :: alturaMaxima(No * no) {
if (!no) return 0;
int alturaEsquerda = alturaMaxima(no->getNoEsq ());
int alturaDireita = alturaMaxima(no->getNoDir ());
return (alturaEsquerda > alturaDireita) ?
alturaEsquerda + 1: alturaDireita + 1;
}
35
// Converte um inteiro para uma String
string Impressao :: intToString(int elem){
ostringstream ss;
ss << elem;
return ss.str();
}
// Imprime os ramos diagonais
void Impressao :: imprimeGalhos(int larguraGalho , int
espacoEntreNos , int larguraInicial ,
int nosNesseNivel , const
deque <No *> &listaNos ,
ostream& tipoSaida){
deque <No*>:: const_iterator iterador = listaNos.begin()
;
//std::vector <No *>:: iterator iterador = listaNos ->
begin();
for (int i = 0; i < nosNesseNivel / 2; i++) {
tipoSaida << ((i == 0) ? setw(larguraInicial -1) :
setw(espacoEntreNos -2)) << "" << ((* iterador ++) ?
"/" : " ");
tipoSaida << setw (2* larguraGalho +2) << "" << ((*
iterador ++) ? "\\" : " ");
}
tipoSaida << endl;
}
// Imprime ramos horizontais
void Impressao :: imprimeNos(int larguraGalho , int
espacoEntreNos , int larguraInicial , int
nosNesseNivel ,
const deque <No*>& listaNos , ostream&
tipoSaida){
deque <No*>:: const_iterator iter = listaNos.begin();
for (int i = 0; i < nosNesseNivel; i++, iter ++) {
tipoSaida << ((i == 0) ? setw(larguraInicial) : setw
(espacoEntreNos)) << "" << ((* iter && (*iter)->
getNoEsq ()) ? setfill(’_’) : setfill(’ ’));
tipoSaida << setw(larguraGalho +2) << ((* iter) ?
intToString ((* iter)->getElemNo ()) : "");
tipoSaida << ((* iter && (*iter)->getNoDir ()) ?
setfill(’_’) : setfill(’ ’)) << setw(larguraGalho
36
) << "" << setfill(’ ’);
}
tipoSaida << endl;
}
// Imprime as folhas
void Impressao :: imprimeFolhas(int espacoIdentacao ,
int nivel , int nosNesseNivel ,
const deque <No*>& listaNos ,
ostream& tipoSaida){
deque <No*>:: const_iterator iter = listaNos.begin();
for (int i = 0; i < nosNesseNivel; i++, iter ++) {
tipoSaida << ((i == 0) ? setw(espacoIdentacao +2) :
setw (2* nivel +2)) << ((* iter) ? intToString ((* iter
)->getElemNo ()) : "");
}
tipoSaida << endl;
}
void Impressao :: imprimeArvore(No * raiz , int nivel , int
espacoIdentacao , ostream& tipoSaida){
int h = alturaMaxima(raiz);
int nosNesseNivel = 1;
int larguraGalho = 2*(( int)pow(2.0,h) -1) - (3-nivel)*(
int)pow(2.0,h-1);
int espacoEntreNos = 2 + (nivel +1)*(int)pow(2.0,h);
int larguraInicial = larguraGalho + (3-nivel) +
espacoIdentacao;
deque <No*> listaNos;
listaNos.push_back(raiz);
for (int r = 1; r < h; r++) {
imprimeGalhos(larguraGalho , espacoEntreNos ,
larguraInicial ,nosNesseNivel ,listaNos ,tipoSaida);
larguraGalho = larguraGalho /2 - 1;
espacoEntreNos = espacoEntreNos /2 + 1;
larguraInicial = larguraGalho + (3-nivel) +
espacoIdentacao;
imprimeNos(larguraGalho ,espacoEntreNos ,
larguraInicial ,nosNesseNivel ,listaNos ,tipoSaida);
for (int i = 0; i < nosNesseNivel; i++) {
37
No * noAtual = listaNos.front();
listaNos.pop_front ();
if (noAtual) {
listaNos.push_back(noAtual ->getNoEsq ());
listaNos.push_back(noAtual ->getNoDir ());
} else {
listaNos.push_back(NULL);
listaNos.push_back(NULL);
}
}
nosNesseNivel *= 2;
}
imprimeGalhos(larguraGalho ,espacoEntreNos ,
larguraInicial ,nosNesseNivel ,listaNos ,tipoSaida);
imprimeFolhas(espacoIdentacao ,nivel ,nosNesseNivel ,
listaNos ,tipoSaida);
}
Impressao ::~ Impressao ()
{
}
6 Considerac¸o˜es Finais
Espero que esse documento seja u´til e tambe´m que o co´digo em si funcione
no seu computador, infelizmente, como diz o t´ıtulo, esta´ orientado a` gam-
biarra mas e´ apenas um guia de como entender (ou na˜o) como essa estrutura
funciona.
Na˜o me responsabilizo por falhas de segmentac¸a˜o e/ou exploso˜es.
7 Fontes
ATX 24 Pinos;
Times New Roman;
Da Juventude;
NOVA, Arena Fonte;
De A´gua.
38
8 Recomendac¸o˜es
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clif-
ford Stein. Introduction to Algorithms.
• Material do Ph.D. em Cieˆncia da Computac¸a˜o Siang Wun Song - Carnegie
Mellon University Slides
• Beber e na˜o dirigir.
• Slides do Jairo Francisco de Souza
• A´rvore Bina´ria de busca - Wikipe´dia
• A´rvore AVL - Wikipe´dia
39
	Árvore Binária de Busca
	Definição
	Busca
	Inserção
	Exclusão
	Exclusão na folha
	Exclusão de um nó com um filho
	Exclusão de um nó com dois filhos
	Percusso
	Pré-ordem (Em Profundidade)
	Ordem Simétrica (Em Ordem)
	Pós-ordem
	Árvore AVL
	Balanceamento
	Busca
	Inserção
	Remoção
	Rotação
	Rotação à direita
	Rotação à esquerda
	Rotação dupla à direita
	Rotação dupla à esquerda
	Árvore Rubro-Negra
	Definição
	Inserção
	Remoção
	Diagrama de Classes
	Implementação
	Classe [No]
	Classe [ArvoreBinaria]
	Classe [AVL]
	Classe [ArvoreRN]
	Bônus - Classe [Impressao]
	Considerações Finais
	Fontes
	Recomendações