Abstract FR:

Le sujet principal de cette thèse est l'étude asymptotique du profil des arbres binaires de recherche, c'est à dire la répartition des nuds de ces arbres par niveau de profondeur. Les résultats sont atteints en utilisant conjointement des techniques analytiques et probabilistes et s'étendent au cas des arbres binaires associés à l'algorithme classique de gestion d'équivalence" Union Find". Une étude porte également sur les arbres binaires de recherche multidimensionnels ou k-d arbres ; elle concerne une nouvelle méthode de choix des clés, imaginé par L. Devroye. Nous montrons que, avec cette méthode, le temps moyen mis par l'algorithme de Bentley pour répondre à une recherche d'orthogonale ou à une recherche de correspondances partielles est asymptotiquement optimal.