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 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.
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 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.
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.
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).
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.
M-ary treeIn graph theory, an m-ary tree (for nonnegative integers m) (also known as n-ary, k-ary or k-way tree) is an arborescence (or, for some authors, an ordered tree) in which each node has no more than m children. A binary tree is the special case where m = 2, and a ternary tree is another case with m = 3 that limits its children to three. A full m-ary tree is an m-ary tree where within each level every node has 0 or m children. A complete m-ary tree (or, less commonly, a perfect m-ary tree) is a full m-ary tree in which all leaf nodes are at the same depth.
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.
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 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).
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.
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.
Tri par insertionEn informatique, le tri par insertion est un algorithme de tri classique. La plupart des personnes l'utilisent naturellement pour trier des cartes à jouer. En général, le tri par insertion est beaucoup plus lent que d'autres algorithmes comme le tri rapide (ou quicksort) et le tri fusion pour traiter de grandes séquences, car sa complexité asymptotique est quadratique. Le tri par insertion est cependant considéré comme l'algorithme le plus efficace sur des entrées de petite taille.
Key managementKey management refers to management of cryptographic keys in a cryptosystem. This includes dealing with the generation, exchange, storage, use, crypto-shredding (destruction) and replacement of keys. It includes cryptographic protocol design, key servers, user procedures, and other relevant protocols. Key management concerns keys at the user level, either between users or systems. This is in contrast to key scheduling, which typically refers to the internal handling of keys within the operation of a cipher.
Cryptographie asymétriquevignette|320x320px|Schéma du chiffrement asymétrique: une clé sert à chiffrer et une seconde à déchiffrer La cryptographie asymétrique, ou cryptographie à clé publique est un domaine relativement récent de la cryptographie. Elle permet d'assurer la confidentialité d'une communication, ou d'authentifier les participants, sans que cela repose sur une donnée secrète partagée entre ceux-ci, contrairement à la cryptographie symétrique qui nécessite ce secret partagé préalable.
Échange de clévignette|Paramètres de configuration pour la machine de cryptographie Enigma, en fonction du jour, du mois, etc. On peut lire sur ce document plusieurs mises en garde concernant son caractère secret. Avant l'avènement de la cryptographie moderne, la nécessité de tels mécanismes d'échange de clé constituaient une vulnérabilité majeure. En informatique, et plus particulièrement en cryptologie, un protocole déchange de clé (ou de négociation de clé, ou d'établissement de clé, ou de distribution de clé) est un mécanisme par lequel plusieurs participants se mettent d'accord sur une clé cryptographique.
Empreinte de clé publiqueEn cryptographie, une empreinte de clé publique (ou empreinte cryptographique de clé publique ; en anglais, public key fingerprint) est une courte séquence d'octets utilisée pour identifier une clé publique plus longue. Les empreintes de clé publique sont créées en appliquant une fonction de hachage cryptographique à une clé publique. Comme les empreintes de clé publique sont plus courtes que les clés auxquelles elles se rapportent, elles peuvent être utilisées pour simplifier certaines tâches de gestion des clés.
B+ treeA B+ tree is an m-ary tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves. The root may be either a leaf or a node with two or more children. A B+ tree can be viewed as a B-tree in which each node contains only keys (not key–value pairs), and to which an additional level is added at the bottom with linked leaves. The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context — in particular, .
Longueur de cléEn cryptologie, la longueur de clé ( ou key length) est la taille mesurée en bits de la clé de chiffrement (ou de signature) utilisée par un algorithme de chiffrement. La longueur de la clé est différente de la sécurité cryptographique, qui est la mesure de l'attaque la plus rapide contre un algorithme, aussi mesurée en bits. La sécurité évaluée d'un cryptosystème ne peut pas dépasser sa longueur de clé (étant donné que tout algorithme peut être cassé par force brute), mais elle peut être plus petite.
