Fenómeno

Las búsquedas se volvieron lentas

Un servicio guarda pedidos en un árbol de búsqueda por número de pedido. En pruebas, con pedidos al azar, buscar era rapidísimo. En producción, los números de pedido son consecutivos: 1, 2, 3… Tras un millón de pedidos, buscar el último tarda un millón de pasos.

Mucha gente cree que un árbol de búsqueda tiende a quedar equilibrado por sí solo. En un estudio, el 45 % no creía posible que insertar costara O(n).

Piensa antes de seguir: si insertas 1, 2, 3, 4 y 5 en ese orden en un BST vacío, ¿qué forma tiene?