Flashcards: Structures hiérarchiques et parcours d'arbres — 22 cards

Arbre — définition ?

Structure hiérarchique non vide avec racine unique.

Racine — rôle ?

Point de départ de l’arbre, sans parent.

Nœud — rôle ?

Élément relié à ses fils, interne ou feuille.

Feuille — caractéristique ?

Nœud sans fils, terminal.

Nœud interne — caractéristique ?

Nœud avec au moins un fils.

Arbre binaire — limite fils ?

Au plus deux fils par nœud.

Profondeur — définition ?

Distance d’un nœud à la racine.

Hauteur — définition ?

Longueur du plus long chemin racine-feuille.

Sous-arbre enraciné — définition ?

Partie de l’arbre à partir d’un nœud.

Inégalités hauteur/nœuds — importance ?

Elles permettent d’évaluer la taille et la profondeur.

Transformation en arbre binaire — but ?

Standardiser la structure pour traitement algorithmique.

Arbres en informatique — usage ?

Représenter données hiérarchiques, structures, expressions.

Parcours en profondeur — principe ?

Explorer le plus profondément avant de revenir en arrière.

Parcours en largeur — principe ?

Explorer niveau par niveau, par file.

Complexité tri par comparaison — limite ?

Θ(n log n) dans le pire cas.

Nœud — différence feuille/interne ?

Feuilles : pas d’enfant, internes : au moins un enfant.

Hauteur — relation avec nœuds ?

Plus de nœuds peut augmenter la hauteur.

Transformation arbre — en quoi consiste ?

Réorganiser fils pour limiter à deux par nœud.

Arbre en informatique — structure clé ?

Racine, nœuds, feuilles, parcours.

Parcours en profondeur — types ?

Préfixe, infixe, postfixe.

Parcours en largeur — méthode ?

Utilise une file, explore niveau par niveau.

Inégalité hauteur/nœuds — formule ?

h+1 ≤ n ≤ (a^{h+1}-1)/(a-1).