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. Après une séquence quelconque d'insertion et de suppression des clés, la forme de l'arbre est une variable aléatoire dont la distribution de probabilité est la même que celle d'un arbre binaire aléatoire ; en particulier, sa hauteur est proportionnelle au logarithme de son nombre de nœuds selon une forte probabilité, de sorte que chaque opération de recherche, d'insertion, ou de suppression s'effectue en un temps logarithmique. L'arbretas a été décrit pour la première fois par Cecilia R. Aragon et Raimund Seidel en 1989; son nom est un mot-valise issu de l'arbre et du tas. Il s'agit d'un arbre binaire généré à partir d'un ensemble de nombres dans lequel chaque clé se voit assignée une priorité numérique choisie aléatoirement. Tout comme pour n'importe quel arbre binaire de recherche, l'ordre infixe sur les nœuds est le même que celui des clés ordonnés. La structure d'un arbre est déterminée par la restriction qu'il possède la propriété de tas: c'est-à-dire que, la priorité pour tout nœud interne doit être plus grande que la priorité de ses enfants. Ainsi, le nœud racine doit être le nœud de plus grande priorité, et ses sous-arbres gauches et droits sont formés de la même manière à partir des éléments respectivement plus petits et plus grand que l'élément stocké dans la racine. Une manière équivalente de définir un arbretas et de dire qu'il est formé en insérant les nœuds selon leur ordre de priorité, de la plus grande à la plus petite dans un arbre binaire de recherche, sans faire aucun rééquilibrage.