Séance de cours

Arbres binaires et nombres catalans

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Description

Cette séance de cours couvre la définition des arbres binaires comme une structure inductive, la formule récursive pour le nombre d'arbres binaires avec n vertices, la fonction génératrice pour les nombres catalans, et la dérivation de la formule récursive pour les arbres binaires en utilisant des fonctions génératrices.

Source officielle

Concepts associés (15)

Arbre binaire de recherche

En informatique, un arbre binaire de recherche ou ABR (en anglais, binary search tree ou BST) est une structure de données représentant un ensemble ou un tableau associatif dont les clés appartiennent à un ensemble totalement ordonné. Un arbre binaire de recherche permet des opérations rapides pour rechercher une clé, insérer ou supprimer une clé.

Arbre AVL

En informatique théorique, les arbres AVL ont été historiquement les premiers arbres binaires de recherche automatiquement équilibrés. Dans un arbre AVL, les hauteurs des deux sous-arbres d'un même nœud diffèrent au plus de un. La recherche, l'insertion et la suppression sont toutes en dans le pire des cas. L'insertion et la suppression nécessitent d'effectuer des rotations. La dénomination « arbre AVL » provient des noms respectifs de ses deux inventeurs, respectivement et , qui l'ont publié en 1962 sous le titre An Algorithm for the Organization of Information.

Arbre enraciné

En théorie des graphes, un arbre enraciné ou une arborescence est un graphe acyclique orienté possédant une unique racine, et tel que tous les nœuds sauf la racine ont un unique parent. En informatique, c'est également une structure de données récursive utilisée pour représenter ce type de graphes. Dans un arbre, on distingue deux catégories d'éléments : les feuilles (ou nœuds externes), éléments ne possédant pas de fils dans l'arbre ; les nœuds internes, éléments possédant des fils (sous-branches).

Rotation d'un arbre binaire de recherche

En algorithmique, la rotation d'un arbre binaire de recherche permet de changer la structure d'un arbre binaire de recherche ou ABR sans invalider l'ordre des éléments. Une telle rotation consiste en fait à faire remonter un nœud dans l'arbre et à en faire redescendre un autre. Cette opération est très utilisée dans les arbres équilibrés en général car elle permet de réduire la hauteur d'un arbre en faisant descendre les petits sous-arbres et remonter les grands, ce qui permet de « rééquilibrer » les arbres et d'accélérer de nombreuses opérations sur ces arbres.

Arbre binaire

En informatique, un arbre binaire est une structure de données qui peut se représenter sous la forme d'une hiérarchie dont chaque élément est appelé nœud, le nœud initial étant appelé racine. Dans un arbre binaire, chaque élément possède au plus deux éléments fils au niveau inférieur, habituellement appelés gauche et droit. Du point de vue de ces éléments fils, l'élément dont ils sont issus au niveau supérieur est appelé père. Au niveau le plus élevé, niveau 0, il y a un nœud racine.

Afficher plus

Séances de cours associées (58)

L'algorithme de Huffman : mécaniser la preuve

Explore la mécanisation de l'algorithme de Huffman et sa mise en œuvre fonctionnelle.

Indexation structurée en arbres : les arbres B+ expliqués

Couvre les arbres B+, une structure de données clé pour une indexation efficace dans les bases de données.

Structures de données : piles, files d'attente, listes liées

Couvre les piles, les files d'attente, les listes liées et les arbres de recherche binaires dans les structures de données.

Arbre de recherche binaire optimal

Explore les arbres de recherche binaires optimaux pour minimiser efficacement les coûts de recherche attendus.

Opérations sur les arbres de recherche binaires

Explique les opérations d'arbre de recherche binaire, en se concentrant sur l'insertion, la recherche et la conversion de liste, en mettant l'accent sur la vérification formelle et le débogage.

Afficher plus

Concepts associés (15)

Arbre binaire de recherche

Arbre AVL

Arbre enraciné

Rotation d'un arbre binaire de recherche

Arbre binaire

Afficher plus