Alors je viens d'apprendre les arbres rouges noirs à Cormen et wow! En règle générale, j'aime comprendre tous les algorithmes et structures de données au point que je peux les reconstruire à partir de zéro sans avoir à tricher en regardant le pseudo-code. J'aime vraiment les algorithmes, donc j'aime apprendre comment ils fonctionnent et je vais généralement ligne par ligne et j'essaie certains cas en regardant le code et en vérifiant si ce qui se passe est ce que j'ai compris que cela devrait se produire.
Le simple fait de comprendre ce qui se passait m'a pris BEAUCOUP de temps pour les arbres RB. Même avec les explications du livre, j'ai toujours eu du mal à saisir le code. Sans oublier que je ne comprenais pas comment / pourquoi les rotations fonctionnent. Je ne le trouve pas du tout intuitif. Je veux dire, les trois (six en fait) cas différents pour l'insertion puis les 4 cas pour la suppression? Est-il possible de comprendre cette chose? Il m'est impossible de reconstruire ce code sans tricher. Jusqu'à l'arbre binaire, je pouvais implémenter les choses de ma tête, avec quelques ajustements, cela fonctionnerait toujours, mais les arbres RB, je ne vais même pas essayer. Je veux dire, même le professeur est parfois confus, donc je suppose que ce n'est vraiment pas si facile, mais en même temps, ne devrions-nous pas avoir à comprendre tout ce qui se passe ou du moins pourquoi? Le livre n'a pas t vraiment expliquer comment quelqu'un a eu l'idée des rotations. Comment quelqu'un a-t-il remarqué qu'avec 2 rotations, vous pouviez résoudre n'importe quel problème d'insertion? C'est incroyable!
Ma question est, dois-je vraiment comprendre à 100% les arbres RB? Je me sens un peu mal de sauter des trucs sans bien le comprendre. Merci d'avance les gars! (PS: il n'y a pas de balise pour RB-tree, en fait même pas pour tree, juste binary-tree, donc je ne mets que des algorithmes)
la source
Réponses:
Vous semblez assimiler l'idée de «comprendre» à «être capable d'écrire le code sans regarder le livre». Ce sont deux choses différentes. Si vous pouvez voir comment la rotation des nœuds d'arbre réorganise l'arbre afin de maintenir l'équilibre, alors vous le comprenez. Être capable de rappeler immédiatement tous les cas pour lesquels des rotations s'appliquent n'est pas la question.
Moi-même, je pourrais probablement comprendre les rotations si j'avais un stylo / papier / plusieurs heures pour jouer avec. Mais je ne pourrais certainement pas l'écrire sans une pensée. Si je devais réellement écrire un tel algorithme, je le vérifierais pour m'assurer que j'obtenais tous les détails correctement. Bien sûr, dans presque toutes les situations, j'utiliserais du code déjà écrit.
Lorsque tout cela est utilisé, c'est lorsque vous rencontrez une situation qui ne correspond pas tout à fait aux algorithmes. Vous n'aurez jamais besoin d'écrire votre propre implémentation d'arborescence. Mais vous pourriez vous retrouver, disons, devant aplanir une héritière de listes doublement liées. Dans ce cas, avoir compris l'idée de base de la rotation peut être très utile.
la source
Si vous êtes un peu familier avec la programmation fonctionnelle, vous pourriez trouver cette approche meilleure (Okasaki 1999):
http://www.eecs.usma.edu/webs/people/okasaki/jfp99redblack.pdf
Sinon, prenez au moins le cœur de la phrase d'ouverture:
la source
Vous n'avez pas besoin de comprendre les rotations en détail. Vous devez comprendre la relation entre les arbres et les RB 2-3-4 arbres (voir Sedgewick). Toutes ces rotations folles ont beaucoup plus de sens quand on les considère comme des arbres 2-3-4. Si votre professeur n'a pas enseigné les arbres RB comme détail d'implémentation pour les arbres 2-3-4, vous devriez probablement lire quelque chose sur les arbres 2-3-4. (Le traitement de Sedgewick est assez bon; Wikipedia ne l'a pas.)
Plus généralement, comprendre les détails d'implémentation de la raison pour laquelle un algorithme fonctionne n'est que parfois utile. Comprendre la logique du fonctionnement de l'algorithme est presque toujours utile. Être capable de créer l'algorithme vous-même n'est généralement pas nécessaire, bien que plus vous comprenez d'algorithmes, meilleures sont vos chances.
la source
Si vous avez besoin de "RB Trees By Heart" pour votre examen la semaine prochaine, vous devrez mordre la balle et les apprendre. Dans ce cas, vous devez reconsidérer vos méthodes d'apprentissage. Peut-être qu'essayer d'expliquer RB Trees à un camarade de classe vous aidera plus qu'une autre nuit d'écriture de code solitaire.
Si RB Trees est une base pour votre prochain cours après les vacances, sautez-les maintenant (sans rancune) et concentrez-vous sur le cours de ce semestre. Mais gardez les yeux ouverts pour les sujets qui pourraient vous préparer à une deuxième tentative de RB Trees.
Si vous sentez honnêtement que vous n'en aurez jamais vraiment besoin (cf. commentaire d'Anna Lear), dites-leur au revoir sans regret - personne ne sait plus qu'une goutte dans la mer de la connaissance (c'est dommage que les enseignants pensent souvent que leur goutte est la plus importante) important).
la source
La clé du succès de la programmation est de ne jamais abandonner :
Aujourd'hui ses arbres RB demain ce sera autre chose. La plus grande leçon n'est pas d'abandonner .
Pour moi, c'est l'un des éléments essentiels de la programmation, ne pas abandonner ...
Je suggérerais que vous continuiez d'essayer , et quand vous échouez, recommencez .
Parce qu'une fois que vous avez surmonté les montagnes, le ciel devient clair. Votre esprit change de compréhension, vous êtes temporairement élevé (jusqu'à la prochaine montagne) . Cette élévation temporelle vaut plus que tout l'argent du monde.
la source
La meilleure façon de le comprendre est de l' essayer :
C'est comme ça qu'on a fait au collège. Et pour l'examen, nous avons pu expliquer comment une partie de celui-ci fonctionnait.
la source