SoloCodigo
Programación Web y Scripting => Python => Mensaje iniciado por: sepultura en Domingo 27 de Mayo de 2007, 13:31
-
Buenas, despues de pasarme programando una clase de arbol binario unas quantas horas, e decidido implementarle un balanceo mediante la altura (AVL), pero no me funciona bien, les pido ayuda porque ya nose que mas intentar, aca les dejo el codigo de mi programa, aver si hay algun error que uds, pueden ver y yo no soy capaz:class CTree(object):
__slots__ = ['__root', '__left', '__right']
def __init__(self):
self.__root = None
self.__left = None
self.__right = None
def plant(self, data, left, right):
self.__root = data
self.__left = left
self.__right = right
def insert(self, data):
a = CTree()
b = CTree()
if self.__root == None:
self.plant(data, a, b )
elif data < self.__root:
self.__left.insert(data)
self.balance()
elif data > self.__root:
self.__right.insert(data)
self.balance()
else:
raise ValueError, 'Element already exists'
def search(self, data):
if self.__root == None:
return None
elif self.__root == data:
return self.__root
else:
if self.__root < data:
return self.__right.search(data)
else:
return self.__left.search(data)
def height(self):
if self.__root == None:
return 0
else:
return (1 + max(self.__left.height(), self.__right.height()))
def size(self):
if self.__root == None:
return 0
else:
return (1 + self.__left.size() + self.__right.size())
def rotacio_s(self,left):
aux = CTree()
if left == 1:
aux.plant(self.__left,self.__left.left,self.__root)
elif left == 0:
aux.plant(self.__right,self.__root,self.__right.right)
self = aux
def rotacio_d(self,left):
if left == 1:
self.__left.rotacio_s(0)
self.rotacio_s(1)
elif left == 0:
self.__right.rotacio_s(1)
self.rotacio_s(0)
def balance(self):
if self.__root != None:
if ((self.__left.height() - self.__right.height()) == 2):
if (self.__left.left.height() >= self.__left.right.height()):
self.rotacio_s(1)
else:
self.rotacio_d(1)
elif (self.__right.height() - self.__left.height() == 2):
if (self.__right.right.height() >= self.__right.left.height()):
self.rotacio_s(0)
else:
self.rotacio_d(0)
def __str__(self):
if self.__root == None:
return ('NULL')
else:
return(str(self.__root) + '-' + str(self.__left) + '-' + str(self.__right))
rotacio_s, es la rotacion simple, rotacio_d, es la rotacion doble, espero ke me puedan ayudar, yo sigo trabajando en ello aver k tal :comp: gracias
-
bueno, ya lo e resuelto, por si a alguien le interesa , la solucion pasaba por canviar la rotacion simple, tal que quedase asi:
def rotacio_s (self,left):
if (left):
aux = CTree()
aux.plant (self.__root,self.__left.__right,self.__right)
self.plant (self.__left.__root,self.__left.__left,aux)
else:
aux = CTree()
aux.plant (self.__root,self.__left,self.__right.__left)
self.plant (self.__right.__root,aux,self.__right.__right)
xaooo :hola:
PD: plant, es una funcion para plantar arboles nuevos