Arbre binaire de rechercheEn 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 AVLEn 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 binaireEn 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.
Arbre bicoloreUn arbre bicolore, ou arbre rouge-noir ou arbre rouge et noir est un type particulier d'arbre binaire de recherche équilibré, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui les nomme symmetric binary B-trees (littéralement « arbres B binaires symétriques »). Chaque nœud de l'arbre possède en plus de ses données propres un attribut binaire qui est souvent interprété comme sa « couleur » (rouge ou noir).
Self-balancing binary search treeIn computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. These operations when designed for a self-balancing binary search tree, contain precautionary measures against boundlessly increasing tree height, so that these abstract data structures receive the attribute "self-balancing".
Arbre BEn informatique, un arbre B (appelé aussi B-arbre par analogie au terme anglais « B-tree ») est une structure de données en arbre équilibré. Les arbres B sont principalement mis en œuvre dans les mécanismes de gestion de bases de données et de systèmes de fichiers. Ils stockent les données sous une forme triée et permettent une exécution des opérations d'insertion et de suppression en temps toujours logarithmique. Le principe est de permettre aux nœuds parents de posséder plus de deux nœuds enfants : c'est une généralisation de l’arbre binaire de recherche.
T-treeIn computer science a T-tree is a type of binary tree data structure that is used by main-memory databases, such as Datablitz, eXtremeDB, MySQL Cluster, Oracle TimesTen and MobileLite. A T-tree is a balanced index tree data structure optimized for cases where both the index and the actual data are fully kept in memory, just as a B-tree is an index structure optimized for storage on block oriented secondary storage devices like hard disks.
TreapEn informatique, les notions de treap ou arbretas et d'arbres binaires de recherche randomisés sont deux formes très proche d'arbre binaire de recherche, des structures de données qui maintiennent un ensemble dynamique de clés ordonnées et permettent d'effectuer une recherche binaire parmi ces clés.
Rotation d'un arbre binaire de rechercheEn 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 splayUn arbre splay (ou arbre évasé) est un arbre binaire de recherche auto-équilibré possédant en outre la propriété que les éléments auxquels on a récemment accédé (pour les ajouter, les regarder ou les supprimer) sont rapidement accessibles. Ils disposent ainsi d'une complexité amortie en O(log n) pour les opérations courantes comme insertion, recherche ou suppression. Ainsi dans le cas où les opérations possèdent une certaine structure, ces arbres constituent des bases de données ayant de bonnes performances, et ceci reste vrai même si cette structure est a priori inconnue.
Algorithme de RémyL'algorithme de Rémy est un générateur d'arbres binaires, dont la principale application est un algorithme efficace de génération aléatoire d'arbres binaires. L'algorithme doit son nom à son inventeur Jean-Luc Rémy. L'algorithme de Rémy est dû à Jean-Luc Rémy, chercheur au Centre de recherche en informatique de Nancy. Il a été créé en 1978 sans être publié immédiatement et a fait partie du folklore de l'algorithmique et de la combinatoire énumérative jusqu'à sa parution dans une revue francophone en 1985.
Arborescencethumb|Exemple de représentation arborescente En mathématiques, plus précisément dans la théorie des graphes : une arborescence est un arbre comportant un sommet particulier , nommé racine de l'arborescence, à partir duquel il existe un chemin unique vers tous les autres sommets. En informatique, cette notion désigne souvent celle d'arbre de la théorie des graphes. Une arborescence désigne alors généralement une organisation des données en mémoire, de manière logique et hiérarchisée, utilisant une structure algorithmique d'arbre.
Recherche dichotomiqueLa recherche dichotomique, ou recherche par dichotomie (), est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié. Le principe est le suivant : comparer l'élément avec la valeur de la case au milieu du tableau ; si les valeurs sont égales, la tâche est accomplie, sinon on recommence dans la moitié du tableau pertinente. Le nombre d'itérations de la procédure, c'est-à-dire le nombre de comparaisons, est logarithmique en la taille du tableau.
Join-based tree algorithmsIn computer science, join-based tree algorithms are a class of algorithms for self-balancing binary search trees. This framework aims at designing highly-parallelized algorithms for various balanced binary search trees. The algorithmic framework is based on a single operation join. Under this framework, the join operation captures all balancing criteria of different balancing schemes, and all other functions join have generic implementation across different balancing schemes.
Imprimeriethumb|Johannes Gutenberg, inventeur de la presse mécanique à caractère alphabétique mobile métallique à partir de 1450. L'imprimerie est un ensemble de techniques permettant la reproduction en grande quantité, sur support matériel, d'écrits et d'illustrations, cela afin d'en permettre une distribution de masse. Généralement, on utilise des supports plans et la matière la plus utilisée est le papier ou le textile. Ces techniques forment ce que l'on appelle communément la chaîne graphique.
Arbre kdvignette|Partition d'un espace à trois dimensions pour la construction d'un arbre 3-d. En informatique, un arbre k-d (ou k-d tree, pour k-dimensional tree) est une structure de données de partition de l'espace permettant de stocker des points, et de faire des recherches (recherche par plage, plus proche voisin, etc.) plus rapidement qu'en parcourant linéairement le tableau de points. Les arbres k-d sont des cas particuliers d'arbres BSP (binary space partition trees).
Presse typographiquevignette|L'atelier de Joost Amman en 1568. La presse typographique est un dispositif destiné à imprimer des textes et des illustrations sur du papier, en exerçant une forte pression sur la feuille de papier placée sur une forme imprimante, ensemble de caractères en relief ou gravure sur bois, préalablement encrés, de manière que l'encre se dépose sur le papier. L'opération répétée permet d'obtenir un grand nombre d'exemplaires identiques.
Impression au bloc de boisL’impression au bloc de bois est une technique d'impression de motifs, d'images et de textes largement exploitée dans l'Asie de l'Est et ayant pour origine la Chine, où elle a été utilisée dès l'antiquité comme méthode d'impression textile puis sur papier. Des exemples de production d'étoffes chinoises ont été conservés jusqu'à nous, remontant au moins au troisième siècle avant notre ère. L'impression au bloc de bois est très répandue pendant la dynastie Tang () et demeure la méthode d'impression de livres, de textes et d'images la plus utilisée dans l'Asie de l'Est jusqu'au .
Histoire de l'imprimerieL'histoire de l'imprimerie s'échelonne sur des milliers d'années, depuis les premières formes d'impression jusqu'à nos jours. Cette histoire comprend les points marquants de l'évolution des formes d'impression, des coûts qui y sont reliés et de l'étendue de la diffusion des œuvres imprimées. L'histoire de l'imprimerie est marquée par l'évolution de l'écriture ainsi que de son support matériel. Les premières formes de copies de documents sont produites par les moines copistes, qui reproduisent méthodiquement à la main les ouvrages.
Extrême gaucheLe terme extrême gauche est employé depuis 1920 pour désigner une partie des groupes, mouvements, organisations et partis politiques, , dont les principaux furent d'obédience maoïste et trotskiste, qui souhaitent le renversement du capitalisme en faveur d'une société sans classes sociales, mais n'ont pas de représentation dans les assemblées parlementaires, car ils restent à l'écart des accords de désistement électoral et de gouvernement.
