Un árbol de búsqueda binaria es un árbol binario con un invariante de ordenamiento: para cada nodo, todas las claves en su subárbol izquierdo son menores, y todas las claves en su subárbol derecho son mayores. Esto te permite buscar dividiendo el problema por la mitad en cada paso.
8
/ \
3 10
/ \ \
1 6 14 left < node < right at every node
def search(node, key):
while node:
if key == node.val: return node
node = node.left if key < node.val else node.right # go one way
return None
def insert(node, key):
if node is None: return Node(key)
if key < node.val: node.left = insert(node.left, key)
else: node.right = insert(node.right, key)
return node
| Operación | Equilibrado | Peor caso (degenerado) |
|---|---|---|
| búsqueda | O(log n) | O(n) |
| inserción | O(log n) | O(n) |
| eliminación | O(log n) | O(n) |
El peor caso ocurre cuando las claves se insertan en orden ordenado — el árbol se degenera en una lista enlazada de altura n.
Los BST te proporcionan datos dinámicos ordenados con operaciones logarítmicas — el ancestro conceptual de los índices de bases de datos y los mapas ordenados.
El problema de degeneración motiva árboles autoequilibrados, un tema de seguimiento clave en entrevistas.