1 """
   2 Funcionalidad: Arboles B+ en python
   3 Autor: Diego Andrés Sanabria Martín (diegueus9)
   4 Licencia: GPL v2.0
   5 Fecha: Noviembre de 2005
   6 Nota: Este código es en un 95% igual al de arboles b, solo se adicionan dos lineas
   7 para modificar el comportamiento al de una arbol b +.
   8 """
   9 class Arbol:
  10     def __init__(self):
  11         self.pagina=[]
  12         self.hijos=[]
  13         self.pad=None
  14     def __repr__(self,nivel=0):
  15         r=""
  16         r=r+"Nivel : "+str(nivel)+" "+str(self.pagina)+"\n"
  17         for i in range(len(self.hijos)):
  18             r=r+self.hijos[i].__repr__(nivel+1)
  19         return r
  20     def insertar(self,dato,min,max,padre=None):
  21         tmp=[]
  22         # Guarda el supuesto puntero al padre
  23         self.pad=padre
  24         try:
  25             self.pagina.index(dato)
  26             return self
  27         except:
  28             # Si el arbol es nulo y no tiene nada
  29             if len(self.pagina)==0:
  30                 self.pagina.append(dato)
  31             # Si aun no se llenado la pagina
  32             elif len(self.pagina)<max and self.pad==None and len(self.hijos)==0:
  33                 self.pagina.append(dato)
  34                 self.pagina.sort()
  35             # Si no se llena la pagina pero hay hijos
  36             elif len(self.pagina)<max and self.pad==None and len(self.hijos)!=0:
  37                 estaInsertado=False
  38                 for iterador in range(len(self.pagina)):
  39                     if dato<self.pagina[iterador] and not estaInsertado:
  40                         self.hijos[iterador].insertar(dato,min,max,self)
  41                         estaInsertado=True
  42                 if not estaInsertado:
  43                     self.hijos[iterador+1].insertar(dato,min,max,self)
  44             # Si no se llena la pagina pero hay un padre y no hay hijos
  45             elif len(self.pagina)<max and self.pad!=None and len(self.hijos)==0:
  46                 self.pagina.append(dato)
  47                 self.pagina.sort()
  48             # Si no se llena la pagina y tengo un padre y unos hijos
  49             elif len(self.pagina)<max and self.pad!=None and len(self.hijos)!=0:
  50                 estaInsertado=False
  51                 for iterador in range(len(self.pagina)):
  52                     if dato<self.pagina[iterador] and not estaInsertado:
  53                         self.hijos[iterador].insertar(dato,min,max,self)
  54                         estaInsertado=True
  55                 if not estaInsertado:
  56                     self.hijos[iterador+1].insertar(dato,min,max,self)
  57             # Si la pagina ya esta llena y no tengo padre ni hijos
  58             elif len(self.pagina)==max and self.pad==None and len(self.hijos)==0:
  59                 self.pagina.append(dato)
  60                 self.pagina.sort()
  61                 for i in range(max/2):
  62                     tmp.append(self.pagina.pop())
  63                 dato=self.pagina.pop()
  64                 self.pad=Arbol()
  65                 self.pad.insertararriba(dato,min,max)
  66                 self.pad.hijos.append(self)
  67                 arboltmp=Arbol()
  68                 ########################ARBOL B+##################################
  69                 arboltmp.insertar(dato,min,max,self.pad)
  70                 ##################################################################
  71                 for a in range(len(tmp)):
  72                     arboltmp.insertar(tmp.pop(),min,max,self.pad)
  73                 self.pad.hijos.append(arboltmp)
  74             # Si la pagina ya esta llena pero tengo hijos
  75             elif len(self.pagina)==max and self.pad==None and len(self.hijos)!=0:
  76                 estaInsertado=False
  77                 for iterador in range(len(self.pagina)):
  78                     if dato<self.pagina[iterador] and not estaInsertado:
  79                         self.hijos[iterador].insertar(dato,min,max,self)
  80                         estaInsertado=True
  81                 if not estaInsertado:
  82                     self.hijos[iterador+1].insertar(dato,min,max,self)
  83             # Si la pagina esta llena no hay hijos pero si hay padre
  84             elif len(self.pagina)==max and self.pad!=None and len(self.hijos)==0:
  85                 self.pagina.append(dato)
  86                 self.pagina.sort()
  87                 for i in range(max/2):
  88                     tmp.append(self.pagina.pop())
  89                 dato=self.pagina.pop()
  90                 arboltmp=Arbol()
  91                 ########################ARBOL B+##################################
  92                 arboltmp.insertar(dato,min,max,self.pad)
  93                 ##################################################################
  94                 for a in range(len(tmp)):
  95                     arboltmp.insertar(tmp.pop(),min,max,self.pad)
  96                 self.pad.hijos.append(arboltmp)
  97                 self.pad.ordenarHijos()
  98                 self.pad.insertararriba(dato,min,max)
  99             # Si la pagina esta llena y no tiene padre pero si hijos
 100             elif len(self.pagina)==max and self.pad!=None and len(self.hijos)!=0:
 101                 estaInsertado=False
 102                 for iterador in range(len(self.pagina)):
 103                     if dato<self.pagina[iterador] and not estaInsertado :
 104                         self.hijos[iterador].insertar(dato,min,max,self)
 105                         estaInsertado=True
 106                 if not estaInsertado:
 107                     self.hijos[iterador+1].insertar(dato,min,max,self)
 108         return self.retornar()
 109     def insertararriba(self,dato,min,max):
 110         self.pagina.append(dato)
 111         self.pagina.sort()
 112         if len(self.pagina)>max:
 113             tmppag=[]
 114             tmphij=[]
 115             if self.pad==None:
 116                 self.pad=Arbol()
 117             self.pad.insertararriba(self.pagina.pop(max/2),min,max)
 118             arb=Arbol()
 119             for i in range(0,max/2):
 120                 tmppag.append(self.pagina.pop())
 121                 tmphij.append(self.hijos.pop())
 122             tmphij.append(self.hijos.pop())
 123             for a in range(0,len(tmppag)):
 124                     arb.insertar(tmppag.pop(),min,max,self.pad)
 125             arb.hijos=tmphij
 126             arb.ordenarHijos()
 127             try:
 128                 self.pad.hijos.index(self)
 129             except:
 130                 self.pad.hijos.append(self)
 131             self.pad.hijos.append(arb)
 132         self.retornar()
 133     def mayor(self):
 134         return self.pagina[len(self.pagina)-1]
 135     def menor(self):
 136         return self.pagina[0]
 137     def ordenarHijos(self):
 138         ultimo=len(self.hijos)-1
 139         for i in range(0,len(self.hijos)+1):
 140             for j in range(i+1,len(self.hijos)):
 141                 if self.hijos[i].mayor()>self.hijos[j].mayor():
 142                     tmp=self.hijos[i]
 143                     self.hijos[i]=self.hijos[j]
 144                     self.hijos[j]=tmp
 145     def buscar(self, dato):
 146         try:
 147             self.pagina.index(dato)
 148             print "El dato "+str(dato)+" ya esta en el arbol."
 149             return True
 150         except:
 151             estaenArbol=False
 152             for iterador in range(len(self.hijos)):
 153                 if dato<self.hijos[iterador].mayor() and not estaenArbol :
 154                     estaenArbol=self.hijos[iterador].buscar(dato)
 155             return estaenArbol
 156     def retornar(self):
 157         if self.pad!=None:
 158             return self.pad.retornar()
 159         else:
 160             return self
 161 class ArbolBplus:
 162     def __init__(self, d):
 163         self.dmax=2*d
 164         self.dmin=d
 165         self.raiz=Arbol()
 166     def insertar(self,dato):
 167         self.raiz=self.raiz.insertar(dato,self.dmin,self.dmax)
 168     def __repr__(self):
 169         return str(self.raiz)