Geração de prioridade na estrutura de dados de TREAP

Question

Estou estudando a estrutura de dados do TREAP.Ao inserir o nó, o TREAP gere a prioridade do nó.Mas e se 69 a prioridade gerada do nó for 13 na foto acima?

A prioridade dos pais deve maior que a prioridade da criança.O atributo de árvore binário do TREAP colide com o atributo heap?

Eu quero saber.Obrigado.

Answer 1

Supondo que você tenha Treap da sua foto sem 69 nó e deseja adicionar (69, 13) nó:
1. Split Treap existente para 2 Treaps L e R por chave 69 (Aqui todos os antigos Treap serão l) 2. Criar Treap M com nó único (69, 13)
3. Merge M com L e, em seguida, resulte com R Para este caso nó (69, 13) torna-se uma nova raiz, e o Old Treap será a criança esquerda.

Answer 2

Se o nó 69 teve prioridade 13, então seria a raiz da árvore e o nó 31 seria a sua criança esquerda.Os descendentes do nó 31 seriam como no seu diagrama, exceto, exceto para o nó 69.

É sempre possível organizar um TREAP para que ele respeite tanto o heap quanto as propriedades de busca binária.De fato, na ausência de valores iguais ou prioridades iguais, há apenas um arranjo possível.

A atribuição aleatória de prioridades torna provável que o TREAP seja razoavelmente equilibrado.Pode não ser perfeitamente equilibrado, mas no edifício lateral positivo, o TREAP é rápido e descomplicado.