Treap

Dans le de l'informatique, un treap est un arbre de recherche binaire qui commande les noeuds en ajoutant un attribut prioritaire de à un noeud, aussi bien qu'une clef. Les noeuds sont commandés de sorte que les clefs forment un arbre de recherche binaire et les priorités obéissent la propriété d'ordre maximum de tas. Le treap nommé est une composition du tas d'arbre et de .

Définitions

Le treap a été inventé par le Cecilia R. Aragon et le Raimund G. Seidel en 1989, cependant le crédit d'auteurs Jean Vuillemin avec étudier essentiellement la même structure de données en 1980.

si v est un descendant gauche d'u, puis de clef < de clef ;
Si v est un descendant droit d'u, alors clef > clef ;
Si v est un enfant d'u, puis priorité de <= prioritaire ;

Pendant l'insertion, la valeur est également assignée une priorité. (Cette priorité peut être aléatoire, dans ce cas l'utilisation d'un générateur de nombre pseudo-aléatoire de s'applique.) Au commencement, l'insertion procède en quelque sorte identique à l'insertion générale de l'arbre de recherche binaire . Après que ceci soit fait, les rotations d'arbre de sont utilisées pour reconstituer la propriété de tas : l'ordre de traversal de dans-ordre est invariable sous des rotations, ainsi un traversal de dans-ordre rapporte toujours le même ordre des valeurs.

Si les priorités sont non-random, l'arbre sera habituellement non équilibré ; ce plus mauvais comportement théorique de moyen-cas peut être été supérieur par un meilleur comportement de prévoir-cas, car les articles les plus importants seront près de la racine.

L'objet exposé de Treaps les propriétés des arbres de recherche binaire et du amasse

Structures de données relatives

Quand la priorité est aléatoirement assignée selon la taille de sous-arbre, la structure est connue comme arbre de recherche binaire randomisé par ou RBST.

Random links: