Trade-offs

¿Merece la pena balancear?

Un programa inserta un millón de claves que llegan al azar (no ordenadas), y nunca borra.

Un programa inserta un millón de claves que hoy llegan al azar y nunca borra. ¿Necesita un árbol balanceado?No, nunca: un BST simple queda balanceado por sí solo con cualquier orden de llegada de clavesNo: con claves al azar, un BST simple garantiza O(log n) en el peor caso de cualquier operaciónCon claves al azar, el BST simple queda bajo; sin garantía del orden de llegada, conviene el balanceadoSí, siempre: un BST simple es O(n) en cualquier caso, también con claves llegadas al azar