Генерация приоритетов в структуре данных Treap
Я изучаю структуру данных Treap. При вставке узла трепа генерирует приоритет узла. Но что если сгенерированный приоритет 69 узла равен 13 на рисунке выше?
Приоритет родителя должен быть выше приоритета ребенка. Атрибут бинарного дерева treap конфликтует с атрибутом кучи?
Я хочу знать. Благодарю.
2 ответа
Предполагая, что у вас есть изображение с картинки без узла 69, и вы хотите добавить (69, 13) узел:
1. Разделите существующий треп на 2 трепа L и R по ключу 69 (здесь весь старый треп будет L)
2. Создайте трэп М с одним узлом (69, 13)
3. Объедините M с L, затем приведите с R
В этом случае узел (69, 13) становится новым корнем, а старый триап будет его дочерним.
Если бы узел 69 имел приоритет 13, то он был бы корнем дерева, а узел 31 был бы его левым потомком. Потомки узла 31 будут такими же, как на вашей диаграмме, за исключением, конечно, узла 69.
Всегда можно расположить трэп так, чтобы он учитывал как свойства кучи, так и свойства двоичного поиска. Фактически, при отсутствии равных ценностей или равных приоритетов возможна только одна договоренность.
Случайное распределение приоритетов делает вероятным, что треп будет разумно сбалансирован. Это может быть не совсем сбалансировано, но с положительной стороны, построение трепа быстрое и несложное.