Question

J'ai vu des arbres binaires et des recherches binaires mentionnés dans plusieurs livres que j'ai lus récemment, mais comme je suis encore au début de mes études en informatique, je n'ai pas encore suivi de cours vraiment consacré aux algorithmes et aux données. structures de manière sérieuse.

J'ai vérifié les sources typiques (Wikipedia, Google) et la plupart des descriptions de l'utilité et de la mise en œuvre (en particulier) des arbres rouge-noir se sont révélées denses et difficiles à comprendre.Je suis sûr que pour quelqu'un avec l'expérience nécessaire, cela est parfaitement logique, mais pour le moment, cela se lit presque comme une langue étrangère.

Alors, qu’est-ce qui rend les arbres binaires utiles dans certaines des tâches courantes que vous effectuez lors de la programmation ?Au-delà de cela, quels arbres préférez-vous utiliser (veuillez inclure un exemple d’implémentation) et pourquoi ?

Était-ce utile?

La solution

Les arbres rouges noirs sont bons pour créer des arbres bien équilibrés.Le problème majeur des arbres de recherche binaires est que vous pouvez les déséquilibrer très facilement.Imaginez que votre premier chiffre soit un 15.Ensuite, tous les nombres suivants sont de plus en plus inférieurs à 15.Vous aurez un arbre très lourd du côté gauche et qui n'a rien du côté droit.

Les arbres rouges et noirs résolvent ce problème en forçant votre arbre à être équilibré chaque fois que vous insérez ou supprimez.Il y parvient grâce à une série de rotations entre les nœuds ancêtres et les nœuds enfants.L’algorithme est en fait assez simple, même s’il est un peu long.Je suggérerais de prendre le manuel CLRS (Cormen, Lieserson, Rivest et Stein), "Introduction aux algorithmes" et de lire sur les arbres RB.

L'implémentation n'est pas non plus si courte, il n'est donc probablement pas préférable de l'inclure ici.Néanmoins, les arbres sont utilisés largement pour les applications hautes performances nécessitant un accès à de nombreuses données.Ils fournissent un moyen très efficace de rechercher des nœuds, avec une surcharge d'insertion/suppression relativement faible.Encore une fois, je suggère de consulter CLRS pour savoir comment ils sont utilisés.

Bien que les BST ne puissent pas être utilisés explicitement, un exemple d'utilisation des arbres en général se trouve dans presque tous les SGBDR modernes.De même, votre système de fichiers est presque certainement représenté comme une sorte de structure arborescente, et les fichiers sont également indexés de cette façon.Les arbres alimentent Google.Les arbres alimentent presque tous les sites Web sur Internet.

Autres conseils

J'aimerais aborder uniquement la question "Alors, qu'est-ce qui rend les arbres binaires utiles dans certaines des tâches courantes que vous effectuez lors de la programmation ?"

C’est un sujet important sur lequel beaucoup de gens ne sont pas d’accord.Certains disent que les algorithmes enseignés dans un diplôme d'informatique, tels que les arbres de recherche binaires et les graphiques orientés, ne sont pas utilisés dans la programmation quotidienne et ne sont donc pas pertinents.D’autres ne sont pas d’accord, affirmant que ces algorithmes et structures de données constituent le fondement de toute notre programmation et qu’il est essentiel de les comprendre, même si vous n’avez jamais besoin d’en écrire un pour vous-même.Cela se reflète dans les conversations sur les bonnes pratiques d’entretien et d’embauche.Par exemple, Steve Yegge a un article sur entretien chez Google qui répond à cette question.Souvenez-vous de ce débat ;les gens expérimentés ne sont pas d’accord.

Dans une programmation commerciale typique, vous n'aurez peut-être pas besoin de créer des arbres binaires, voire même très souvent.Cependant, vous utiliserez de nombreuses classes qui fonctionnent en interne à l’aide d’arborescences.La plupart des classes d'organisation principales dans chaque langage utilisent des arbres et des hachages pour stocker et accéder aux données.

Si vous êtes impliqué dans des projets plus performants ou dans des situations qui sortent quelque peu des normes de la programmation commerciale, vous constaterez que les arbres seront un ami immédiat.Comme le disait une autre affiche, les arbres sont des structures de données de base pour les bases de données et les index de toutes sortes.Ils sont utiles pour l'exploration et la visualisation de données, les graphiques avancés (2D et 3D) et une foule d'autres problèmes informatiques.

J'ai utilisé des arbres binaires sous la forme de Arbres BSP (partitionnement d'espace binaire) en graphiques 3D.Je suis actuellement en train d'examiner à nouveau les arbres pour trier de grandes quantités de données géocodées et d'autres données destinées à la visualisation d'informations dans les applications Flash/Flex.Chaque fois que vous repoussez les limites du matériel ou que vous souhaitez fonctionner avec des spécifications matérielles inférieures, la compréhension et la sélection du meilleur algorithme peuvent faire la différence entre l'échec et le succès.

Aucune des réponses ne mentionne à quoi servent exactement les BST.

Si ce que vous voulez faire est simplement une recherche par valeurs, alors une table de hachage est beaucoup plus rapide, O(1) insère et recherche (meilleur des cas amortis).

Un BST sera une recherche O (log N) où N est le nombre de nœuds dans l'arborescence, les insertions sont également O (log N).

Les arbres RB et AVL sont importants comme une autre réponse mentionnée en raison de cette propriété, si un BST simple est créé avec des valeurs dans l'ordre, l'arbre sera aussi grand que le nombre de valeurs insérées, ce qui est mauvais pour les performances de recherche.

La différence entre les arbres RB et AVL réside dans les rotations nécessaires pour rééquilibrer après une insertion ou une suppression, les arbres AVL sont O (log N) pour les rééquilibrages tandis que les arbres RB sont O (1).Un exemple d'avantage de cette complexité constante est dans le cas où vous conservez une source de données persistante, si vous devez suivre les modifications à restaurer, vous devrez suivre les modifications possibles O (log N) avec une arborescence AVL.

Pourquoi seriez-vous prêt à payer le coût d’un arbre plutôt qu’une table de hachage ?COMMANDE!Les tables de hachage n'ont pas d'ordre, les BST en revanche sont toujours naturellement ordonnés en raison de leur structure.Donc, si vous vous retrouvez à jeter un tas de données dans un tableau ou un autre conteneur, puis à les trier plus tard, un BST peut être une meilleure solution.

La propriété order de l'arborescence vous offre un certain nombre de capacités d'itération ordonnées, dans l'ordre, en profondeur d'abord, en largeur d'abord, en pré-commande et en post-commande.Ces algorithmes d'itération sont utiles dans différentes circonstances si vous souhaitez les rechercher.

Les arbres rouges et noirs sont utilisés en interne dans presque tous les conteneurs ordonnés de bibliothèques de langage, C++ Set and Map, .NET SortedDictionary, Java TreeSet, etc...

Les arbres sont donc très utiles et vous pouvez les utiliser assez souvent sans même le savoir.Vous ne le ferez probablement jamais besoin d'en écrire un vous-même, même si je le recommande vivement comme exercice de programmation intéressant.

Les arbres rouges noirs et les arbres B sont utilisés dans toutes sortes de stockages persistants ;parce que les arbres sont équilibrés, les performances des traversées en largeur et en profondeur sont atténuées.

Presque tous les systèmes de bases de données modernes utilisent des arborescences pour le stockage des données.

Les BST font tourner le monde, comme le dit Michael.Si vous cherchez un bon arbre à mettre en œuvre, jetez un œil à Arbres AVL (Wikipédia).Ils ont une condition d’équilibrage, ils sont donc garantis O(logn).Ce type d’efficacité de recherche rend logique l’intégration dans tout type de processus d’indexation.La seule chose qui serait plus efficace serait une fonction de hachage, mais celles-ci deviennent laides rapidement, rapidement et à la hâte.De plus, vous tombez sur le Paradoxe d'anniversaire (également connu sous le nom de problème du casier).

Quel manuel utilisez-vous ?Nous avons utilisé Structures et analyse de données en Java par Mark Allen Weiss.En fait, je l'ai ouvert sur mes genoux pendant que j'écris ceci.Il contient une excellente section sur les arbres rouge-noir et comprend même le code nécessaire pour implémenter tous les arbres dont il parle.

Les arbres rouge-noir restent équilibrés, vous n'avez donc pas besoin de traverser en profondeur pour sortir les objets.Le temps gagné fait des arbres RB O(log()n)) dans le PIRE cas, alors que les arbres binaires malchanceux peuvent entrer dans une configuration déséquilibrée et provoquer des récupérations dans O(n) un mauvais cas.Cela se produit dans la pratique ou sur des données aléatoires.Ainsi, si vous avez besoin de code urgent (récupérations de bases de données, serveur réseau, etc.), vous utilisez des arborescences RB pour prendre en charge des listes/ensembles ordonnés ou non.

Mais les RBTrees sont pour les noobs !Si vous faites de l'IA et que vous devez effectuer une recherche, vous constaterez que vous fourchez beaucoup les informations d'état.Vous pouvez utiliser un rouge-noir persistant pour créer de nouveaux états dans O(log(n)).Un arbre persistant rouge noir conserve une copie de l'arbre avant et après une opération morphologique (insertion/suppression), mais sans copier l'arbre entier (normalement et opération O(log(n))).J'ai open source un arbre rouge-noir persistant pour Java

http://edinburghhacklab.com/2011/07/a-java-implementation-of-persistent-red-black-trees-open-sourced/

La meilleure description des arbres rouge-noir que j'ai vue est celle de « Introduction aux algorithmes » de Cormen, Leisersen et Rivest.Je pourrais même le comprendre suffisamment pour en implémenter partiellement un (insertion uniquement).Il existe également de nombreuses applets telles que Celui-ci sur diverses pages Web qui animent le processus et vous permettent de regarder et de parcourir une représentation graphique de l'algorithme construisant une structure arborescente.

Puisque vous demandez quel arbre les gens utilisent, vous devez savoir qu'un arbre Rouge Noir est fondamentalement un arbre B 2-3-4 (c'est-à-dire un arbre B d'ordre 4).Un arbre B est pas équivalent à un arbre binaire (comme demandé dans votre question).

Iciest une excellente ressource décrivant l'abstraction initiale connue sous le nom d'arbre B binaire symétrique qui a ensuite évolué pour devenir le RBTree.Vous auriez besoin d'une bonne compréhension des arbres B avant que cela ait du sens.Résumer:un lien « rouge » sur un arbre rouge noir est un moyen de représenter les nœuds qui font partie d'un nœud d'arbre B (valeurs dans une plage clé), tandis que les liens « noirs » sont des nœuds connectés verticalement dans un arbre B.

Voici donc ce que vous obtenez lorsque vous traduisez les règles d'un arbre Rouge Noir en termes d'arbre B (j'utilise le format Règle de l'arbre rouge noir => B Arbre équivalent):

1) Un nœud est soit rouge, soit noir.=> Un nœud dans un b-tree peut soit faire partie d'un nœud, soit être un nœud dans un nouveau niveau.

2) La racine est noire.(Cette règle est parfois omise, car elle n'affecte pas l'analyse) => Le nœud racine peut être considéré soit comme une partie d'un nœud racine interne, soit comme l'enfant d'un nœud parent imaginaire.

3) Toutes les feuilles (NIL) sont noires.(Toutes les feuilles sont de la même couleur que la racine.) => Puisqu'une façon de représenter un arbre RB consiste à omettre les feuilles, nous pouvons exclure cela.

4) Les deux enfants de chaque nœud rouge sont noirs.=> Les enfants d'un nœud interne dans un B-tree se trouvent toujours à un autre niveau.

5) Chaque chemin simple d'un nœud donné à l'une de ses feuilles descendantes contient le même nombre de nœuds noirs.=> Un arbre B reste équilibré car il nécessite que tous les nœuds feuilles soient à la même profondeur (par conséquent, la hauteur d'un nœud d'arbre B est représentée par le nombre de liens noirs de la racine à la feuille d'un arbre Rouge Noir )

Il existe également une implémentation « non standard » plus simple par Robert Sedgewick ici:(C'est l'auteur du livre Algorithmes avec Wayne)

Beaucoup, beaucoup de chaleur ici, mais pas beaucoup de lumière, alors voyons si nous pouvons en fournir.

D'abord, un arbre RB est une structure de données associative, contrairement, par exemple, à un tableau, qui ne peut pas prendre une clé et renvoyer une valeur associée, enfin, à moins qu'il ne s'agisse d'une "clé" entière dans un index clairsemé à 0 % d'entiers contigus.Un tableau ne peut pas non plus grandir en taille (oui, je connais aussi realloc(), mais sous les couvertures, cela nécessite un nouveau tableau puis un memcpy()), donc si vous avez l'une de ces exigences, un tableau ne fera pas l'affaire. .L'efficacité de la mémoire d'une baie est parfaite.Zéro déchet, mais pas très intelligent ni flexible - malgré realloc().

Deuxième, contrairement à un bsearch() sur un tableau d'éléments, qui EST une structure de données associative, un arbre RB peut croître (ET diminuer) en taille de manière dynamique.Le bsearch() fonctionne très bien pour indexer une structure de données d'une taille connue, qui restera cette taille.Donc, si vous ne connaissez pas la taille de vos données à l'avance, ou si de nouveaux éléments doivent être ajoutés ou supprimés, un bsearch() est disponible.Bsearch() et qsort() sont tous deux bien pris en charge en C classique et ont une bonne efficacité mémoire, mais ne sont pas assez dynamiques pour de nombreuses applications.Ce sont cependant mes préférés car ils sont rapides, faciles et si vous n'utilisez pas d'applications en temps réel, ils sont souvent suffisamment flexibles.De plus, en C/C++, vous pouvez trier un tableau de pointeurs vers des enregistrements de données, en pointant par exemple vers le membre struc{} que vous souhaitez comparer, puis en réorganisant le pointeur dans le tableau de pointeurs de telle sorte que la lecture des pointeurs dans l'ordre à la fin du tri par pointeur, vos données sont triées par ordre.Son utilisation avec des fichiers de données mappés en mémoire est extrêmement efficace en termes de mémoire, rapide et assez simple.Tout ce que vous avez à faire est d'ajouter quelques "*" à votre ou vos fonctions de comparaison.

Troisième, contrairement à une table de hachage, qui doit également avoir une taille fixe et ne peut pas être développée une fois remplie, un arbre RB se développera automatiquement et s'équilibrera pour maintenir sa garantie de performance O(log(n)).Surtout si la clé de l'arbre RB est un int, elle peut être plus rapide qu'un hachage, car même si la complexité d'une table de hachage est O(1), ce 1 peut être un calcul de hachage très coûteux.Les comparaisons d'entiers multiples d'une horloge d'un arbre surpassent souvent les calculs de hachage de plus de 100 horloges, sans parler du rehachage et de l'espace malloc() pour les collisions de hachage et les rehachages.Enfin, si vous souhaitez un accès ISAM, ainsi qu'un accès par clé à vos données, un hachage est exclu, car il n'y a pas d'ordre des données inhérent à la table de hachage, contrairement à l'ordre naturel des données dans toute implémentation arborescente.L'utilisation classique d'une table de hachage consiste à fournir un accès par clé à une table de mots réservés pour un compilateur.L'efficacité de la mémoire est excellente.

Quatrième, et très bas sur n'importe quelle liste, se trouve la liste chaînée ou doublement liée, qui, contrairement à un tableau, prend naturellement en charge les insertions et les suppressions d'éléments et, comme cela l'implique, le redimensionnement.C'est la plus lente de toutes les structures de données, car chaque élément ne sait que comment accéder à l'élément suivant, vous devez donc rechercher, en moyenne, des liens (element_knt/2) pour trouver votre donnée.Il est principalement utilisé lorsque les insertions et les suppressions quelque part au milieu de la liste sont courantes, et surtout lorsque la liste est circulaire et alimente un processus coûteux qui rend le temps de lecture des liens relativement réduit.Mon RX général consiste à utiliser un tableau arbitrairement grand au lieu d'une liste chaînée si votre seule exigence est qu'il puisse augmenter en taille.Si vous manquez de taille avec un tableau, vous pouvez réallouer() un tableau plus grand.La STL fait cela pour vous « sous les couvertures » lorsque vous utilisez un vecteur.Brut, mais potentiellement des milliers de fois plus rapide si vous n'avez pas besoin d'insertions, de suppressions ou de recherches par clé.L'efficacité de la mémoire est médiocre, en particulier pour les listes doublement liées.En fait, une liste doublement chaînée, nécessitant deux pointeurs, est exactement aussi inefficace en mémoire qu'un arbre rouge-noir tout en n'ayant AUCUNE de ses caractéristiques attrayantes de récupération rapide et ordonnée.

Cinquième, les arbres prennent en charge de nombreuses opérations supplémentaires sur leurs données triées par rapport à toute autre structure de données.Par exemple, de nombreuses requêtes de base de données exploitent le fait qu'une plage de valeurs de feuille peut être facilement spécifiée en spécifiant leur parent commun, puis en concentrant le traitement ultérieur sur la partie de l'arborescence que le parent « possède ».Le potentiel de multithreading offert par cette approche devrait être évident, car seule une petite région de l'arborescence doit être verrouillée, à savoir uniquement les nœuds que possède le parent et le parent lui-même.

En bref, les arbres sont la Cadillac des structures de données.Vous payez un prix élevé en termes de mémoire utilisée, mais vous obtenez une structure de données entièrement auto-entretenue.C'est pourquoi, comme indiqué dans d'autres réponses ici, les bases de données de transactions utilisent presque exclusivement des arbres.

Si vous souhaitez voir à quoi un arbre Rouge-Noir est censé ressembler graphiquement, j'ai codé une implémentation d'un arbre Rouge-Noir que vous pouvez télécharger ici

IME, presque personne ne comprend l'algorithme de l'arbre RB.Les gens peuvent vous répéter les règles, mais ils ne comprennent pas pourquoi ces règles et d'où elles viennent.Je ne fais pas exception :-)

Pour cette raison, je préfère l'algorithme AVL, car il est facile de comprendre.Une fois que vous l’avez compris, vous pouvez le coder à partir de zéro, car cela a du sens pour vous.

Les arbres peuvent être rapides.Si vous avez un million de nœuds dans un arbre binaire équilibré, il faut en moyenne vingt comparaisons pour trouver un élément.Si vous avez un million de nœuds dans une liste chaînée, il faut en moyenne cinq cent mille comparaisons pour trouver le même élément.

Si l'arbre est déséquilibré, il peut être aussi lent qu'une liste, et prend également plus de mémoire à stocker.Imaginez un arbre dans lequel la plupart des nœuds ont un enfant droit, mais pas d'enfant gauche ;il est une liste, mais vous devez toujours conserver de l'espace mémoire pour insérer le nœud de gauche s'il en existe un.

Quoi qu'il en soit, le Arbre AVL a été le premier algorithme d'arbre binaire équilibré, et l'article de Wikipédia à ce sujet est assez clair.Honnêtement, l'article de Wikipédia sur les arbres rouge-noir est clair comme de la boue.

Au-delà des arbres binaires, les B-Trees sont des arbres où chaque nœud peut avoir plusieurs valeurs.L'arbre B est pas un arbre binaire, c'est justement son nom.Ils sont vraiment utiles pour utiliser efficacement la mémoire ;chaque nœud de l'arborescence peut être dimensionné pour tenir dans un bloc de mémoire, de sorte que vous n'allez pas (lentement) trouver des tonnes de choses différentes en mémoire qui ont été paginées sur le disque.Voici un exemple phénoménal de Arbre B.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top