il y a t'il quelques chose de plus performant dans les arbre binaire de recherche pour effectuer une recherche dans un arbre?

ben tu as toutes sortes d'arbres qui s'équilibrent tous seuls ...

Les B-Trees ou arbres de Bayer, par exemple. Ce sont des arbres équilibrés où chaque noeud contient plusieurs dizaines de données, et où la profondeur dépasse rarement 3 ou 4. C'est typiquement ce qu'on utilise pour implémenter les index dans les bases de données.

A part les algorithme de complexité O(log²(n)) (recherche dichotomique, arbre binaire) pour la recherche, je ne connais rien de plus performant sachant que leur complexité estr deja TRES bonne.
Si kk1 a une solution jsuis preneur

rien de mieux qu'un arbre binaire. ne pas confondre les RB_tree et autres arbre auto-équilibrants, donc le rôle est de maintenir l'équilibre

 
ben si tu veux une BONNE recherche rapide dans ton arbre, t'a besoin de le tenir equilibre pour rester constamment en complexite O(log²(n)) sinon dans le PIRE des cas, ton arbre binaire vas ressembler a une liste chainee ! => complexité O(n) (ce qui est nettement moins efficace. Il te faut donc des arbres AVL.

oui, mais étant donné un arbre binaire, y a pas de méthode plus rapide. tu ne m'as pas compris

Bah pour indexer du texte le plus simple c'est d'utiliser pour chaque étage une lettre du mot. C'est assez performant et simple à mettre en place (truc qui est utilisé pour la compression huffmann quoi)

 
ouaip perso j'ai bricolé le concept pour accelerer la chose (ca ne marche qu'avec eds ensembles bien disparate, sinon on retombe sur ce que tu dis la)

La structure de données utilisée pour un index dépend directement du type de données utilisées et, éventuellement, du support utilisé pour stocker la structure de données.
 
Si tout est en mémoire, on n'a pas les même contraintes que si la structure est sur disque. Parce que dans ce dernier cas, il faut réduire au maximum le nombre de noeuds auxquels on accède, quitte à disposer de gros noeuds (2, 4 ou 8 Ko, typiquement).
 
Mais si c'est en mémoire, un arbre de recherche plus classique -- et plus simple à implémenter -- ou une table de hachage fera l'affaire (Taz, avec une bonne fonction de hachage, une table de hachage est plus rapide qu'un arbre binaire).

Est ce que les propos avancés dans ce post sont de source sûr ?
J'ai recherché un peu ce que tu dis Giz avec google et j'arrive pas à retrouver tes chiffres sur la complexité. Aurais-tu une adresse ou je pourrais vérifier ?
Et est ce vrai comme le prétend Biface qu'une table de hachage avec une bonne fonction de hachage est plus rapide qu'un arbre binaire ?

Ca dépend ®

J'adore tes réponses

Ou peut on trouver un algorithme de B tree detaillé

 
Je comprends pas tres bien la question, tu voudrais construire un arbre pour effectuer une recherche dans un arbre ?
Si tu veux reduire fortement les acces disques : B-arbres (utilisé dans les SGBD)
Sinon t'as les "skew heaps" qui sont excellents (fusion, insertion, supprMin en O(log n))...