Generazione prioritaria nella struttura dei dati di Treap

Question

Sto studiando la struttura dei dati dei treni.Quando si inserisce il nodo, Treap Radomly genera la priorità del nodo.Ma cosa succede se la priorità generata da 69 nodi è 13 nella foto sopra?

La priorità del genitore deve superare la priorità del bambino.Attributo Tree Binary Treap si scontra con l'attributo heap?

Voglio sapere.Grazie.

Answer 1

Supponendo che tu abbia Treap dalla tua foto senza 69 nodo e vuoi aggiungere (69, 13) nodo:
1. Split Esistendo Treap a 2 Treap L e R da Key 69 (qui tutto il vecchio Treap sarà L)
2. Crea Treap M con nodo singolo (69, 13)
3. Unisci M con L, quindi risulta con R
Per questo nodo caso (69, 13) diventa una nuova radice, e il vecchio Treap sarà il figlio sinistro.

Answer 2

Se il nodo 69 aveva priorità 13, allora sarebbe la radice dell'albero e del nodo 31 sarebbe il suo figlio sinistro.I discendenti del nodo 31 sarebbero come nel tuo diagramma, tranne ovviamente per il nodo 69.

È sempre possibile organizzare un trep in modo che rispetti sia il mucchio che le proprietà di ricerca binarie.Infatti, in assenza di valori uguali o di pari priorità, c'è solo un possibile accordo.

L'assegnazione casuale delle priorità rende probabile che il Treap sarà ragionevolmente equilibrato.Potrebbe non essere perfettamente bilanciato, ma sul lato positivo la costruzione del lato è veloce e senza complicazioni.