class noh:
    def __init__(self, dado):
        self.dado = dado
        self.esq = None
        self.dir = None
        self.cor = True

def rotacionaEsquerda(y):
    x = y.dir
    y.dir = x.esq
    x.esq = y
    x.cor = y.cor
    y.cor = True
    return x


def rotacionaDireita(y):
    x = y.esq
    y.esq = x.dir
    x.dir = y
    x.cor = y.cor
    y.cor = True
    return x

def sobeVermelho(y):
    y.cor = True
    y.esq.cor = False
    y.dir.cor = False

def ehVermelho(y):
    if y == None:
        return False
    else:
        return y.cor

def ehNegro(y):
    if y == None:
        return True
    else:
        return y.cor == False


def insere_aux(raiz, dado):
    if raiz == None:
        return noh(dado)
    elif dado < raiz.dado:
        raiz.esq = insere_aux(raiz.esq, dado)
    elif dado > raiz.dado:
        raiz.dir = insere_aux(raiz.dir, dado)
    else:
        #jah existe esse dado, ignorar
        return raiz

    if ehVermelho(raiz.dir) and ehNegro(raiz.esq):
        raiz = rotacionaEsquerda(raiz)
    if ehVermelho(raiz.esq) and ehVermelho(raiz.esq.esq):
        raiz = rotacionaDireita(raiz)
    if ehVermelho(raiz.esq) and ehVermelho(raiz.dir):
        sobeVermelho(raiz)
    return raiz

def insere(raiz, dado):
    raiz = insere_aux(raiz, dado)
    raiz.cor = False
    return raiz

def busca(raiz, dado):
    if raiz == None:
        return raiz
    if dado < raiz.dado:
        return busca(raiz.esq, dado)
    if dado > raiz.dado:
        return busca(raiz.dir, dado)
    return raiz

arvore = None

insere(arvore, 5)
insere(arvore, 7)
insere(arvore, 3)