Binary search trees · Árboles binarios de búsqueda
Binary search trees
- A binary search tree (BST) stores values so they stay sorted and are fast to find.
- Each node holds a value and links to up to two children: a
leftand aright. - The top node is the root. A node with no children is a leaf.
Á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.
The BST rule
- For every node: everything in its left subtree is smaller, everything in its right is larger.
- This one rule is what lets you find a value by going left or right — never both.
La regla del BST
- Para cada nodo: todo lo que está en su subárbol izquierdo es menor, y todo lo que está en el derecho es mayor.
- 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
A node
- We model a node as a small object with a
value, aleft, and aright. - A brand-new node has no children yet, so
leftandrightstart asNone.
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
Inserting a value
- Start at the root. If the tree is empty, the new value becomes the root.
- If the value is smaller than the current node, go left; otherwise go right.
- Repeat until you reach an empty spot, and put the new node there.
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
In-order traversal gives sorted order
- In-order traversal visits: the left subtree, then the node, then the right subtree.
- Because of the BST rule, this visits the values in sorted order — for free.
- It is naturally recursive: traverse left, take the value, traverse right.
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]
Searching is fast
- To find a value, compare it with the node, then go left or right — skipping half the tree each step.
- In a balanced tree this takes about
O(log n)steps, much faster than scanning a list. - A badly-shaped tree (values inserted already sorted) can degrade to a line —
O(n).
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)—.
Common mistakes
- In a binary search tree: left child < node < right child.
- An unbalanced tree loses the speed advantage.
Errores comunes
- En un árbol binario de búsqueda: hijo izquierdo < nodo < hijo derecho.
- Un árbol desequilibrado pierde la ventaja de velocidad.
Now you try
- Build the three core operations:
insert,in_order, andcontains. - The
Nodeclass (and a workinginsert, where you need it) is provided. - Press Check answer to test it on several trees.
Ahora tú intentas
- 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.
Searching a BST · Búsqueda en un BST
Left is smaller, right is bigger — so each step skips half the tree. · La izquierda es menor, la derecha es mayor — así que cada paso descarta la mitad del árbol.
The · El Node class is provided. Write insert(root, value) that adds value to the BST and returns the root. If root is None, return a new Node(value). If value < root.value go left, otherwise go right — and reassign that child to the result of inserting into it. · 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.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Node and a working insert are provided. Write in_order(root) that returns a list of the values from an in-order traversal: left subtree, then this node's value, then right subtree. Thanks to the BST rule the list comes out sorted. An empty tree (None) gives []. · 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 [].
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Node and a working insert are provided. Write contains(root, value) that returns True if value is in the tree, else False. Use the BST rule: if it equals this node return True; if it is smaller search left · izquierda, otherwise search right · derecha; an empty branch (None) means it is not there. · 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í.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.