Un árbol binario de búsqueda (ABB o BST) organiza los datos de modo que cada nodo cumple la regla: los valores del subárbol izquierdo son menores que el valor del nodo y los del subárbol derecho son mayores o iguales. Esto permite localizar elementos en tiempo logarítmico cuando el árbol está balanceado y facilita algoritmos de ordenación y filtrado en Python.
Utilizamos el mismo modelo de nodo presentado en los temas anteriores, lo que nos permite compartir funciones de inserción y recorridos sin modificaciones.
class Nodo:
def __init__(self, valor, nivel=0):
self.valor = valor
self.izquierdo = None
self.derecho = None
self.nivel = nivel
class ArbolBusqueda:
def __init__(self):
self.raiz = None
self.cantidad = 0
La inserción sigue el mismo patrón que en el tema 3: avanzamos según la comparación y colocamos el nodo en la primera referencia nula.
class ArbolBusqueda:
# ...
def crear_nodo(self, valor, nivel=0):
return Nodo(valor, nivel=nivel)
def insertar(self, valor):
if self.raiz is None:
self.raiz = self.crear_nodo(valor)
self.cantidad = 1
return self.raiz
actual = self.raiz
while True:
if valor < actual.valor:
if actual.izquierdo is None:
actual.izquierdo = self.crear_nodo(valor, nivel=actual.nivel + 1)
self.cantidad += 1
return actual.izquierdo
actual = actual.izquierdo
else:
if actual.derecho is None:
actual.derecho = self.crear_nodo(valor, nivel=actual.nivel + 1)
self.cantidad += 1
return actual.derecho
actual = actual.derecho
Encontrar un valor aprovecha la misma regla. Si el valor buscado es menor que el nodo actual, exploramos el subárbol izquierdo; de lo contrario, el derecho.
def buscar_abb(nodo, valor):
while nodo:
if valor == nodo.valor:
return nodo
nodo = nodo.izquierdo if valor < nodo.valor else nodo.derecho
return None
El mínimo se obtiene siguiendo la rama izquierda hasta encontrar una hoja. El máximo aplica el mismo principio hacia la derecha.
def minimo(nodo):
if nodo is None:
return None
while nodo.izquierdo:
nodo = nodo.izquierdo
return nodo
def maximo(nodo):
if nodo is None:
return None
while nodo.derecho:
nodo = nodo.derecho
return nodo
Eliminar un nodo requiere manejar tres casos clásicos:
def eliminar_abb(raiz, valor):
if raiz is None:
return None
if valor < raiz.valor:
raiz.izquierdo = eliminar_abb(raiz.izquierdo, valor)
elif valor > raiz.valor:
raiz.derecho = eliminar_abb(raiz.derecho, valor)
else:
if raiz.izquierdo is None:
return raiz.derecho
if raiz.derecho is None:
return raiz.izquierdo
sucesor = minimo(raiz.derecho)
raiz.valor = sucesor.valor
raiz.derecho = eliminar_abb(raiz.derecho, sucesor.valor)
return raiz
Cuando el código proviene de fuentes externas conviene validar que el árbol respete la regla de ordenamiento. Esto se logra comprobando rangos permitidos en cada nodo.
def es_abb(nodo, minimo_val, maximo_val):
if nodo is None:
return True
if nodo.valor < minimo_val or nodo.valor > maximo_val:
return False
return es_abb(nodo.izquierdo, minimo_val, nodo.valor - 1) and es_abb(nodo.derecho, nodo.valor + 1, maximo_val)
Un ABB puede degradarse a una lista cuando los datos llegan casi ordenados. Para mitigar el problema:
El siguiente programa integra inserción, búsqueda, obtención de extremos y eliminación en un ABB.
class Nodo:
def __init__(self, valor, nivel=0):
self.valor = valor
self.izquierdo = None
self.derecho = None
self.nivel = nivel
class ArbolBusqueda:
def __init__(self):
self.raiz = None
self.cantidad = 0
def crear_nodo(self, valor, nivel=0):
return Nodo(valor, nivel=nivel)
def insertar(self, valor):
if self.raiz is None:
self.raiz = self.crear_nodo(valor)
self.cantidad = 1
return self.raiz
actual = self.raiz
while True:
if valor < actual.valor:
if actual.izquierdo is None:
actual.izquierdo = self.crear_nodo(valor, nivel=actual.nivel + 1)
self.cantidad += 1
return actual.izquierdo
actual = actual.izquierdo
else:
if actual.derecho is None:
actual.derecho = self.crear_nodo(valor, nivel=actual.nivel + 1)
self.cantidad += 1
return actual.derecho
actual = actual.derecho
def buscar(self, valor):
actual = self.raiz
while actual:
if valor == actual.valor:
return actual
actual = actual.izquierdo if valor < actual.valor else actual.derecho
return None
def minimo(self, nodo):
if nodo is None:
return None
while nodo.izquierdo:
nodo = nodo.izquierdo
return nodo
def eliminar(self, nodo, valor):
if nodo is None:
return None
if valor < nodo.valor:
nodo.izquierdo = self.eliminar(nodo.izquierdo, valor)
elif valor > nodo.valor:
nodo.derecho = self.eliminar(nodo.derecho, valor)
else:
if nodo.izquierdo is None:
return nodo.derecho
if nodo.derecho is None:
return nodo.izquierdo
sucesor = self.minimo(nodo.derecho)
nodo.valor = sucesor.valor
nodo.derecho = self.eliminar(nodo.derecho, sucesor.valor)
return nodo
def imprimir_inorden(self, nodo):
if nodo is None:
return
self.imprimir_inorden(nodo.izquierdo)
print(nodo.valor, end=" ")
self.imprimir_inorden(nodo.derecho)
def limpiar(self, nodo):
if nodo is None:
return
self.limpiar(nodo.izquierdo)
self.limpiar(nodo.derecho)
nodo.izquierdo = None
nodo.derecho = None
if __name__ == "__main__":
abb = ArbolBusqueda()
for valor in [15, 8, 20, 4, 10, 17, 25]:
abb.insertar(valor)
print("Inorden:")
abb.imprimir_inorden(abb.raiz)
objetivo = 10
encontrado = abb.buscar(objetivo)
print(f"\nBuscar {objetivo}: {'hallado' if encontrado else 'no encontrado'}")
abb.raiz = abb.eliminar(abb.raiz, 15)
print("Inorden tras eliminar la raiz:")
abb.imprimir_inorden(abb.raiz)
print()
abb.limpiar(abb.raiz)
abb.raiz = None
abb.cantidad = 0