Arbre PQ
De Wikipedia, l'encyclopédie encyclopedia
En informatique théorique et en bioinformatique, un arbre PQ est une structure de données arborescente qui représente une famille de permutations d'un ensemble fini d'éléments. Cette structure est décrite et appelée ainsi par Kellogg S. Booth et George S. Lueker en 1976[1]. C'est un arbre étiqueté enraciné dans lequel les enfants de chaque nœud sont totalement ordonnés. Chaque élément est représenté par une feuille, et chaque nœud interne est étiqueté par P ou par Q. Un nœud étiqueté P a au moins deux enfants et un nœud Q a au moins trois enfants.