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