Génération de priorité dans la structure de données Treap

Question

J'étudie la structure de données Treap.Lors de l'insertion de nœud, le Treap générera radiculément la priorité du nœud.Mais que si la priorité générée par 69 nœuds est 13 dans l'image ci-dessus?

La priorité des parents doit être supérieure à la priorité de l'enfant.L'attribut arborescence binaire de Treap est-elle en collision avec l'attribut HEAP?

Je veux savoir.Merci.

Answer 1

En supposant que vous ayez le TREAP de votre photo sans 69 nœud et souhaitez ajouter (69, 13) Node:
1. SPLIT TAAP existant à 2 Treaps L et R par clé 69 (ici tout le vieux Teap sera l)
2. CREATEZ TAAP M avec noeud unique (69, 13)
3. fusionné m avec l, puis entraîner avec R
Pour ce cas, le nœud (69, 13) devient une nouvelle racine et le vieux Treap sera celui de l'enfant à gauche.

Answer 2

Si le nœud 69 avait la priorité 13, alors ce serait la racine de l'arbre et du nœud 31 serait son enfant gauche.Les descendants du noeud 31 seraient comme dans votre diagramme, sauf bien sûr pour le nœud 69.

Il est toujours possible d'organiser un TAAP afin qu'il respecte à la fois le tas et les propriétés de recherche binaires.En fait, en l'absence de valeurs égales ou d'égales prioritaires, il n'y a qu'un seul arrangement possible.

L'affectation aléatoire des priorités permettra probablement que le Treap soit raisonnablement équilibré.Il pourrait ne pas être parfaitement équilibré, mais sur le bâtiment du côté positif, le Treap est rapide et simple.