Á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);
     }
}