Arbres rouge-noir

Question

J'ai vu les arbres binaires et la recherche binaire mentionnés dans plusieurs livres que j'ai lus récemment, mais comme je n'en suis qu'au début de mes études en informatique, je n'ai pas encore suivi de cours traitant sérieusement des algorithmes et des structures de données.

J'ai consulté les sources habituelles (Wikipedia, Google) et la plupart des descriptions de l'utilité et de la mise en œuvre des arbres rouge-noir (en particulier) sont apparues comme denses et difficiles à comprendre. Je suis sûr que pour quelqu'un qui a le bagage nécessaire, cela a parfaitement du sens, mais pour l'instant, cela se lit presque comme une langue étrangère.

En quoi les arbres binaires sont-ils utiles dans certaines des tâches courantes que vous effectuez en programmant ? Au-delà de cela, quels arbres préférez-vous utiliser (veuillez inclure un exemple d'implémentation) et pourquoi ?

Answer 1

Les arbres rouges noirs permettent de créer des arbres bien équilibrés. Le problème majeur des arbres de recherche binaire est que vous pouvez très facilement les déséquilibrer. Imaginez que votre premier nombre soit un 15. Puis tous les nombres suivants sont de plus en plus petits que 15. Vous obtiendrez un arbre très lourd sur le côté gauche et sans rien sur le côté droit.

Les arbres noirs rouges résolvent ce problème en obligeant votre arbre à être équilibré à chaque fois que vous insérez ou supprimez des éléments. Pour ce faire, ils effectuent 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 vous suggère de vous procurer le manuel CLRS (Cormen, Lieserson, Rivest and Stein), "Introduction to Algorithms" et de lire le livre RB Trees.

L'implémentation n'est pas non plus très courte, il n'est donc pas vraiment préférable de l'inclure ici. Néanmoins, les arbres sont utilisés de manière extensive pour les applications hautes performances qui doivent accéder à de nombreuses données. Ils offrent un moyen très efficace de trouver des nœuds, avec un coût d'insertion/suppression relativement faible. Encore une fois, je vous suggère de consulter le CLRS pour savoir comment ils sont utilisés.

Bien que les BST ne soient pas nécessairement utilisés de manière explicite, un exemple de l'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 manière. Les arbres alimentent Google. Les arbres alimentent pratiquement tous les sites Web sur l'internet.

Answer 2

J'aimerais aborder uniquement la question "Qu'est-ce qui rend les arbres binaires utiles dans certaines des tâches courantes que vous vous trouvez à faire en programmant ?".

Il s'agit d'un sujet important sur lequel de nombreuses personnes ne sont pas d'accord. Certains affirment que les algorithmes enseignés dans le cadre d'un diplôme en informatique, tels que les arbres de recherche binaires et les graphes dirigés, ne sont pas utilisés dans la programmation quotidienne et ne sont donc pas pertinents. D'autres ne sont pas d'accord et affirment que ces algorithmes et structures de données constituent la base de toute notre programmation et qu'il est essentiel de les comprendre, même si vous n'avez jamais à en écrire un vous-même. Cela se traduit par des conversations sur les bonnes pratiques d'entretien et d'embauche. Par exemple, Steve Yegge a un article sur l'entretien chez Google qui aborde cette question. N'oubliez pas ce débat ; les personnes expérimentées ne sont pas d'accord.

Dans le cadre d'une programmation commerciale classique, il se peut que vous n'ayez pas besoin de créer des arbres binaires ou même des arbres très souvent. Cependant, vous utiliserez de nombreuses classes qui fonctionnent en interne à l'aide d'arbres. La plupart des classes d'organisation de base de 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 un peu de la norme de la programmation commerciale, vous trouverez que les arbres sont un ami immédiat. Comme l'a dit un autre poster, les arbres sont des structures de données essentielles 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 de calcul.

J'ai utilisé des arbres binaires sous la forme de Arbres BSP (partitionnement de l'espace binaire) dans les graphiques 3d. Je me penche actuellement à nouveau sur les arbres pour trier de grandes quantités de données géocodées et d'autres données pour la visualisation d'informations dans des applications Flash/Flex. Lorsque vous repoussez les limites du matériel ou que vous souhaitez fonctionner sur des spécifications matérielles inférieures, comprendre et sélectionner le meilleur algorithme peut faire la différence entre l'échec et le succès.

Answer 3

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

Si ce que vous voulez faire est simplement de consulter les valeurs, une table de hachage est beaucoup plus rapide, O(1) insertion et consultation (amorti dans le meilleur des cas).

Une BST sera O(log N) lookup où N est la hauteur de l'arbre, les insertions sont également O(log N).

Les arbres RB et AVL sont importants, comme l'a mentionné une autre réponse, en raison de cette propriété. Si une BST simple est créée avec des valeurs en 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 alors que les arbres RB sont O(1). Un exemple de l'avantage de cette complexité constante est dans le cas où vous gardez une source de données persistante, si vous avez besoin de suivre les changements pour le roll-back, vous devriez suivre O(log N) changements possibles avec un arbre AVL.

Pourquoi seriez-vous prêt à payer pour le coût d'un arbre par rapport à une table de hachage ? L'ORDRE ! Les tables de hachage n'ont pas d'ordre, alors que les BST, en revanche, sont toujours naturellement ordonnées en vertu de leur structure. Donc si vous vous retrouvez à jeter un tas de données dans un tableau ou un autre conteneur et à les trier plus tard, une BST peut être une meilleure solution.

La propriété order de l'arbre vous offre un certain nombre de possibilités d'itération ordonnée : in-order, depth-first, breadth-first, pre-order, post-order. Ces algorithmes d'itération sont utiles dans différentes circonstances si vous souhaitez les consulter.

Les arbres rouges noirs sont utilisés en interne dans presque tous les conteneurs ordonnés des bibliothèques de langage, C++ Set et 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 n'aurez probablement jamais besoin de pour en écrire un vous-même, bien que je le recommande vivement comme un exercice de programmation intéressant.

Answer 4

Les arbres rouges et noirs et les arbres B sont utilisés dans toutes sortes de stockage permanent. Comme 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 base de données modernes utilisent des arbres pour le stockage des données.

Answer 5

Les BST font tourner le monde, comme l'a dit Michael. Si vous cherchez un bon arbre à mettre en œuvre, jetez un coup d'œil à Arbres AVL (Wikipedia). Ils ont une condition d'équilibrage, donc ils sont garantis d'être O(logn). Ce type d'efficacité de recherche fait qu'il est logique de l'intégrer dans tout type de processus d'indexation. La seule chose qui serait plus efficace serait une fonction de hachage, mais ces fonctions deviennent vite désagréables. En outre, vous vous heurtez à la Paradoxe de l'anniversaire (également connu sous le nom de "problème du pigeon").

Quel manuel scolaire utilisez-vous ? Nous avons utilisé Structures de données et analyse en Java par Mark Allen Weiss. Je l'ai ouvert sur mes genoux au moment où j'écris ces lignes. Il contient une excellente section sur les arbres Rouge-Noir, et inclut même le code nécessaire pour mettre en œuvre tous les arbres dont il parle.