Quel arbre binaire auto-équilibré recommanderiez-vous?

J'apprends Haskell et comme exercice je fais des arbres binaires. Ayant créé un arbre binaire régulier, je souhaite l'adapter pour qu'il s'équilibre automatiquement. Donc:

• Quel est le plus efficace?
• Quelle est la plus simple à mettre en œuvre?
• Lequel est le plus utilisé?

Mais surtout, lequel recommandez-vous?

Je suppose que cela appartient ici car il est ouvert au débat.

Je vous recommande de commencer avec un arbre rouge-noir ou un arbre AVL .

L'arbre rouge-noir est plus rapide pour l'insertion, mais l'arbre AVL a un léger bord pour les recherches. L'arbre AVL est probablement un peu plus facile à implémenter, mais pas du tout basé sur ma propre expérience.

L'arbre AVL garantit que l'arbre est équilibré après chaque insertion ou suppression (aucun sous-arbre n'a un facteur d'équilibre supérieur à 1 / -1, tandis que l'arbre rouge-noir garantit que l'arbre est raisonnablement équilibré à tout moment.

Je considérerais une alternative si vous êtes d'accord avec les structures de données randomisées : Skip Lists .

D'un point de vue de haut niveau, c'est une structure arborescente, sauf qu'elle n'est pas implémentée comme un arbre mais comme une liste avec plusieurs couches de liens.

Vous obtiendrez O (log N) insertions / recherches / suppressions, et vous n'aurez pas à gérer tous ces cas de rééquilibrage délicats.

Je n'ai jamais envisagé de les implémenter dans un langage fonctionnel cependant, et la page wikipedia n'en affiche aucun, donc ce n'est peut-être pas facile (par rapport à l'immuabilité)

Si vous voulez commencer par une structure relativement facile (les arbres AVL et les arbres rouge-noir sont compliqués), une option est un treap - nommé comme une combinaison de "tree" et "heap".

Chaque nœud obtient une valeur de "priorité", souvent attribuée de manière aléatoire lors de la création du nœud. Les nœuds sont positionnés dans l'arborescence de sorte que l'ordre des clés soit respecté, et que l'ordre des tas de valeurs de priorité soit respecté. Le classement en tas signifie que les deux enfants d'un parent ont des priorités inférieures à celles du parent.

EDIT a supprimé "dans les valeurs de clé" ci-dessus - la priorité et l'ordre des clés s'appliquent ensemble, donc la priorité est importante même pour des clés uniques.

C'est une combinaison intéressante. Si les clés sont uniques et les priorités sont uniques, il existe une structure arborescente unique pour tout ensemble de nœuds. Même ainsi, les insertions et les suppressions sont efficaces. À strictement parler, l'arbre peut être déséquilibré au point où il s'agit effectivement d'une liste chaînée, mais cela est extrêmement peu probable (comme avec les arbres binaires standard), y compris pour les cas normaux tels que les clés insérées dans l'ordre (contrairement aux arbres binaires standard).

Quel est le plus efficace?

Vague et difficile à répondre. Les complexités informatiques sont toutes bien définies. Si c'est ce que vous entendez par efficacité, il n'y a pas vraiment de débat. En effet, tous les bons algorithmes sont livrés avec des preuves et des facteurs de complexité.

Si vous voulez dire «exécution» ou «utilisation de la mémoire», vous devrez comparer les implémentations réelles. Ensuite, la langue, l'exécution, le système d'exploitation et d'autres facteurs entrent en jeu, ce qui rend la question difficile à répondre.

Quelle est la plus simple à mettre en œuvre?

Vague et difficile à répondre. Certains algorithmes peuvent vous sembler complexes, mais triviaux pour moi.

Lequel est le plus utilisé?

Vague et difficile à répondre. Il y a d'abord le "par qui?" en partie? Haskell seulement? Et C ou C ++? Deuxièmement, il y a le problème du logiciel propriétaire où nous n'avons pas accès à la source pour faire une enquête.

Mais surtout, lequel recommandez-vous?

Je suppose que cela appartient ici car il est ouvert au débat.

Correct. Puisque vos autres critères ne sont pas très utiles, c'est tout ce que vous obtiendrez.

Vous pouvez obtenir la source d'un grand nombre d'algorithmes d'arborescence. Si vous voulez apprendre quelque chose, vous pouvez simplement implémenter tout ce que vous pouvez trouver. Plutôt que de demander une "recommandation", il vous suffit de collecter tous les algorithmes que vous pouvez trouver.

Voici la liste:

http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Il en existe six populaires. Commencez par ceux-là.

Si vous êtes intéressé par les arbres Splay, il existe une version plus simple de ceux qui, je crois, ont été décrits pour la première fois dans un article d'Allen et Munroe. Il n'a pas les mêmes garanties de performances, mais évite les complications liées au rééquilibrage "zig-zig" contre "zig-zag".

Fondamentalement, lors de la recherche (y compris la recherche d'un point d'insertion ou d'un nœud à supprimer), le nœud que vous trouvez est tourné directement vers la racine, de bas en haut (par exemple à la sortie d'une fonction de recherche récursive). À chaque étape, vous sélectionnez une seule rotation à gauche ou à droite selon que l'enfant que vous souhaitez faire remonter d'une autre étape vers la racine était l'enfant de droite ou l'enfant de gauche (si je me souviens bien de mes directions de rotation, c'est respectivement).

Comme les arbres Splay, l'idée est que les éléments récemment consultés sont toujours près de la racine de l'arbre, donc rapidement accessibles à nouveau. Plus simples, ces arbres de rotation à la racine Allen-Munroe (ce que j'appelle - je ne connais pas le nom officiel) peuvent être plus rapides, mais ils n'ont pas la même garantie de performance amortie.

Une chose - puisque cette structure de données, par définition, mute même pour les opérations de recherche, elle devrait probablement être implémentée de manière monadique. IOW ce n'est peut-être pas un bon choix pour la programmation fonctionnelle.

Un arbre équilibré très simple est un arbre AA . Son invariant est plus simple et donc plus facile à mettre en œuvre. En raison de sa simplicité, ses performances sont toujours bonnes.

En tant qu'exercice avancé, vous pouvez essayer d'utiliser des GADT pour implémenter l'une des variantes d'arbres équilibrés dont l'invariant est appliqué par le type type de système.