3
Pour un arbre de recherche équilibré, il s'agit de O (log (N)) pour tous les cas. Pour les arbres de recherche déséquilibrés, le cas le plus défavorable est O (N), par exemple insert 1, 2, 3, 4, ... et la meilleure des cas est quand il est équilibré, par exemple insert 6, 4, 8, 3, 5 Comment définir la complexité moyenne des cas pour un arbre de recherche déséquilibré?Quelle est la profondeur asymptotique moyenne d'un arbre de recherche déséquilibré simple?
Je m'attendrais à propos de 'O (n^.5)' en raison de la similarité avec les marches aléatoires, mais je ne publie pas de réponse car je ne peux pas vraiment le prouver. BTW, si c'est un devoir, pourriez-vous l'étiqueter comme tel? – pavpanchekha
ce n'est pas des devoirs. C'est par curiosité que la plupart des arbres de recherche dans les bibliothèques standard en C++, Java sont implémentés comme déséquilibrés. – user236215
C'est trop dur pour faire ses devoirs. –