3ª Contribuição de Pesquisa

Arvore B

class No:
    def __init__(self, folha=False):
        self.chave = [] 
        self.filho    = []  
        self.folha = folha
        
    def __str__(self):
        if self.folha:
            return "Noh folha da arvore com {0} chave\n\tChave:{1}\n\tfilho:{2}\n".format(len(self.chave), self.chave, self.filho)
        else:
            return "Noh interno da arvore com {0} chave, {1} filho\n\tChave:{2}\n\n".format(len(self.chave), len(self.filho), self.chave, self.filho)

class arvB:
    def __init__(self, t):
        self.raiz = No(folha=True)
        self.t = t
        
    def insere(self, chave):
        r = self.raiz
        if len(r.chave) == (2*self.t) - 1:   
            s = No()
            self.raiz = s
            s.filho.insert(0, r)                 
            self.divSubArv(s, 0)            
            self.insInc(s, chave)
        else:
            self.insInc(r, chave)
    
    def insInc(self, x, chave):
        i = len(x.chave) - 1
        if x.folha:
            x.chave.append(0)
            while i >= 0 and chave < x.chave[i]:
                x.chave[i+1] = x.chave[i]
                i -= 1
            x.chave[i+1] = chave
        else:
            while i >= 0 and chave < x.chave[i]:
                i -= 1
            i += 1
            if len(x.filho[i].chave) == (2*self.t) - 1:
                self.divSubArv(x, i)
                if chave > x.chave[i]:
                    i += 1
            self.insInc(x.filho[i], chave)

    def buscar(self, chave, x=None):
        if isinstance(x, No):
            i = 0
            while i < len(x.chave) and chave > x.chave[i]:   
                i += 1
            if i < len(x.chave) and chave == x.chave[i]:      
                return (x, i)
            elif x.folha:                               
                return None
            else:                                      
                return self.buscar(chave, x.filho[i])
        else:                                        
            return self.buscar(chave, self.raiz)
        
    def divSubArv(self, x, i):
        t = self.t
        y = x.filho[i]
        z = No(folha=y.folha)
        
        x.filho.insert(i+1, z)
        x.chave.insert(i, y.chave[t-1])

        z.chave = y.chave[t:(2*t - 1)]
        y.chave = y.chave[0:(t-1)]
        
        if not y.folha:
            z.filho = y.filho[t:(2*t)]
            y.filho = y.filho[0:(t-1)]    
        
    def __str__(self):
        r = self.raiz
        return r.__str__() + '\n'.join([child.__str__() for child in r.filho])  

if __name__ == "__main__":
    arvB = arvB(3)
    arvB.insere(5)
    arvB.insere(6)
    arvB.insere(7)
    arvB.insere(8)
    arvB.insere(9)
    arvB.insere(10)
    arvB.insere(1)

    x, i = arvB.buscar(9)

    print("Indice da Pesquisa: {}\n".format(i))

    print(arvB)