Arbres binaires

Résolu/Fermé

k-23 Messages postés 252 Date d'inscription mardi 4 mars 2008 Statut Membre Dernière intervention 25 novembre 2014 - 15 avril 2008 à 20:42
mamiemando Messages postés 33468 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 20 janvier 2025 - 16 avril 2008 à 10:23

Bonjour,

un arbres binaire de recherche A contient n nombres on dit que la taille de A est n

je voudrais savoir quel est le nombre maximum de comparaison qu'une insertion d,un nombre dans un arbres binaires de recherche n peut faire?

on me dit qu'il y a une formule je la trouve pas

A voir également:

Arbres binaires
Binaires - Guide
Calculs binaires - Forum Matériel & Système
Les données de chaîne ou binaires seront tronquées. ✓ - Forum Bases de données
Compter le nombre de tables dans une base ✓ - Forum Programmation
{SQL Server} Problemes avec Source de données ODBC ✓ - Forum SQL Server

1 réponse

Réponse 1 / 1

mamiemando Messages postés 33468 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 20 janvier 2025 7 813
16 avril 2008 à 10:23

Si c'est un arbre équilibre (arbre rouge noir par exemple) c'est du O(log(n))
https://en.wikipedia.org/wiki/Red-black_tree

Preuve "intuitive" : l'arbre est équilibré et à chaque branchement chaque individu est séparé en deux groupes de même taille (à 1 près). La hauteur de l'arbre est donc vérifie donc 2^h = n, soit h = log(n)/log(2). Comme il y a autant d'évaluation que d'étage dans l'arbre (soit h), la complexité est bien du O(log(n))

Bonne chance

Discussions similaires

SQL! données de chaine ou binaires tronquées

données chaîne ou binaires seront tronquées.

{SQL Server} Update d'une chaine de caractaire

Chaîne contenant ' sous SQL

Arbres dans twilight