Galerie de cartes mentales [Notes d'étude] Structure-Arbre de données
Certaines connaissances sur les arbres dans les structures de données, y compris les arbres de Huffman, la recherche de tables arborescentes, les arbres binaires d'indices, les méthodes de traversée d'arbres binaires et les arbres couvrants minimaux. Tout le monde est invité à apprendre.
Modifié à 2023-07-05 11:27:01Cent ans de solitude est le chef-d'œuvre de Gabriel Garcia Marquez. La lecture de ce livre commence par l'analyse des relations entre les personnages, qui se concentre sur la famille Buendía et raconte l'histoire de la prospérité et du déclin de la famille, de ses relations internes et de ses luttes politiques, de son métissage et de sa renaissance au cours d'une centaine d'années.
Cent ans de solitude est le chef-d'œuvre de Gabriel Garcia Marquez. La lecture de ce livre commence par l'analyse des relations entre les personnages, qui se concentre sur la famille Buendía et raconte l'histoire de la prospérité et du déclin de la famille, de ses relations internes et de ses luttes politiques, de son métissage et de sa renaissance au cours d'une centaine d'années.
La gestion de projet est le processus qui consiste à appliquer des connaissances, des compétences, des outils et des méthodologies spécialisés aux activités du projet afin que celui-ci puisse atteindre ou dépasser les exigences et les attentes fixées dans le cadre de ressources limitées. Ce diagramme fournit une vue d'ensemble des 8 composantes du processus de gestion de projet et peut être utilisé comme modèle générique.
Cent ans de solitude est le chef-d'œuvre de Gabriel Garcia Marquez. La lecture de ce livre commence par l'analyse des relations entre les personnages, qui se concentre sur la famille Buendía et raconte l'histoire de la prospérité et du déclin de la famille, de ses relations internes et de ses luttes politiques, de son métissage et de sa renaissance au cours d'une centaine d'années.
Cent ans de solitude est le chef-d'œuvre de Gabriel Garcia Marquez. La lecture de ce livre commence par l'analyse des relations entre les personnages, qui se concentre sur la famille Buendía et raconte l'histoire de la prospérité et du déclin de la famille, de ses relations internes et de ses luttes politiques, de son métissage et de sa renaissance au cours d'une centaine d'années.
La gestion de projet est le processus qui consiste à appliquer des connaissances, des compétences, des outils et des méthodologies spécialisés aux activités du projet afin que celui-ci puisse atteindre ou dépasser les exigences et les attentes fixées dans le cadre de ressources limitées. Ce diagramme fournit une vue d'ensemble des 8 composantes du processus de gestion de projet et peut être utilisé comme modèle générique.
Arbre
Arbre de Huffman
Longueur de trajet pondérée WPL
Supposons qu'un arbre binaire ait n nœuds feuilles pondérés, alors la somme de la longueur du chemin depuis le nœud racine jusqu'à chaque nœud feuille et le produit du poids du nœud correspondant est appelée la longueur de chemin pondérée WPL (longueur de chemin pondérée) de l'arbre binaire. .
Les mêmes nœuds feuilles construisent des arbres binaires différents
Les nœuds feuilles avec des poids plus élevés sont plus proches de la racine et plus la valeur de wpl est petite.
définition
L'arbre binaire avec la longueur de chemin pondérée minimale est appelé arbre de Huffman (également appelé arbre optimal).
Comment construire ?
en principe
Les nœuds feuilles avec des poids plus élevés sont plus proches du nœud racine.
Plus le poids est petit, plus le nœud feuille est éloigné du nœud racine.
Trouver la petite valeur (les nœuds synthétisés doivent également être comparés entre eux)
processus
Il n'y a pas de nœuds feuilles avec des poids
application
Codage de Huffman (codage de préfixe)
Caractéristiques du codage de Huffman : Plus le poids est élevé, plus le code de caractère est court, et vice versa.
Dans le codage Huffman d'un ensemble de caractères, il est impossible que le codage Huffman d'un caractère soit le préfixe du codage Huffman d'un autre caractère.
application
Encodage de caractère
mode d'emploi de la machine
Recherche de table arborescente
Arbre de tri binaire
gauche<racine<droite
Arbre binaire équilibré AVL
Une version améliorée de l'arbre de tri binaire (un arbre de tri binaire spécial), essayez de garder l'arbre aussi court que possible !
Comment savoir si un arbre pousse normalement ?
Facteur d'équilibre = hauteur du sous-arbre gauche - hauteur du sous-arbre droit
Arbre de tri binaire avec facteur d'équilibre <= 1
Équilibrer la profondeur maximale et le nombre minimum de nœuds d'un arbre binaire
B-tree (une extension de l'arbre binaire équilibré)
insérer
La création d'un B-tree est un processus d'opérations d'insertion continues
indice arbre binaire
Les conditions pour le champ de chaîne vide à gauche : il se trouve à l'extrémité la plus à gauche de la séquence et le pointeur gauche d'origine est vide.
Les conditions pour le domaine de chaîne vide droit : il se trouve à l'extrémité droite de la séquence et le pointeur droit d'origine est vide.
Méthode de parcours d'arbre binaire
pour le nœud racine
prologue
racine-gauche-droite
mi-commande
racine gauche-droite
Épilogue
racine gauche-droite
niveau
Parcourir ligne par ligne
arbre couvrant minimum
L'algorithme de Prim
Exiger
Le poids est le plus petit et ne peut pas former de cycle.
Pour les questions avec peu de nœuds
Les étapes principales de l'algorithme Prime sont les suivantes : dans un graphe connecté pondéré, V est un ensemble contenant tous les sommets U est déjà un nœud dans l'arbre couvrant minimum, à partir de n'importe quel sommet v du graphe. ={v}, répétez les opérations suivantes : trouvez une arête avec le plus petit poids parmi toutes les arêtes (u,w)∈E de tous u∈U,w∈V-U, et ajoutez l'arête (u,w) à l'ensemble de arêtes trouvées. Et ajoutez le point w à l’ensemble U. Lorsque U = V, l’arbre couvrant minimum est trouvé.
Algorithme de Kruskal
Déterminez d’abord les nœuds et sélectionnez ceux avec les chemins les plus courts dans l’ordre.
Impossible de former un anneau
Pour les questions avec un petit nombre de côtés
Idée de base : dirigée par les bords. Dans un graphe connecté pondéré, U est l'ensemble de toutes les arêtes, N est le nombre de sommets et soit SU l'ensemble des arêtes qui se trouvent déjà sur l'arbre couvrant minimum. Répétez les opérations suivantes : sélectionnez à chaque fois une arête e∈U-SU de plus petit poids et une arête qui ne forme pas de cycle avec les arêtes de SU, et ajoutez-la à SU. Lorsque le nombre d’arêtes dans SU est égal à N-1, l’arbre couvrant minimum est trouvé.
question
Si un nœud n’est pas un nœud feuille, alors il aura des enfants, et ces enfants constituent un groupe de frères.
Le nombre de nœuds sans pointeur droit est : nombre de nœuds racine de nœuds non feuilles
Excluez les symétriques, comptez le nombre et assurez-vous qu'il est toujours moins à gauche et plus à droite ou plus à gauche et moins à droite.
Arbre
Longueur de recherche moyenne ASL
lié à la hauteur de l'arbre
Chapitre 5 Arbres et arbres binaires
Parcours d'arbre binaire et arbre de Huffman
Difficulté : Conversion entre arbres binaires et arbres et forêts
La plupart des tests se présentent sous la forme de questions à choix multiples, qui impliquent également des algorithmes de traversée d'arbre et d'arbre de Huffman.
Arbre
ensemble fini de n nœuds
Le nœud racine est unique
Il n’y a pas de limite au nombre de sous-arbres, mais ils ne se croisent pas.
Degré : le nombre de sous-arbres appartenant au nœud
Arbre binaire : degré <=2
nature
Il y a au plus 2^i-1 nœuds au i-ème niveau de l'arbre binaire.
Si la profondeur dans l'arbre binaire est k, alors il y a au plus 2^k-1 nœuds. (k>=1)
n0=n2 1, n0 représente le nombre de nœuds de degré 0 et n2 représente le nombre de nœuds de degré 2.
Dans un arbre binaire complet, la profondeur d'un arbre binaire complet avec n nœuds est [log2n] 1, où [log2n] est arrondi à l'inférieur.
[Arbre binaire] Formule de calcul de nœud N = n0 n1 n2
Nombre total de nœuds = degré total 1=Oxn0 1xn1 2xn2 ..
arbre binaire complet
Tous les nœuds ont des sous-arbres gauche et droit, et tous les nœuds feuilles sont au même niveau.
arbre binaire complet
Les nœuds feuilles ne peuvent apparaître qu’au niveau le plus bas et au niveau inférieur suivant.
Et les nœuds de la couche inférieure sont concentrés dans l’arbre binaire aux positions les plus à gauche de la couche.
La correspondance de traversée entre les arbres, les forêts et les arbres binaires
tas
définition
Doit être un arbre binaire complet
Un arbre binaire complet permet uniquement que la dernière ligne soit moins que pleine. Et la dernière ligne doit être triée de gauche à droite. Il ne doit y avoir aucun espace entre les éléments de la dernière ligne
Ordre du tas
jour
petit tas de racines
Opérations de base
Stockage en tas
1. Parcourez le nombre en fonction de la séquence de couches, représentée par un tableau unidimensionnel
Le nœud parent est i, l'indice du nœud enfant gauche est 2i 1 et le nœud enfant droit est 2i 2 (cette règle est souvent utilisée dans les algorithmes)
Filtre supérieur
Seul le dernier élément de l'arborescence viole l'ordre des tas
Principalement utilisé pour insérer de nouveaux éléments dans le tas
Complexité : O(logN)
Filtrer vers le bas
Seul le nœud racine viole l'ordre des tas
Ajustez le nœud racine vers le bas
Complexité : O(logN)
Construire une pile
Comment convertir un tableau non ordonné en tas ?
de haut en bas
Insérer dans le tas, filtrer
Complexité : O(NlogN)
de bas en haut
Ajustez d'abord les éléments dans un tas et filtrez vers le bas. En partant de l'avant-dernière ligne, effectuez l'opération de filtrage vers le bas sur le nœud parent.
Complexité : O(N)
Application : file d'attente prioritaire
deux opérations
insérer une file d'attente
pop up élément minimal
Peut être implémenté à l'aide d'un petit tas racine
Étant donné que le nœud racine du petit tas racine est min, après l'apparition, les éléments restants sont ajustés dans un tas (placez le dernier élément au nœud racine et filtrez vers le bas)
Complexité : O(logN)
Tri par tas : extraire les éléments de la file d'attente prioritaire en séquence
Complexité : O(NlogN)