« Salut Amigo ! »
« Bonjour, Rishi ! »
"J'ai trouvé mes vieilles notes là-bas et j'ai préparé du matériel intéressant pour vous. Je pense que vous serez intéressé à l'entendre."
"Ecoutons-le. Tu trouves toujours quelque chose d'intéressant qui s'avère plus tard très utile."
"OK. Aujourd'hui, je veux vous parler des arbres , je vais donc commencer par les graphiques ."
" Un graphe est un système de points et de droites qui les relient. Les points sont appelés les sommets du graphe, et les droites sont appelées les arêtes du graphe. Par exemple :"
"Un graphique est très pratique à utiliser comme modèle mathématique pour divers processus et tâches du monde réel. De nombreuses tâches et algorithmes différents ont été inventés pour les graphiques, ils sont donc utilisés assez souvent."
"Par exemple, supposons que les sommets sont des villes et que les arêtes sont des routes. La recherche de la route la plus courte entre les villes devient alors : « étant donné un graphe, trouver le chemin le plus court entre deux sommets ». "
"Mais le chemin de A à B n'est pas toujours le même que le chemin de B à A. Ainsi, il est parfois préférable d'avoir deux lignes différentes. Pour ce faire, les lignes (bords du graphique) sont remplacées par des flèches. Dans En d'autres termes, le graphique peut avoir deux flèches : une de A à B et une autre de B à A."
"Si le graphe utilise des flèches, alors on l'appelle un graphe orienté ; s'il n'a que des lignes, alors on l'appelle un graphe non orienté ."
"Chaque sommet peut avoir son propre nombre d'arêtes. Un sommet peut aussi n'avoir aucune arête. Inversement, un sommet peut être relié par des arêtes à tous les autres sommets. Si chaque paire de sommets dans un graphe est reliée par une arête, alors c'est ce qu'on appelle un graphe complet. "
"Si vous pouvez utiliser des arêtes pour atteindre chaque sommet d'un graphe, alors on l'appelle un graphe connexe . Un graphe qui a trois sommets distincts et pas d'arêtes est toujours un graphe, mais nous l'appelons un graphe déconnecté ."
"Pour former un graphe connexe à partir de N sommets, vous avez besoin d'au moins N-1 arêtes. Ce type de graphe s'appelle un arbre."
"De plus, généralement, un sommet est choisi comme racine de l'arbre et les autres sont déclarés comme étant des branches. Les branches d'arbre qui n'ont pas leurs propres branches sont appelées feuilles . Par exemple :"
"Si chaque élément de l'arbre a deux enfants, alors on l' appelle un arbre binaire . En d'autres termes, il peut y avoir 0 ou 2 branches. Vous pouvez voir un arbre binaire en haut à droite."
" Un arbre est appelé un arbre binaire complet lorsque chaque branche a 2 enfants et que toutes les feuilles (sommets sans enfants) sont sur la même ligne."
"Par exemple:"
« Pourquoi ces arbres sont-ils nécessaires ? »
"Oh, les arbres sont utilisés dans de nombreux endroits. En général, les arbres binaires sont des données structurées triées."
"Qu'est ce que c'est?"
"Oui, c'est très simple. On stocke une certaine valeur dans chaque sommet. Et chaque élément suit une règle : la valeur stockée dans l'enfant de droite doit être supérieure à la valeur stockée dans le sommet, et la valeur stockée dans l'enfant de gauche doit être inférieur à la valeur stockée dans le sommet. Cet ordre permet de trouver rapidement les éléments de l'arbre dont on a besoin."
« Pouvez-vous préciser ce que cela signifie ? »
"Les éléments de l'arborescence sont généralement triés par addition. Supposons que nous ayons 7 éléments : 13, 5, 4, 16, 8, 11, 10"
"Voici comment les éléments sont ajoutés à l'arbre."
"Si nous recherchons le numéro 7 dans cet arbre, alors voici comment se déroulera la recherche"
"0) Commencer à la racine."
"1a) Est-ce que 7 est égal à 13 ? Non"
« 1b) Est-ce que 7 est supérieur à 13 ? Non, nous passons donc au sous-arbre de gauche. »
"2a) Est-ce que 7 est égal à 5 ? Non."
« 2b) Est-ce que 7 est supérieur à 5 ? Oui, nous passons donc au sous-arbre de droite. »
"3a) Est-ce que 7 est égal à 8 ? Non"
"3b) Est-ce que 7 est supérieur à 8 ? Non, nous passons donc au sous-arbre de gauche."
"4a) Il n'y a pas de sous-arbre à gauche, ce qui signifie que le nombre 7 n'est pas dans l'arbre."
"Ah. En d'autres termes, nous n'avons qu'à vérifier les sommets sur le chemin de la racine à l'emplacement potentiel du nombre souhaité. Ouais, c'est vraiment rapide."
"De plus, si l'arbre est équilibré, vous n'aurez qu'à traverser environ 20 sommets pour rechercher un million d'éléments."
"Je suis d'accord - ce n'est pas beaucoup."
« Que veux-tu dire par arbre équilibré ?
« Un arbre qui n'est pas déformé, c'est-à-dire qui n'a pas de longues branches. Par exemple, si les éléments étaient déjà triés quand on a construit l'arbre, alors on aurait fait un très long arbre composé d'une seule branche .
« Hmm. Tu as raison. Alors qu'est-ce qu'on fait ?
"Comme vous l'avez probablement déjà deviné, l'arbre le plus efficace a des branches qui ont approximativement la même longueur. Ensuite, chaque comparaison supprime la plus grande partie du sous-arbre restant."
« Alors, nous devons reconstruire l'arbre ? »
« Oui. Il doit être « équilibré » - pour être aussi proche que possible d'un arbre binaire complet. »
"Pour résoudre ce problème, des arbres auto-équilibrés ont été inventés. Si l'arbre se déforme après l'ajout d'un élément, il réorganise légèrement les éléments pour que tout se passe bien. Voici un exemple d'équilibrage :"
"Certains de ces arbres sont connus sous le nom d'arbres rouges -noirs ."
« Pourquoi les appelle-t-on rouge-noir ? »
"Leur inventeur a dessiné tous les sommets en utilisant deux couleurs. Une couleur était le rouge et l'autre était le noir. Les différents sommets obéissent à des règles différentes. Cela constitue la base entière de la procédure d'équilibrage."
"Par exemple:"
« Alors, quelles sont ces règles ?
"1) Un sommet rouge ne peut pas être l'enfant d'un sommet rouge."
"2) La profondeur noire de chaque feuille est la même (la profondeur noire fait référence au nombre de sommets noirs sur le chemin depuis la racine)."
"3) La racine de l'arbre est noire."
"Je n'expliquerai pas comment cela fonctionne - ta tête est probablement déjà en train d'exploser."
"Oui. Mon processeur dégage un peu de fumée."
"Voici un lien pour vous. Si vous le souhaitez, vous pouvez en savoir plus ici."
Lien vers du matériel supplémentaire
"Et maintenant, va faire une pause."
GO TO FULL VERSION