Les arbres de recherche binaires randomisés comme treap donnent une bonne performance (de l'ordre de O (log n)) avec une probabilité élevée tout en évitant les opérations de rééquilibrage compliquées (et coûteuses) nécessaires aux arbres déterministes équilibrés comme AVL, red-blackm, AA, etc.arbres de recherche binaires randomisés
Nous savons que si nous ajoutons des clés aléatoires à un simple BST, nous pouvons nous attendre à ce qu'il soit raisonnablement équilibré. Une raison simple est que le nombre d'arbres lourdement non équilibrés pour n nœuds est beaucoup plus faible que le nombre d'arbres «presque équilibrés» et donc, un ordre aléatoire pour l'insertion des clés est susceptible de se retrouver avec un arbre acceptable. Dans ce cas, dans «L'art de la programmation par ordinateur», Knuth donne un peu plus de 1,3 * lg2 (n) que la longueur moyenne d'un chemin qui est plutôt bon. Il dit aussi que en supprimant une clé aléatoire de l'arbre aléatoire préserve son caractère aléatoire (et donc son bon équilibrage moyen).
Il semble donc qu'un arbre de recherche binaire dans lequel les clés sont insérées et supprimées dans un ordre aléatoire donnerait probablement des performances de l'ordre de O (log n) pour les trois opérations: recherche, insertion et suppression.
Cela dit, je me demande si l'approche suivante donnerait les mêmes bonnes propriétés:
- prendre une fonction de hachage h (x) qui est connu pour être « bon » (par exemple, il assurer une répartition homogène de les touches)
- utilisez la commande définie par h (x) sur les touches au lieu de la commande sur k.
- en cas de collision, commander en fonction de la clé. Cela devrait être rare si la clé de hachage est assez bonne et la gamme de la fonction de hachage est beaucoup plus grande que l'ensemble des touches.
Pour donner un exemple, un BST pour la touche {4, 3, 5, 1, 2} inséré dans cet ordre, serait:
4
/\
3 5
/\
1 2
En supposant que la fonction de hachage serait les associer à (respectivement) {221,142,12,380,18) nous aurions.
221(4)
/ \
142(3) 380(1)
/ \
12(5) 18(2)
Le point clé est que BST peut dégénérer « régulière » car les touches sont insérées selon la même relation de commande qui est utilisé pour les stocker dans l'arbre (leur ordre « naturel », par exemple l'ordre alphabétique de la chaîne) mais la fonction de hachage induit un ordre sur les clés qui n'a aucun rapport avec le caractère "naturel" et, par conséquent, devrait donner les mêmes résultats que si les clés étaient insérées dans un ordre aléatoire.
Une hypothèse forte est que la fonction de hachage est "bonne", mais ce n'est pas déraisonnable, je pense.
Je n'ai trouvé aucune référence à une approche similaire dans la littérature, donc cela pourrait être complètement faux, mais je ne vois pas pourquoi!
Voyez-vous un inconvénient dans mon raisonnement? Quelqu'un a déjà essayé de le faire?