Arboles AVL en python
Nota: el objeto visitante hace el recorrido en amplitud de un arbol, acá se usa para la implementación.
1 """
2 Funcionalidad: Implementación de arboles AVL en python.
3 Autor: Diego Andrés Sanabria (diegueus9)
4 Fecha: Noviembre de 2005
5 """
6 from visitante import *
7 def mayor(a,b):
8 if a>b:
9 return a
10 else:
11 return b
12
13 class arbavl:
14 def __init__(self,dato):
15 self.izq=None
16 self.der=None
17 self.alt=0
18 self.nivel=None
19 self.fe=None
20 self.clave=dato
21 # Es la función que inserta un dato en el arbol
22 def insertar(self, dato):
23 # si la clave es menor que el dato a insertar
24 if self.clave<dato:
25 # si el hijo de derecha es nulo
26 if self.der==None:
27 # entonces cree el hijo de izq con el dato
28 self.der=arbavl(dato)
29 # si el hijo de derecha es nulo
30 else:
31 self.der.insertar(dato)
32 elif self.clave>dato:
33 if self.izq==None:
34 self.izq=arbavl(dato)
35 else:
36 self.izq.insertar(dato)
37 else:
38 print "El dato "+str(dato)+"ya existe"
39 def balancear(self):
40 if self.izq!=None:
41 self.izq=self.izq.balancear()
42 self.izq.actNivel(self.nivel+1)
43 self.izq.actfe()
44 if self.der!=None:
45 self.der=self.der.balancear()
46 self.der.actNivel(self.nivel+1)
47 self.der.actfe()
48 self.actfe()
49 print "*************************"
50 print self.clave
51 print self.fe
52 if self.izq:
53 print self.izq.fe
54 if self.der:
55 print self.der.fe
56 if self.fe==-2 and (self.izq.fe==-1 or self.izq.fe==0):
57 print "Rotación Simple Derecha"
58 return self.rotsd()
59 elif self.fe==-2 and self.izq.fe==1:
60 print "Rotación Izquierda Derecha"
61 return self.rotid()
62 elif self.fe==2 and (self.der.fe==1 or self.der.fe==0):
63 print "Rotación Simple Izquierda"
64 return self.rotsi()
65 elif self.fe==2 and self.der.fe==-1:
66 print "Rotación Derecha Izquierda"
67 return self.rotdi()
68 else: # self.fe==-1 or self.fe==0 or self.fe==1
69 print "El arbol "+str(self.clave)+" esta balanceado"
70 return self
71 def menor(self):
72 if self.clave!=None:
73 if self.izq!=None:
74 return self.izq.menor()
75 else:
76 return self.clave
77 def borrar(self,dato):
78 if self.clave==dato:
79 if self.izq==None and self.der==None:
80 return None
81 elif self.izq!=None and self.der==None:
82 self.clave=self.izq.clave
83 self.der=self.izq.der
84 self.izq=self.izq.izq
85 return self
86 elif self.der==None and self.der==None:
87 self.clave=self.der.clave
88 self.der=self.der.der
89 self.der=self.der.izq
90 return self
91 else:
92 tmp=self.der.menor()
93 self.clave=tmp
94 self.der=self.der.borrar(tmp)
95 return self
96 elif self.clave<dato:
97 if self.der:
98 self.der=self.der.borrar(dato)
99 else:
100 print "El dato no esta en el arbol"
101 return self
102 elif self.clave>dato:
103 if self.izq:
104 self.izq=self.izq.borrar(dato)
105 else:
106 print "El dato no esta en el arbol"
107 return self
108 def rotsd(self):
109 p=self
110 q=self.izq
111 p.izq=q.der
112 q.der=p
113 return q
114 def rotsi(self):
115 p=self
116 q=self.der
117 p.der=q.izq
118 q.izq=p
119 return q
120 def rotid(self):
121 p=self
122 q=self.izq
123 r=self.izq.der
124 q.der=r.izq
125 p.izq=r
126 r.izq=q
127 p.izq=r.der
128 r.der=p
129 return r
130 def rotdi(self):
131 p=self
132 q=self.der
133 r=self.der.izq
134 q.izq=r.der
135 p.der=r
136 r.der=q
137 p.der=r.izq
138 r.izq=p
139 return r
140 def obtNivel(self):
141 if self.izq!=None and self.der!=None:
142 return mayor(self.izq.obtNivel(),self.der.obtNivel())
143 elif self.izq!=None and self.der==None:
144 return self.izq.obtNivel()
145 elif self.izq==None and self.der!=None:
146 return self.der.obtNivel()
147 else:
148 return self.nivel
149 def obtfe(self):
150 self.fe=0
151 if self.izq!=None and self.der!=None:
152 self.fe=self.der.obtNivel()-self.izq.obtNivel()
153 elif self.izq!=None and self.der==None:
154 self.fe=self.nivel-self.izq.obtNivel()
155 elif self.izq==None and self.der!=None:
156 self.fe=self.der.obtNivel()-self.nivel
157 else:
158 self.fe=0
159 return self.fe
160 def actNivel(self,nivel=0):
161 self.nivel=nivel
162 if self.izq!=None:
163 self.izq.actNivel(self.nivel+1)
164 if self.der!=None:
165 self.der.actNivel(self.nivel+1)
166 def actfe(self):
167 self.obtfe()
168 if self.izq!=None:
169 self.izq.actfe()
170 if self.der!=None:
171 self.der.actfe()
172 def __repr__(self):
173 a=""
174 a=a+str(self.clave)+","+str(self.nivel)+","+str(self.fe)+"\n"
175 if self.izq:
176 a=a+str(self.izq)
177 if self.der:
178 a=a+str(self.der)
179 return a
180 class ArbolAVL:
181 def __init__(self):
182 self.arb=None
183 def insertar(self,dato):
184 if self.arb==None:
185 self.arb=arbavl(dato)
186 self.arb.actNivel()
187 self.arb.actfe()
188 else:
189 self.arb.insertar(dato)
190 self.arb.actNivel()
191 self.arb.actfe()
192 self.arb=self.arb.balancear()
193 self.arb.actNivel()
194 self.arb.actfe()
195 def eliminar(self,dato):
196 self.arb=self.arb.borrar(dato)
197 if self.arb:
198 self.arb.actNivel()
199 self.arb.actfe()
200 self.arb=self.arb.balancear()
201 self.arb.actNivel()
202 self.arb.actfe()
203 def buscar(self,dato):
204 if self.clave==dato:
205 return True
206 elif self.clave>dato:
207 if self.izq:
208 return self.izq.buscar(dato)
209 else:
210 return False
211 elif self.clave<dato:
212 if self.der:
213 return self.der.buscar(dato)
214 else:
215 return False
216 def __repr__(self):
217 tmp=Visitante()
218 b=tmp.amplitud(self.arb)
219 tmp=None
220 return b