Concept
Self-balancing binary search tree
Concepts associés (26)
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.
Treap
En 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 bicolore
Un 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).
Arbre splay
Un 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.
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.
Skip list
En informatique, et plus précisément en algorithmique, une skip list, ou liste à enjambements, ou liste à saut, est une structure de données probabiliste, à base de listes chaînées parallèles. La plupart de ses opérations s'effectuent en temps O(log n) avec une grande probabilité, où n est le nombre d'éléments contenus dans la liste. Les skip lists ont été inventées par William Pugh, d'abord présentées dans un rapport technique en 1989 puis présentées dans une publication en 1990.
Complexité en temps
En algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat. Habituellement, le temps correspondant à des entrées de taille n est le temps le plus long parmi les temps d’exécution des entrées de cette taille ; on parle de complexité dans le pire cas. Les études de complexité portent dans la majorité des cas sur le comportement asymptotique, lorsque la taille des entrées tend vers l'infini, et l'on utilise couramment les notations grand O de Landau.
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 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.
Ensemble (informatique)
En informatique, un ensemble ou set est un type abstrait qui peut stocker certaines valeurs, sans ordre particulier, et sans répétition. Il s'agit d'une mise en œuvre informatique de la notion mathématique d'ensemble fini. Un ensemble stocke des valeurs, sans ordre défini, et ne contient pas de données en double (la tentative d'insertion d'une donnée déjà présente est sans effet). Contrairement à la plupart des autres types de collections les ensembles sont plus utilisés pour tester l'appartenance d'une valeur à cet ensemble que pour en extraire des données.