Árboles binarios de búsqueda
Árboles binarios de búsqueda
- Un árbol binario de búsqueda (BST, por sus siglas en inglés) almacena valores de manera que permanezcan ordenados y sean rápidos de encontrar.
- Cada nodo contiene un valor y enlaces hacia hasta dos hijos: uno
left(izquierdo) y otroright(derecho). - El nodo superior es la raíz. Un nodo sin hijos se denomina hoja.
La regla del BST
- Para cada nodo: todo en su subárbol izquierdo es menor, todo en su subárbol derecho es mayor o igual (esta lección envía valores iguales a la derecha).
- Esta única regla permite buscar un valor moviéndose solo a la izquierda o a la derecha —nunca a ambos lados—.
5
/ \
3 8
/ \ \
1 4 9
left < node <= right, at every node
Un nodo
- Modelamos un nodo como un pequeño objeto con un
value(valor), unleft(hijo izquierdo) y unright(hijo derecho). - Un nodo recién creado no tiene hijos aún, por lo que
leftyrightcomienzan comoNone.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
n = Node(5)
print(n.value) # 5
print(n.left) # None
Insertar un valor
- Comienza en la raíz. Si el árbol está vacío, el nuevo valor se convierte en la raíz.
- Si el valor es menor que el nodo actual, ve a la izquierda; de lo contrario, ve a la derecha.
- Repite hasta encontrar un espacio vacío e inserta el nuevo nodo allí.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
root = None
for v in [5, 3, 8, 1]:
root = insert(root, v)
print(root.value) # 5
print(root.left.value) # 3
print(root.right.value) # 8
El recorrido in-order da ordenamiento
- El recorrido in-order visita: el subárbol izquierdo, luego el nodo, y finalmente el subárbol derecho.
- Debido a la regla del BST, esto recorre los valores en orden ordenado —sin costo adicional—.
- Es naturalmente recursivo: recorrer a la izquierda, tomar el valor, recorrer a la derecha.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
def in_order(root):
if root is None:
return []
return in_order(root.left) + [root.value] + in_order(root.right)
root = None
for v in [5, 3, 8, 1, 4]:
root = insert(root, v)
print(in_order(root)) # [1, 3, 4, 5, 8]
Buscar es rápido
- Para encontrar un valor, compáralo con el nodo actual y muévete a la izquierda o derecha —descartando la mitad del árbol en cada paso—.
- En un árbol equilibrado, esto toma aproximadamente
O(log n)pasos, mucho más rápido que escanear una lista. - Un árbol mal estructurado (valores insertados ya ordenados) puede degradarse a una línea —complejidad
O(n)—.
Errores comunes
- En un árbol binario de búsqueda: hijo izquierdo < nodo <= hijo derecho (los valores iguales van a la derecha aquí).
- Un árbol desequilibrado pierde la ventaja de velocidad.
Ahora tú prueban
- Construye las tres operaciones fundamentales:
insert,in_orderycontains. - Se proporciona la clase
Node(y una funcióninsertfuncional cuando sea necesario). - Presiona Check answer para probarlo con varios árboles.
Búsqueda en un BST
La izquierda es menor, la derecha es mayor — así que cada paso descarta la mitad del árbol.
Dificultad 5/5 · 400 monedas + un pequeño bono en el primer intento de hoy
Se proporciona la clase Node. Escribe insert(root, value) que agregue value al BST y devuelva la raíz. Si root es None, devuelve un nuevo Node(value). Si value < root.value ve a la izquierda, de lo contrario ve a la derecha — y reasigna ese hijo al resultado de insertar en él.
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 5/5 · 400 monedas + un pequeño bono en el primer intento de hoy
Node y un insert funcional están proporcionados. Escribe in_order(root) que devuelva una lista de los valores de un recorrido in-order: subárbol izquierdo, luego el valor de este nodo, luego subárbol derecho. Gracias a la regla del BST la lista sale ordenada. Un árbol vacío (None) da [].
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 5/5 · 400 monedas + un pequeño bono en el primer intento de hoy
Node y un insert funcional están proporcionados. Escribe contains(root, value) que devuelva True si value está en el árbol, de lo contrario False. Usa la regla del BST: si es igual a este nodo devuelve True; si es menor busca izquierda, de lo contrario busca derecha; una rama vacía (None) significa que no está ahí.
Haz clic en Ejecutar para ver la salida aquí.