Mission

Mission : sauver l'index d'utilisateurs qui rame après la migration

Diagnostiquer un BST dégénéré causé par un ordre d'insertion trié et raisonner sur la suppression d'un noeud à deux enfants.

Contexte

Une équipe a migré 50 000 utilisateurs vers un nouvel index construit comme un BST, en insérant les identifiants dans l'ordre croissant où ils existaient déjà en base (donc déjà triés). Depuis la migration, les recherches par identifiant sont devenues aussi lentes qu'un parcours de liste complète, et personne ne comprend pourquoi le BST "ne sert à rien".