Generación de prioridades en la estructura de datos de TREAP.

Question

Estoy estudiando la estructura de datos de TREAP.Al insertar un nodo, TREAT genere Radomly la prioridad del nodo.Pero, ¿qué pasa si la prioridad generada por 69 nodos es 13 en la imagen de arriba?

La prioridad de los padres debe ser mayor que la prioridad del niño.¿El atributo del árbol binario de TREAP choca con el atributo del montón?

quiero saber.Gracias.

Answer 1

Suponiendo que tiene TREAT de su imagen sin 69 nodos y desea agregar (69, 13) nodo:
1. split trajes existentes a 2 tratos l y r por Key 69 (Aquí, todos los viejos planes serán l) 2. crear treap m con un solo nodo (69, 13)
3. fusion m con l, entonces resultado con R
Para este caso, el nodo de caso (69, 13) se convierte en una nueva raíz, y el Old Trae será que se deja niño.

Answer 2

Si el nodo 69 tenía prioridad 13, entonces sería la raíz del árbol y el nodo 31 sería su hijo izquierdo.Los descendientes del nodo 31 serían como en su diagrama, excepto por supuesto para el nodo 69.

Siempre es posible organizar un planeador para que respete tanto el montón como las propiedades de búsqueda binaria.De hecho, en ausencia de valores iguales o prioridades iguales, solo hay una disposición posible.

La asignación aleatoria de las prioridades hace que sea probable que los planes sean equilibrados razonablemente.Puede que no esté perfectamente equilibrado, pero en el edificio lateral positivo, el trate es rápido y sin complicaciones.