Создание приоритета в структуре данных TREAP

Question

Я изучаю структуру данных TREAP.При вставке узла приоритет приоритет узела TREAP RADOMLY.Но что, если сгенерированный приоритет 69 узлов - 13 на рисунке выше?

Приоритет родителя должен выше, чем приоритет ребенка.Бинарный атрибут двоина TREAP сталкивается с атрибутом кучи?

Я хочу знать.Спасибо.

Answer 1

Предполагая, что вы не содержали фотографию без 69 узлов и хотите добавить (69, 13) узел:

1. <Сильные> Сплит Существующие TREAP до 2 TREAP L и R по ключу 69 (здесь все старые трейп будет l) 2. Создать FREAP M с одним узлом (69, 13) 3. Слияние M с L, а затем привести к R
Для этого случая узел (69, 13) становится новым корнем, а старый трейп будет левым ребенком.

Answer 2

Если узел 69 имел приоритет 13, то будет корнем дерева и узла 31 был бы его левым ребенком.Потомки узла 31 были бы на вашей диаграмме, за исключением курса для узла 69.

Всегда возможно организовать трейп, чтобы он уважает как кучу, так и двоичные поисковые свойства.На самом деле, в отсутствие равных ценностей или равных приоритетов, существует только одно возможное расположение.

Случайное присвоение приоритетов введет вероятность того, что TREAP будет разумно сбалансированным.Это может быть не совсем сбалансировано, но на позитивном боковом здании трейп быстро и несложно.