Prioritätsgenerierung in der Treap-Datenstruktur

Question

Ich studiere die Treap-Datenstruktur.Beim Einfügen von Knoten generiert Treap radomly Node Priorität.Aber was ist, wenn der Wert von 69 Knoten erzeugte Priorität in dem Bild oben ist?

Die Priorität des Elternteils muss höher sein als die Priorität des Kindes.Machen Sie das Binärbaum-Attribut von Treap mit Heap-Attribut?

Ich möchte es wissen.Danke.

Answer 1

Angenommen, Sie haben Treap von Ihrem Bild ohne 69 Knoten und möchten (69, 13) Knoten hinzufügen:
1. split vorhandene Treap auf 2 Treaps L und R mit der Taste 69 (hier wird alles alte Treap l)
2. erstellen treap m mit einem einzigen Knoten (69, 13)
3. Zusammenführen m mit l, dann resultieren Sie mit r
Für diesen Fall wird der Knoten (69, 13) zu einer neuen Wurzel, und alte Treap wird das linke Kind sein.

Answer 2

Wenn der Knoten 69 Priorität 13 hatte, wäre es die Wurzel des Baums und der Knoten 31 wäre sein linkes Kind.Die Nachkommen des Knotens 31 wären wie in Ihrem Diagramm, mit Ausnahme des Node 69.

Es ist immer möglich, ein Treap anzuordnen, damit er sowohl den Heap als auch die binären Sucheigenschaften respektiert.In der Tat, wenn keine gleichwertigen Werte oder gleichen Prioritäten besteht, gibt es nur eine mögliche Anordnung.

Die zufällige Zuordnung von Prioritäten macht es wahrscheinlich, dass die Treap angemessen ausbalanciert wird.Es ist möglicherweise nicht perfekt ausbalanciert, aber auf dem positiven Seitengebäude ist die Treap schnell und unkompliziert.