class noh:
    def __init__(self, dado):
        self.dado = dado
        self.esq = None
        self.dir = None
        self.altura = 0

def imprime(raiz):
    if raiz == None:
        return
    print('[' + str(raiz.dado), end=", ")
    imprime(raiz.esq)
    print(", ", end='')
    imprime(raiz.dir)
    print("]", end="")

def altura(raiz):
    if raiz == None:
        return -1
    return raiz.altura

def rotacionaDireita(y):
    novaRaiz = y.esq
    y.esq = novaRaiz.dir
    novaRaiz.dir = y
    
    y.altura = max(altura(y.esq), altura(y.dir)) + 1
    novaRaiz.altura = max(altura(novaRaiz.esq), altura(novaRaiz.dir)) + 1

    return novaRaiz

def rotacionaEsquerda(y):
    novaRaiz = y.dir
    y.dir = novaRaiz.esq
    novaRaiz.esq = y

    y.altura = max(altura(y.esq), altura(y.dir)) + 1
    novaRaiz.altura = max(altura(novaRaiz.esq), altura(novaRaiz.dir)) + 1
    return novaRaiz

def fatorBalanceamento(raiz):
    return altura(raiz.esq) - altura(raiz.dir)

#***********************************************
# A FUNÇÃO INSERE AINDA ESTÁ INCOMPLETA, ela não rotaciona 
# adequadamente quanto a árvore pende para a direita
#***********************************************

def insere(raiz, dado):
    if raiz  == None:
        return noh(dado)
    
    if raiz.dado == dado:
        #dado repetido, nao inserir
        return raiz
    elif dado < raiz.dado:
        #inserir na esquerda
        raiz.esq = insere(raiz.esq, dado)
        if fatorBalanceamento(raiz) == 2:
            if dado > raiz.esq.dado:
                #adicionei no meio
                raiz.esq = rotacionaEsquerda(raiz.esq)
            raiz = rotacionaDireita(raiz)
    elif dado > raiz.dado:
        #inserir na direita
        raiz.dir = insere(raiz.dir, dado)

    #arruma altura
    raiz.altura = max(altura(raiz.esq), altura(raiz.dir)) + 1 
    return raiz

#***********************************************
# FALTA A FUNÇÃO DE BUSCA
#***********************************************

arvore = None
arvore = insere(arvore, 6)
arvore = insere(arvore, 4)
imprime(arvore)
print()

arvore = insere(arvore, 5)
imprime(arvore)
print()