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

18

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.

dan_waterworth
la source
En termes d'efficacité et de facilité de mise en œuvre, les efficacités générales sont bien définies, mais pour votre mise en œuvre, je pense que la meilleure chose serait d'implémenter autant que vous pouvez trouver et de nous faire ensuite savoir ce qui fonctionne le mieux ...
glenatron

Réponses:

15

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.

Quick Joe Smith
la source
1
Personnellement, je trouve l'insert rouge-noir plus facile que l'insert AVL. La raison en est l'analogie (imparfaite) aux arbres B. Les insertions sont délicates, mais les suppressions sont mauvaises (autant de cas à considérer). En fait, je n'ai plus moi-même d'implémentation de suppression C ++ rouge-noir - je l'ai supprimée quand j'ai réalisé (1) que je ne l'utilisais jamais - chaque fois que je voulais supprimer, je supprimais plusieurs éléments, alors j'ai converti de l'arborescence en liste, supprimer de la liste, puis reconvertir en un arbre, et (2) il a quand même été cassé.
Steve314
2
@ Steve314, les arbres rouge-noir sont plus faciles, mais vous n'avez pas pu faire une implémentation qui fonctionne? À quoi ressemblent les arbres AVL?
dan_waterworth
@dan_waterworth - Je n'ai pas encore réalisé d'implémentation avec une méthode d'insertion qui fonctionne - j'ai des notes, comprenez le principe de base, mais je n'ai jamais eu la bonne combinaison de motivation, de temps et de confiance. Si je voulais juste des versions qui fonctionnent, c'est juste copier-pseudocode-à-partir d'un manuel et traduire (et n'oubliez pas que C ++ a des conteneurs de bibliothèque standard), mais où est le plaisir?
Steve314
BTW - Je pense (mais je ne peux pas fournir la référence) qu'un manuel assez populaire comprend une implémentation buggée de l'un des algorithmes d'arbre binaire équilibré - pas sûr, mais il pourrait être supprimé rouge-noir. Donc ce n'est pas seulement moi ;-)
Steve314
1
@ Steve314, je sais, les arbres peuvent être diaboliquement compliqués dans un langage impératif, mais étonnamment, les implémenter dans Haskell a été un jeu d'enfant. J'ai écrit un arbre AVL régulier et également une variante spatiale 1D au cours du week-end et ils ne sont tous les deux qu'environ 60 lignes.
dan_waterworth
10

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é)

Matthieu M.
la source
J'aime vraiment les listes de sauts et je les ai déjà implémentées, mais pas dans un langage fonctionnel. Je pense que je vais les essayer après cela, mais en ce moment je suis sur des arbres auto-équilibrés.
dan_waterworth
De plus, les gens utilisent souvent des skiplists pour des structures de données simultanées. Il peut être préférable, au lieu de forcer l'immuabilité, d'utiliser les primitives de concurrence de haskell (comme MVar ou TVar). Cependant, cela ne m'apprendra pas beaucoup sur l'écriture de code fonctionnel.
dan_waterworth
2
@ Fanatic23, une Skip List n'est pas un ADT. L'ADT est soit un ensemble, soit un tableau associatif.
dan_waterworth
@dan_waterworth mon mauvais, vous avez raison.
Fanatic23
5

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).

Steve314
la source
1
+1. Treaps est mon choix personnel, j'ai même écrit un article de blog sur la façon dont ils sont mis en œuvre.
P Shved
5

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à.

S.Lott
la source
3

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.

Steve314
la source
Les splays sont un peu ennuyeux étant donné qu'ils modifient l'arbre même lors de la recherche. Ce serait assez douloureux dans des environnements multi-threads, ce qui est l'une des grandes motivations pour utiliser un langage fonctionnel comme Haskell en premier lieu. Là encore, je n'ai jamais utilisé de langages fonctionnels auparavant, donc ce n'est peut-être pas un facteur.
Quick Joe Smith, du
@Quick - dépend de la façon dont vous avez l'intention d'utiliser l'arborescence. Si vous l'utilisiez dans un véritable code de style fonctionnel, vous abandonneriez la mutation à chaque découverte (rendant un arbre Splay un peu idiot), ou vous finiriez par dupliquer une partie substantielle de l'arbre binaire à chaque recherche, et gardez une trace de l'état de l'arbre avec lequel vous travaillez au fur et à mesure que votre travail progresse (la raison pour laquelle vous utilisez probablement un style monadique). Cette copie peut être optimisée par le compilateur si vous ne référencez plus l'ancien état de l'arbre après la création du nouveau (des hypothèses similaires sont courantes dans la programmation fonctionnelle), mais ce n'est pas le cas.
Steve314
Aucune des deux approches ne vaut l'effort. Là encore, ni les langages purement fonctionnels pour la plupart.
Quick Joe Smith
1
@Quick - Dupliquer l'arborescence est ce que vous ferez pour toute structure de données d'arborescence dans un langage fonctionnel pur pour les algorithmes de mutation tels que les insertions. En termes de source, le code ne sera pas si différent du code impératif qui fait des mises à jour sur place. Les différences ont déjà été gérées, vraisemblablement, pour les arbres binaires non équilibrés. Tant que vous n'essayez pas d'ajouter des liens parents aux nœuds, les doublons partageront au moins des sous-arbres communs, et l'optimisation approfondie dans Haskell est assez hardcore sinon parfaite. Je suis moi-même anti-Haskell en principe, mais ce n'est pas nécessairement un problème.
Steve314
2

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.

Petr Pudlák
la source