class Vozlisce:

    def __init__(self, kljuc=None):
        ''' Ustvari vozlišče drevesa:
        - Vozlisce() ustvari prazno vozlišče
        - Vozlisce(kljuc) ustvari vozlišče z danim podatkom ključ
        '''
        self.kljuc = kljuc
        self.levi = None
        self.desni = None


class AVLDrevo:

    def __init__(self):
        ''' Ustvari prazno AVL drevo. '''
        self.koren = None
        self.visina = -1
        self.ravnotezje = 0

    def __repr__(self, zamik=''):
        if self.prazno():
            return 'AVLDrevo()'.format(zamik)
        elif self.koren.levi.prazno() and self.koren.desni.prazno():
            return 'AVLDrevo({1})'.format(zamik, self.koren.kljuc)
        else:
           return 'AVLDrevo({1},\n{0}      levo = {2},\n{0}      desno = {3})'.\
               format(
                   zamik,
                   self.koren.kljuc,
                   self.koren.levi.__repr__(zamik + '             '),
                   self.koren.desni.__repr__(zamik + '              ')
               )

    def prazno(self):
        ''' Vrne True, če je drevo prazno, sicer vrne False. '''
        return self.koren is None

    def pravilno(self, mini=-float("inf"), maxi=float("inf")):
        ''' vrne True, če je dvojiško drevo AVL drevo in False, če ni '''
        if self.prazno():
            return True
        if self.koren.kljuc < mini or self.koren.kljuc > maxi:
            return False
        return self.koren.levi.pravilno(mini, self.koren.kljuc - 1) and \
               self.koren.desni.pravilno(self.koren.kljuc + 1, maxi) and abs(self.ravnotezje) <= 1

    def vstavi(self, kljuc):
        ''' vstavi nov podatek na ustrezno mesto v AVL drevesu '''
        if self.prazno():
            self.koren = Vozlisce(kljuc)
            self.koren.levi = AVLDrevo()
            self.koren.desni = AVLDrevo()
        elif kljuc < self.koren.kljuc:
            self.koren.levi.vstavi(kljuc)
        elif kljuc > self.koren.kljuc:
            self.koren.desni.vstavi(kljuc)
        self.visina = max(self.koren.levi.visina, self.koren.desni.visina) + 1
        self.ravnotezje = self.koren.levi.visina - self.koren.desni.visina
        self.popravi()

    def popravi(self):
        pass  # To metodo bomo implementirali kasneje.