import java.util.Scanner;

/**
 * Propriedades das árvores rubro-negras:
 * 
 * (1) - Todo nó é RUBRO ou NEGRO
 * 
 * (2) - A raiz é NEGRA
 * 
 * (3) - Toda folha (NIL) é NEGRA
 * 
 * (4) - Se um nó é RUBRO, então seus filhos são NEGROS
 * 
 * (5) - Todos os caminhos partindo de um nó qualquer até suas folhas contêm o
 * mesmo número de nós NEGROS
 * 
 */
public class ARN {

	enum Cor {
		RUBRO, NEGRO;
	}

	final No NIL = new No(Cor.NEGRO);

	private class No {
		No esq;
		No dir;
		No pai;
		Cor cor;
		int elemento;

		// "construtor do NIL"
		No(Cor cor) {
			this.cor = cor;
		}

		// "construtor dos nós internos"
		No(int elemento, Cor cor) {
			this.elemento = elemento;
			this.cor = cor;
			this.pai = NIL;
			this.esq = NIL;
			this.dir = NIL;
		}

		void setEsq(No esq) {
			this.esq = esq;
			esq.pai = this;
		}

		void setDir(No dir) {
			this.dir = dir;
			dir.pai = this;
		}

		void entraNoLugarDe(No x) {
			this.pai = x.pai;

			if (x.pai == NIL) {
				raiz = this;
			} else if (x == x.pai.esq) {
				x.pai.esq = this;
			} else {
				x.pai.dir = this;
			}
		}
	}

	// árvore vazia <=> raiz = NIL
	private No raiz = NIL;

	public boolean vazio() {
		return raiz == NIL;
	}

	public void insere(int elemento) {
		if (vazio()) {
			raiz = new No(elemento, Cor.NEGRO);
		} else {
			insere(raiz, elemento);

			// a raiz pode ter sido pintada de RUBRO no método fixUp
			raiz.cor = Cor.NEGRO;
		}
	}

	private void insere(No raizSubArv, int elemento) {
		if (elemento < raizSubArv.elemento) {
			if (raizSubArv.esq == NIL) {
				raizSubArv.setEsq(new No(elemento, Cor.RUBRO));
				fixUp(raizSubArv.esq);
			} else {
				insere(raizSubArv.esq, elemento);
			}
		} else {
			if (raizSubArv.dir == NIL) {
				raizSubArv.setDir(new No(elemento, Cor.RUBRO));
				fixUp(raizSubArv.dir);
			} else {
				insere(raizSubArv.dir, elemento);
			}
		}
	}

	private void fixUp(No z) {
		// não há violação da propriedade (4) ?
		if (z.pai.cor.equals(Cor.NEGRO)) {
			return;
		}

		// y é o tio de z
		No y = z.pai.pai.dir;
		boolean yEhFilhoDir = true;

		if (z.pai.pai.dir == z.pai) {
			y = z.pai.pai.esq;
			yEhFilhoDir = false;
		}

		// y é RUBRO
		if (y.cor.equals(Cor.RUBRO)) {
			y.cor = Cor.NEGRO;
			z.pai.cor = Cor.NEGRO;
			z.pai.pai.cor = Cor.RUBRO;
			fixUp(z.pai.pai);
		} else {
			if (yEhFilhoDir) {
				// y é NEGRO e z é filho direito
				if (y.cor.equals(Cor.NEGRO) && z.pai.dir == z) {
					rotacionaEsq(z.pai);
					z = z.esq;
				}

				// y é NEGRO e z é filho esquerdo
				z.pai.cor = Cor.NEGRO;
				z.pai.pai.cor = Cor.RUBRO;
				rotacionaDir(z.pai.pai);
			} else {
				// y é NEGRO e z é filho esquerdo
				if (y.cor.equals(Cor.NEGRO) && z.pai.esq == z) {
					rotacionaDir(z.pai);
					z = z.dir;
				}

				// y é NEGRO e z é filho direito
				z.pai.cor = Cor.NEGRO;
				z.pai.pai.cor = Cor.RUBRO;
				rotacionaEsq(z.pai.pai);
			}
		}
	}

	private void rotacionaEsq(No x) {
		No y = x.dir;

		// x.dir <-> y.esq
		x.setDir(y.esq);

		// y.pai <-> x.pai
		y.entraNoLugarDe(x);

		// y.esq <-> x
		y.setEsq(x);
	}

	private void rotacionaDir(No x) {
		No y = x.esq;

		// x.esq <-> y.dir
		x.setEsq(y.dir);

		// y.pai <-> x.pai
		y.entraNoLugarDe(x);

		// y.dir <-> x
		y.setDir(x);
	}

	public boolean busca(int elemento) {
		return busca(raiz, elemento);
	}

	private boolean busca(No raizSubArv, int elemento) {
		if (raizSubArv == NIL) {
			return false;
		}

		if (elemento == raizSubArv.elemento) {
			return true;
		}

		if (elemento < raizSubArv.elemento) {
			return busca(raizSubArv.esq, elemento);
		}

		return busca(raizSubArv.dir, elemento);
	}

	public void imprimePreOrdem() {
		if (vazio()) {
			System.out.println("[]");
		} else {
			StringBuffer str = new StringBuffer("[");
			imprimePreOrdem(raiz, str);
			str.delete(str.length() - 2, str.length());
			str.append("]");
			System.out.println(str);
		}
	}

	private void imprimePreOrdem(No raizSubArv, StringBuffer str) {
		if (raizSubArv != NIL) {
			if (raizSubArv.cor.equals(Cor.NEGRO)) {
				str.append(raizSubArv.elemento + "N, ");
			} else {
				str.append(raizSubArv.elemento + "R, ");
			}

			imprimePreOrdem(raizSubArv.esq, str);
			imprimePreOrdem(raizSubArv.dir, str);
		}
	}

	private int getAltura(No raizSubArv) {
		if (raizSubArv == NIL) {
			return -1;
		}

		int altEsq = getAltura(raizSubArv.esq);
		int altDir = getAltura(raizSubArv.dir);
		return Math.max(altEsq, altDir) + 1;
	}

	private int getAlturaNegra(No raizSubArv) {
		if (raizSubArv == NIL) {
			return 0;
		}

		int altEsq = getAlturaNegra(raizSubArv.esq);
		int altDir = getAlturaNegra(raizSubArv.dir);

		if (raizSubArv.esq.cor.equals(Cor.NEGRO)) {
			altEsq++;
		}

		if (raizSubArv.dir.cor.equals(Cor.NEGRO)) {
			altDir++;
		}

		if (altEsq != altDir) {
			throw new RuntimeException("Problema com a altura negra!");
		}

		return altDir;
	}

	public int getAltura() {
		return getAltura(raiz);
	}

	public int getAlturaNegra() {
		return getAlturaNegra(raiz);
	}

	public static void main(String[] args) {
		ARN abb = new ARN();
		Scanner in = new Scanner(System.in);

		while (true) {
			System.out.println("Digite o comando: ");
			String line = in.nextLine();

			if (line.contains("fecha")) {
				in.close();
				return;
			} else if (line.contains("altura")) {
				System.out.println("altura = " + abb.getAltura());
			} else if (line.contains("insere")) {
				int elemento = Integer.parseInt(line.split("\\s+")[1]);
				abb.insere(elemento);
			} else if (line.contains("altura-negra")) {
				System.out.println("altura negra = " + abb.getAlturaNegra());
			} else if (line.contains("busca")) {
				int elemento = Integer.parseInt(line.split("\\s+")[1]);

				if (abb.busca(elemento)) {
					System.out.println("Elemento encontrado com sucesso!");
				} else {
					System.out.println("Elemento não encontrado!");
				}
			} else {
				System.err.println("Comando Inválido!");
				System.out.println();

			}

			abb.imprimePreOrdem();
			System.err.flush();
			System.out.flush();
		}
	}
}