Arvore AVL

As árvores binárias de busca permitem a organização da informação com o objetivo a otimizar as buscas, acesso mais rápido aos elemetos dado que os elementos estão organizados na árvore, obedecendo uma certa propriedade.

Propriedade:
 - Esquerda são menores que a raiz;
 - Direita são os maiores que a raiz.
 - Na árvore AVL de pesquisa T, as alturas de suas sub-árvores (direita e esquerda) diferem no máximo de uma unidade.

Balanceamento:
Para o balanceamento da árvore temos 2 casos

Caso 1: he (p) > hd (p) Ent ão, q pertence à subárvore esquerda de p, e p possui um filho esquerdo u, onde he (u) 6= hd (u). Dois casos podem ocorrer:
- he (u) > hd (u) : rotação direita
- hd (u) > he (u) : rotação dupla direita

Caso 2: hd (p) > he (p) Ent ̃ao, q pertence à sub de p, e p possui um filho direito z, onde he (z) 6= hd (z). Dois casos podem ocorrer:
- hd (z) > he (z) : rotção esquerda
- he (z) > hd (z) : rotação dupla esquerda


Implementação:

import java.util.ArrayList;
 
public class ArvoreAVL extends Arvore{
 private boolean t;
 private int local;
 
 public ArvoreAVL(){
  super();
 }
 
 //Metodo de busca de um elemento com chave x na arvore
  public No buscarElemento(int x){
   return super.buscarElemento(x);
  }
  /*========================================================================================*/
  private void caso1(No p,boolean h){
   No ptu = new No();
   boolean testeraiz = false; //testa se o no e a raiz
   
   if (p == raiz) testeraiz = true;
   ptu = p.esq;
   if (ptu.balanco == -1){    //rotacao direita
    p.esq = ptu.dir;  //seu filho a esquerda sera o filho a esquerda de seu filho
    if (ptu.dir != null){ //so entra se o filho a esquerda existir
     ptu.dir.pai = p;  //novo pai
    }
    if (p !=raiz){ p.pai.esq = ptu; }   //o pai de p tera o filho a direita de p como seu novo filho a direita
    ptu.pai = p.pai;
    ptu.dir = p;
    p.pai = ptu;
    p.balanco = 0;
    p = ptu;
    if (testeraiz) raiz = ptu; 
   }
   else{ //rotacao dupla direita
    No ptv = new No();
    ptv = ptu.dir;
    ptu.dir = ptv.esq;
    if (ptv.esq != null){//so entra se o filho a esquerda existir
     ptv.esq.pai= ptu;
    }
    ptv.esq = ptu;
    ptu.pai = ptv;
    p.esq = ptv.dir;
    if (ptv.dir !=null){
    ptv.dir.pai = p;
    }
    ptv.dir = p;
    if (p.pai !=null){p.pai.dir = ptv;} //o pai de p tera ptv como seu novo filho a direita
    ptv.pai = p.pai;
    p.pai =ptv;
    if (ptv.balanco == -1)p.balanco = 1;
    else p.balanco = 0;
    if (ptv.balanco == 1) ptu.balanco = -1;
    else ptu.balanco = 0;
    if (testeraiz)raiz = ptv; //se e a raiz
    p = ptv;
   }
   p.balanco = 0;
   t = false;
   
  }
 /*========================================================================================*/
  /*Metodo que executa a rotacao esquerda ou 
  a rotacao dupla esquerda para balancear a Arvore*/
  private void caso2(No p,boolean h){
   No ptu = new No();
   boolean testeraiz = false;
   
   if (p == raiz) testeraiz = true;
   ptu = p.dir;
   if (ptu.balanco == 1){    //rotacao esquerda
    p.dir = ptu.esq;  //seu filho a direita sera o filho a esquerda de seu filho
    if (ptu.esq != null){ //so entra se o filho a esquerda existir
     ptu.esq.pai = p;  //novo pai
    }
    if (p !=raiz) {p.pai.dir = ptu;}  //o pai de p tera o filho a direita de p como seu novo filho a direita
    ptu.pai = p.pai;
    ptu.esq = p;
    p.pai = ptu;
    p.balanco = 0;
    p = ptu;
    if (testeraiz) raiz = ptu; 
   }
   else{ //rotacao dupla esquerda
    No ptv = new No();
    ptv = ptu.esq;
    ptu.esq = ptv.dir;
    if (ptv.dir !=null){ //so entra se o filho a direita existir
     ptv.dir.pai= ptu;
    }
    ptv.dir = ptu;
    ptu.pai = ptv;
    p.dir = ptv.esq;
    if (ptv.esq !=null){
     ptv.esq.pai = p;
    }
    ptv.esq = p;
    if (p.pai !=null){p.pai.esq = ptv;} //o pai de p tera ptv como seu novo filho a esq
    p.pai =ptv;
    if (ptv.balanco == 1)p.balanco = -1;
    else p.balanco = 0;
    if (ptv.balanco == -1) ptu.balanco = 1;
    else ptu.balanco = 0;
    if (testeraiz)raiz = ptv;
    p = ptv;
   }
   p.balanco = 0;
   t = false;
  }
  
 /*========================================================================================*/
  //Metodo de insercao de um elemento com chave x na arvore
  /*Este metodo faz a busca sem usar a motodo buscarElemento() pois a organizacao
   * e o balanceamento sao testados e organizados durante a busca e insercao num mesmo momento.
   * para que todo o processo seja efetuado em O(log(n)) passos. Algoritmo demonstrado no livro: 
   * SZWARCFITER,Jaime Luiz.Estruturas de Dados e seus Algoritmos.(1994).LTC, 2 Ed.*/
  public boolean inserirElemento(int x){
   pt = new No(x);
   if (raiz == null){   
    raiz = pt;}//se arvore vazia, insere na raiz
   else{
    pt = raiz; //pt recebe raiz (para percurso na arvore)
    insAVL(x,pt,false);
   }
   System.out.println(exibirArvorePreOrdem());
   return true;
  }
  //Metodo privado recursivo que auxilia o metodo inserirElemento() para insercao e balanceamnto
  private boolean insAVL(int x,No pt,boolean h){
   t = h; 
   if (pt == null){//No alocado no espaco vazio
    pt = new No(x);
    if(pos==1){aux.esq= pt;} 
    else if (pos == 2){aux.dir = pt;}
    pt.pai = aux;//pai do no
    t=true;
    pos=0;
   }
   else{
    if (x == pt.info){ //ja existe element na arvore
     pt = null;
     return false;
    }
    if (x < pt.info){//chave menor que o no
     aux = pt;  //aux sera o pai do no inserido
     pos = 1;  // filho a esquerda de aux
     insAVL(x,pt.esq,t);
     //depois da insercao, a verificacao
     if (t){
      if (pt.balanco == 1){
       pt.balanco = 0;
       t = false;
      }
      else if (pt.balanco == 0) pt.balanco = -1;
      else if (pt.balanco == -1) caso1(pt,t); //rebalanceamento (rotacao direita)
     }
    }
    else{//chave maior que o no
      aux = pt; //aux sera o pai do no inserido
      pos = 2;  // filho a direita de aux
      insAVL(x,pt.dir,t);
     
      //depois da insercao, a verificacao
     if (t){
      
      if (pt.balanco == -1){
       pt.balanco = 0;
       t = false;
      }
      else if (pt.balanco == 0) pt.balanco = 1;
      else if (pt.balanco == 1) caso2(pt,t); //rebalanceamento (rotacao esquerda)
     }
    }
   }
   return true;
  }
  
  
 /*========================================================================================*/ 
  //Metodo de remocao de um elemento com chave x na arvore
  public boolean removerElemento(int x){
   if (raiz == null){return false;}//arvore vazia
   else{
    pt = raiz;//no de percurso
    remAVL(x,pt,false);
   }
   System.out.println(exibirArvorePreOrdem());
   return true;
  }
  //Metodo auxiliar para remocao do no x e balanceamento da arvore
  public boolean remAVL(int x,No pt,boolean h){
   t=h;

   if (pt == null){return false;}//nao achou
   else{
    if (x == pt.info ){//achou
     //*******REMOCAO*******/
     if (pt.esq == null && pt.dir == null){//no sem filhos
      if (pt == raiz) {raiz = null;}
      else{
       if (pos == 1)//este no e' o filho da esquerda do seu pai
        pt.pai.esq = null;
       else if(pos == 2)//este no e' o filho da direita do seu pai
        pt.pai.dir = null;
      }
      pt =null;
      t = true;
     }
     else {//tem filhos
      aux = pt;
      if (pt.esq == null){ //pode ter apenas o filho da direita
       pt = pt.dir;
       local = 1; //pai de pt tera novo filho a direita
      }
      else{
       if (pt.dir == null){//tem apenas o filho da esquerda
        pt = pt.esq;
        local = 2; //pai de pt tera novo filho a esquerda
       }
       else{//tem dois filhos

        pt = minDir(aux.dir); //achar o menor a direita
        pt.esq = aux.esq; //reordenacao de ponteiros
        if (aux == raiz){raiz = pt;}//se o no a ser removido era a raiz, pt e' a nova raiz
        else { 
         pt.pai = aux.pai;
         if (pos == 1)//este no e' o filho da esquerda do seu pai
          aux.pai.esq =pt;
         else if(pos == 2)//este no e' o filho da direita do seu pai
          aux.pai.dir =pt;
        }
        aux = null;
        return true;
       } 
      }
     }
     if (aux == raiz){raiz = pt;}//se o no a ser removido era a raiz, pt e' a nova raiz
     else{//nao e a raiz(tem pai)
      if (local == 1){aux.pai.dir = pt;} //pai tem filho a direita
      else if (local == 2) {aux.pai.esq = pt; }//pai tem filho a esquerda
     }
     aux = null;
    }
    //Continua a pesquisa
    else{
     if (x < pt.info){//procura na esquerda
      aux = pt;
      pos=1;
      remAVL(x,pt.esq,t);
      //depois da remocao, a verificacao
      if (t){
       if(pt.balanco == -1)
        pt.balanco = 0;
       t = false;
      }
      else if (pt.balanco == 0) pt.balanco = 1;
      else if (pt.balanco == 1)caso2(pt,t);//rebalanceamento (rotacao esquerda)
     }
     else{ //procura na direita
      aux = pt;
      pos=2;
      remAVL(x,pt.dir,t);
      //depois da remocao, a verificacao
      if (t){
       if (pt.balanco == 1){
        pt.balanco = 0;
        t = false;
       }
       else if (pt.balanco == 0) pt.balanco = -1;
       else if (pt.balanco == -1) caso1(pt,t); //rebalanceamento (rotacao direita)
      }
     }
    }
   }
   local=0; //sem valor, ao final da execucao
   return true;

  }
 /*========================================================================================*/ 
  /*Metodo que exibe a arvore em pre ordem
  na representacao de parenteses aninhados*/
  public String exibirArvorePreOrdem(){
   return super.exibirArvorePreOrdem();
  }
  
 /*========================================================================================*/ 
  /*Metodo que exibe o balanco da arvore em pre ordem
  na representacao de parenteses aninhados*/
  public String balanco(){
   if (raiz == null)return ""; 
   No p = this.raiz; // recebe o no raiz
   print = print + Integer.toString(p.balanco)+ " ";
   if (p.esq != null){print = print + "(" + balanco(p.esq)+")";}
   if (p.dir != null){print = print + "(" + balanco(p.dir)+ ")";}
   String pr =print;
   print = " ";
   return pr;
  }
  /*========================================================================================*/
  /*Metodo que exibe o balanco da arvore em pre ordem (auxiliar para 
    recursao na representacao de parenteses aninhados*/
  private String balanco(No p){
   print = Integer.toString(p.balanco)+ " ";
   if (p.esq != null){print = print + "( " + balanco(p.esq) + ")";}
   if (p.dir != null){print = print + "(" + balanco(p.dir)+ ")";}
   String pr = print;
   print = " ";
   return pr;
  }
 
}

Árvore Rubro Negra

              São árvores balanceadas segundo um critério ligeiramente diferente do usado em árvores AVL. A todos os nós é associada uma cor que pode ser vermelha ou negra de tal forma que:

Propriedades:
Uma árvore rubro-negra estará sempre balanceada pois segue o segunte conjunto de propriedades:
1. Todo nó é vermelho ou preto;
2. A raiz é preta;
3. Toda folha (NIL) é preta;
4. Se um nodo é vermelho, então ambos filhos são pretos;
5. Todos os caminhos a partir da raiz da árvore até uma de suas folhas passa obrigatoriamente pelo mesmo número de nodos pretos.

Inclusão na  árvore:
1. Insira um nó x como em uma  árvore binária normal
2. Pinte o nó de vermelho
3. Restaure as propriedades rubro-negra

Use rotação e recoloração:
Há 3 casos a considerar quando x e o pai de x são vermelhos
    Caso 1: x tem um tio y vermelho
    Caso 2: x tem um tio y preto e x  é filho direito
    Caso 3: x tem um tio y preto e x  é filho esquerdo

Obs. 1: O pai de x não pode ser a raiz da  árvore pois  é
Obs. 2: Considerar os casos simétricos aos casos 2 e 3.

Implementação:

public class ArvoreRB<T extends Comparable<T>> {
 
   
     public static final int PRETO = 0;
     public static final int VERM = 1;
  
     private class NoRB<T extends Comparable<T>> {
  
         public T chave;
         public NoRB<T> esq, dir, parent;
         public int cor;
  
         public NoRB() {
             esq = null;
             dir = null;
             parent = null;
             cor = PRETO;
         }
  
         public NoRB(T chave) {
             this();
             this.chave = chave;
         }
  
     }
  
     private NoRB<T> nil = new NoRB<>();
     private NoRB<T> raiz = nil;
  
     private void esqRotate(NoRB<T> x) {
      NoRB<T> y = x.dir;
         x.dir = y.esq;
         if (y.esq != nil) {
             y.esq.parent = x;
         }
         y.parent = x.parent;
         if (x.parent == nil) {
             raiz = y;
         } else {
             if (x == x.parent.esq) {
                 x.parent.esq = y;
             } else {
                 x.parent.dir = y;
             }
         }
         y.esq = x;
         x.parent = y;
     }
  
     private void dirRotate(NoRB<T> x) {
      NoRB<T> y = x.esq;
         x.esq = y.dir;
         if (y.dir != nil) {
             y.dir.parent = x;
         }
         y.parent = x.parent;
         if (x.parent == nil) {
             raiz = y;
         } else {
             if (x == x.parent.dir) {
                 x.parent.dir = y;
             } else {
                 x.parent.esq = y;
             }
         }
         y.dir = x;
         x.parent = y;
     }
  
     private void insere(NoRB<T> z) {
  
         NoRB<T> y = nil;
         NoRB<T> x = raiz;
  
         while (x != nil) {
             y = x;
             if (z.chave.compareTo(x.chave) < 0) {
                 x = x.esq;
             } else {
                 x = x.dir;
             }
         }
         z.parent = y;
         if (y == nil) {
             raiz = z;
         } else if (z.chave.compareTo(y.chave) < 0) {
             y.esq = z;
         } else {
             y.dir = z;
         }
  
         z.esq = nil;
         z.dir = nil;
         z.cor = VERM;
         insereFixUp(z);
     }
  
     private void insereFixUp(NoRB<T> z) {
         while (z != raiz && z.parent.cor == VERM) {
             if (z.parent == z.parent.parent.esq) {
                 NoRB<T> y = z.parent.parent.dir;
                 if (y.cor == VERM) {
                     z.parent.cor = PRETO;
                     y.cor = PRETO;
                     z.parent.parent.cor = VERM;
                     z = z.parent.parent;
                 } else {
                     if (z == z.parent.dir) {
                         z = z.parent;
                         esqRotate(z);
                     }
                     z.parent.cor = PRETO;
                     z.parent.parent.cor = VERM;
                     dirRotate(z.parent.parent);
                 }
             } else {
                 if (z.parent == z.parent.parent.dir) {
                     NoRB<T> y = z.parent.parent.esq;
                     if (y.cor == VERM) {
                         z.parent.cor = PRETO;
                         y.cor = PRETO;
                         z.parent.parent.cor = VERM;
                         z = z.parent.parent;
                     } else {
                         if (z == z.parent.esq) {
                             z = z.parent;
                             dirRotate(z);
                         }
                         z.parent.cor = PRETO;
                         z.parent.parent.cor = VERM;
                         esqRotate(z.parent.parent);
                     }
                 }
             }
         }
         raiz.cor = PRETO;
     }
  
     public void insere(T chave) {
         NoRB<T> novo = new NoRB<T>(chave);
         insere(novo);
     }
  
     private NoRB<T> remove(NoRB<T> z) {
         NoRB<T> y;
         NoRB<T> x;
         if (z.esq == nil || z.dir == nil) {
             y = z;
         } else {
             y = sucessor(z);
         }
  
         if (y.esq != nil) {
             x = y.esq;
         } else {
             x = y.dir;
         }
         x.parent = y.parent;
         if (y.parent == nil) {
             raiz = x;
         } else {
             if (y == y.parent.esq) {
                 y.parent.esq = x;
             } else {
                 y.parent.dir = x;
             }
         }
         if (y != z) {
             z.chave = y.chave;
         }
         if (y.cor == PRETO) {
             deleteFixUp(x);
         }
         return y;
     }
  
     private void deleteFixUp(NoRB<T> x) {
         NoRB<T> w;
         while (x != raiz && x.cor == PRETO) {
             if (x == x.parent.esq) {
                 w = x.parent.dir;
                 if (w.cor == VERM) {
                     w.cor = PRETO;
                     x.parent.cor = VERM;
                     esqRotate(x.parent);
                     w = x.parent.dir;
                 }
                 if (w.esq.cor == PRETO && w.dir.cor == PRETO) {
                     w.cor = VERM;
                     x = x.parent;
                 } else {
                     if (w.dir.cor == PRETO) {
                         w.esq.cor = PRETO;
                         w.cor = VERM;
                         dirRotate(w);
                         w = x.parent.dir;
                     }
                     w.cor = x.parent.cor;
                     x.parent.cor = PRETO;
                     w.dir.cor = PRETO;
                     esqRotate(x.parent);
                     x = raiz;
                 }
             } else {
                 w = x.parent.esq;
                 if (w.cor == VERM) {
                     w.cor = PRETO;
                     x.parent.cor = VERM;
                     dirRotate(x.parent);
                     w = x.parent.esq;
                 }
                 if (w.dir.cor == PRETO && w.esq.cor == PRETO) {
                     w.cor = VERM;
                     x = x.parent;
                 } else {
                     if (w.esq.cor == PRETO) {
                         w.dir.cor = PRETO;
                         w.cor = VERM;
                         esqRotate(w);
                         w = x.parent.esq;
                     }
                     w.cor = x.parent.cor;
                     x.parent.cor = PRETO;
                     w.esq.cor = PRETO;
                     dirRotate(x.parent);
                     x = raiz;
                 }
             }
         }
         x.cor = PRETO;
     }
  
     public NoRB<T> search(T chave) {
  
         NoRB<T> aux = raiz;
  
         while (aux != nil) {
             if (chave.compareTo(aux.chave) < 0) {
                 aux = aux.esq;
             } else if (chave.compareTo(aux.chave) > 0) {
                 aux = aux.dir;
             } else if (chave.compareTo(aux.chave) == 0) {
                 return aux;
             }
         }
  
         return null;
  
     }
  
     private NoRB<T> sucessor(NoRB<T> z) {
         NoRB<T> aux = z.dir;
         while (aux.esq != nil) {
             aux = aux.esq;
         }
         return aux;
     }
  
     public void remove(T chave) {
         NoRB<T> no = search(chave);
         remove(no);
     }
  
     public void PreOrder(NoRB<T> raiz) {
  
         NoRB<T> aux = raiz;
         if (aux == nil) {
             return;
         }
         System.out.println(aux.chave);
         PreOrder(raiz.esq);
         PreOrder(raiz.dir);
     }
  
     public void imprime() {
      PreOrder(raiz);
     }
}

Árvore Binária

Árvores binárias são estruturas de dados adequadas para a representação de hierarquias. Composta por um conjunto de nós, onde existe um nó R (raiz) que contém zero ou mais subárvores, cujas ráizes são ligadas diretamente a R.

A raiz se liga a um ou mais elementos e cada um destes forma uma nova subárvore. Esses elementos são seus galhos ou filhos.

Representação:

Implementação:

package arvoreBinariaDeBusca;

public class Arvore {

private No raiz;

public Arvore()
{
raiz = null;
}

void inserir (int dado)
{
raiz = insere(raiz, dado);
}

private No insere (No r, int x)
{
if (r == null)
{
No novo = new No(x);
return novo;
} else if (r.dado < x)
{
r.esq = insere (r.esq, x);
}
else if (r.dado > x)
{
r.dir = insere(r.dir, x);
}
return r;
}

public void mostrar() //Recursivo está no caderno
{
System.out.println("Pre Ordem");
mostrarPreOrdem(raiz);
System.out.println("\nIn Ordem");
mostrarInOrdem(raiz);
System.out.println("\nPos Ordem");
mostrarPosOrdem(raiz);
}

private void mostrarPreOrdem(No no)//Exibe os elementos da direita e depois os da esquerda
{
if (no != null)
{
System.out.print(no.dado + " ");
mostrarPreOrdem(no.dir);
mostrarPreOrdem(no.esq);
}
}

private void mostrarInOrdem(No no)//Exibe os elementos da direita da raiz, volta para a raiz, exibe os elementos da esquerda dela, exibindo o da direita de cada folha
{
if (no != null)
{
mostrarPreOrdem(no.esq);
System.out.print(no.dado + " ");
mostrarPreOrdem(no.dir);
}
}

private void mostrarPosOrdem(No no)//Exibe os elementos da direita e depois os da esquerda
{
if (no != null)
{
mostrarPreOrdem(no.esq);
mostrarPreOrdem(no.dir);
System.out.print(no.dado + " ");
}
}

}

Lista duplamente ligada circular

Uma lista duplamente encadeada é uma representação de uma sequência de objetos na memória do computador. Cada elemento da sequência é armazenado em um nó da lista, com dois ponteiros, um que aponta para o nó anterior e o outro para o seguinte.

Representação:

Implementação:

package listaDuplamenteLigada;

public class ListaDupla {

private No primeira;
private No ultima;
private int totalDeElementos;

public void adicionaNoComeco(int dado) {
if (this.totalDeElementos == 0) {
No novo = new No(dado);
this.primeira = novo;
this.ultima = novo;
novo.setAnterior(novo);
novo.setProxima(novo);

} else {
No novo = new No(this.primeira, dado);
novo.setAnterior(ultima);
ultima.setProxima(novo);
ultima = novo;
primeira.setAnterior(ultima);
}
this.totalDeElementos++;
}

void mostrar() {
if (primeira != null) {
No p = primeira;

do {
System.out.println(p.getDado());
p = p.getProxima();
} while (p != primeira);
}
}

}

Lista simples encadeada

Uma lista encadeada é uma representação de uma sequência de objetos na memória do computador. Cada elemento da sequência é armazenado em um nó da lista, com um ponteiro referenciando ao próximo nó.

Implementação :

package lista;


public class Lista {
 
 private No inicio;
 
 public Lista ()
 {
  inicio = null;
 }
 
 void mostrar ()
 {
  for (No p = inicio; p != null; p = p.prox)
  {
   System.out.println(p.dado);
  }
 }
 
 void inserir (int n)
 {
  inserirFim(n);
 }
 
 @SuppressWarnings("unused")
 private void inserirInicio(int n)
 {
  No novo = new No(n);
  novo.prox = inicio;
  inicio = novo;
 }
 
 private void inserirFim (int n)
 {
  No novo = new No(n);
  if (inicio == null)
  {
   inicio = novo;
  }else{
   No p = inicio;
   while (p.prox != null)
   {
    p = p.prox;
   }
   p.prox = novo;
  }
 }
 
 void remover (int n)
 {
  if (inicio != null)
  {
   No ant, p;
   p = inicio;
   ant = null;
   
   while(p != null && p.dado != n)
   {
    ant = p;
    p = p.prox;
   }
   
   if (p != null)
   {
    if (ant == null)
    {
     inicio = p.prox;
    }else{
     ant.prox = p.prox;
    }
    p = null;
   }
  }
 }
 
 void inverter()
 {
  
 }

}