treap_algorithms предоставляет базовые алгоритмы для манипулирования узлами, формирующими трэп.
(1) узел заголовка поддерживается со ссылками не только на корень, но и на самый левый узел дерева, чтобы включить начало постоянного времени (), и на самый правый узел дерева, чтобы включить линейную производительность времени при использовании с общими алгоритмами набора (set_union и т. д.);
(2) когда удаляемый узел имеет двух детей, его последующий узел повторно ссылается на свое место, а не копируется, так что единственными указателями, недействительными, являются те, которые ссылаются на удаленный узел.
treap_algorithms сконфигурирован с классом NodeTraits, который инкапсулирует информацию о узле, которым нужно манипулировать. NodeTraits должен поддерживать следующий интерфейс:
Типедефы:
node: тип узла, который формирует подтяжку
node_ptr: указатель на узел
const_node_ptr Указатель на узел const
Статические функции
статический узел_ptr get_parent(const_node_ptr n)
static void set_parent(node_ptr n, node_ptr parent);
статический узел_ptr get_left(const_node_ptr n)
static void set_left(node_ptr n, node_ptr left);
статический узел_ptr get_right (const_node_ptr n)
static void set_right (node_ptr n, node_ptr right);
: header1 и header2 должны быть узлами заголовка двух деревьев.
Последствия: Свопы двух деревьев. После этого заголовок функции1 будет содержать ссылки на второе дерево, а заголовок2 будет иметь ссылки на первое дерево.
: узел и узел2 не могут быть заголовочными узлами двух деревьев.
Последствия: Замена двух узлов. После этого функциональный узел 1 будет вставлен в положение узел 2 перед функцией. Узел 2 будет вставлен в положение, которое узел 1 имел перед функцией.
: Логарифмический.
Броски: Ничего.
Примечание: Эта функция разрушит инварианты упорядочивания контейнеров, если узел 1 и узел 2 не эквивалентны согласно правилам упорядочивания.
: узел 1 и узел 2 не могут быть узлами заголовка двух деревьев с заголовком header1 и header2.
:2>: Swaps два узла. После этого функциональный узел 1 будет вставлен в положение узел 2 перед функцией. Узел 2 будет вставлен в положение, которое узел 1 имел перед функцией.
: Константа.
Броски: Ничего.
Примечание: Эта функция разрушит инварианты упорядочивания контейнеров, если узел 1 и узел 2 не эквивалентны согласно правилам упорядочивания.
: node_to_be_replaced должен быть вставлен в дерево, а new_node не должен быть вставлен в дерево.
: Заменить узел_to_be_replaced в его положении в дереве новым_node. Дерево не нуждается в перебалансировке
Сложность: Логарифмический.
: Ничего.
Примечание: Эта функция разрушит инварианты упорядочивания контейнера, если новый_узл не эквивалентен узлу_to_be_заменен согласно правилам упорядочивания. Эта функция быстрее, чем стирание и вставка узла, так как не требуется перебалансировки и сравнения. Экспериментальная функция
: node_to_be_replaced должен быть вставлен в дерево с заголовком "header" и new_node не должен быть вставлен в дерево.
: Заменить узел_to_be_replaced в его положении в дереве с новым_node. Дерево не нуждается в перебалансировке
Сложность: Постоянный.
Броски: Ничего.
Примечание: Эта функция разрушит инварианты упорядочивания контейнеров, если новый_узл не эквивалентен узлу_to_be_, замещенному согласно правилам упорядочивания. Эта функция быстрее, чем стирание и вставка узла, поскольку не требуется перебалансировки или сравнения. Экспериментальная функция
: «клонер» должен быть функциональным объектом, принимающим узел_ptr и возвращающим новый клонированный узел из него. «Утилизатор» должен взять узел_ptr и не должен выбрасывать.
Последствия: Сначала опустошается целевое дерево, вызывающее пустой узел::оператор()(const node_ptr &) для каждого узла дерева, кроме заголовка.
Затем дублируется все дерево, на которое указывает «source_header» клонирование каждого узла источника с node_ptr Cloner::operator()(const node_ptr &) для получения узлов целевого дерева. Если «клонер» бросает, то клонированные узлы-мишени утилизируются с помощью void disposer(const node_ptr &).
Комплексность: Линейное число элемента дерева-источника плюс число элементов дерева-мишени при вызове этой функции.
Броски: Если клонер-функтор бросит. Если это происходит, узлы-мишени удаляются.
: «disposer» должен быть объектной функцией, принимающей параметр node_ptr: Эффекты : Пустоты целевого дерева, вызывающие void disposer::оператор()(const node_ptr &) для каждого узла дерева, кроме заголовка.
: Линейность к числу элемента дерева-источника плюс дерево-источник. Количество элементов дерева-мишени при вызове этой функции.
Броски: Если клонер-функтор бросит. Если это происходит, узлы-мишени удаляются.
: «заголовок» должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Последствия: Возвращает узел_ptr к первому элементу, который не меньше «ключа» по «комп» или «заголовку», если этот элемент не существует.
: «заголовок» должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Последствия: Возвращает узел_ptr к первому элементу, который больше «ключа» по «комп» или «заголовку», если этот элемент не существует.
: «заголовок» должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Последствия: возвращает узел_ptr к первому элементу, который эквивалентен "ключу" согласно "комп" или "заголовку", если этот элемент не существует.
: «заголовок» должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Последствия: Возвращает пару node_ptr, делимитирующую диапазон, содержащий все элементы, которые эквивалентны «ключу» согласно «компу» или пустому диапазону, который указывает положение, где эти элементы были бы, если бы не было эквивалентных элементов.
: «заголовок» должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare может сравнить KeyType с node_ptrs дерева. Нижний ключ не должен быть больше верхнего ключа в соответствии с компом. Если «нижний_ключ» == «верхний_ключ», (слева_закрыто)
: Возвращает пару со следующими критериями:
first = low_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) if right_closed, lower_bound(upper_key) if right_closed, lower_76>: Logarithmic.
: Если бросает "comp".
Примечание: Эта функция может быть более эффективной, чем вызов upper_bound и lower_bound для low_key и upper_key.
: Экспериментальная функция, интерфейс может измениться.
: "header" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Последствия: Возвращает число элементов с ключом, эквивалентным "ключу" по "комп".
: "h" должен быть узлом заголовка дерева. NodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. NodePtrCompare сравнивает два узла_ptrs. NodePtrPriorityCompare является объектом приоритетной функции, который вызывает строгий слабый порядок, совместимый с тем, который используется для создания дерева. NodePtrПриоритет Сравните сравнивает два узла_ptrs.
Последствия: Вставляет новый_узел в дерево перед верхней границей в соответствии с "комп" и вращает дерево в соответствии с "комп".
Средняя сложность для элемента вставки является наиболее логарифмической.
: "h" должен быть узлом заголовка дерева. NodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. NodePtrCompare сравнивает два узла_ptrs. NodePtrPriorityCompare является объектом приоритетной функции, который вызывает строгий слабый порядок, совместимый с тем, который используется для создания дерева. NodePtrПриоритет Сравните сравнивает два узла_ptrs.
Последствия: Вставляет новый_узел в дерево перед верхней границей в соответствии с "комп" и вращает дерево в соответствии с "комп".
Средняя сложность для вставочного элемента является наиболее логарифмической.
Броски: Если "комп" бросает.
templatetypename,typenameNodePtrPriorityCompare>staticinert_equalconst&constnode_ptr &const и new_node,NodePtrComparecomp,
: «заголовок» должен быть узлом заголовка дерева. NodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. NodePtrCompare сравнивает два узла_ptrs. «Нет» — это узел из дерева «головы». NodePtrPriorityCompare является объектом приоритетной функции, который вызывает строгий слабый порядок, совместимый с тем, который используется для создания дерева. NodePtrПриоритет Сравните сравнивает два узла_ptrs.
Последствия: Вставляет новый_узел в дерево, используя в качестве подсказки, где он будет вставлен. Если «подсказка» находится на верхнем уровне, вставка занимает постоянное время (два сравнения в худшем случае). Вращает дерево по "pcomp".
Сложность: Логарифмическая в целом, но это амортизированное постоянное время, если новый_узел вставлен непосредственно перед "hint".
: «заголовок» должен быть узлом заголовка дерева. «pos» должен быть действительным узлом дерева (включая конец заголовка). "pos" должен быть узлом, указывающим на преемника "new_node" после вставки в соответствии с порядком уже вставленных узлов. Эта функция не проверяет «по» и это предварительное условие должно быть гарантировано абонентом. NodePtrPriorityCompare является объектом приоритетной функции, который вызывает строгий слабый порядок, совместимый с тем, который используется для создания дерева. NodePtrПриоритет Сравните сравнивает два узла_ptrs.
: Вставляет новый_узел в дерево перед "pos" и вращает дерево в соответствии с "pcomp".
: Постоянное время.
Броски: Если "pcomp" бросает, сильная гарантия.
Примечание: Если "pos" не является преемником вновь вставленных инвариантов дерева "new_node" может быть нарушено.
: "header" должен быть узлом заголовка дерева. "new_node" должен быть, согласно используемому порядку, не меньше, чем наибольший вставленный ключ. NodePtrPriorityCompare является объектом приоритетной функции, который вызывает строгий слабый порядок, совместимый с тем, который используется для создания дерева. NodePtrПриоритет Сравните два узла_ptrs.
Эффекты: Вставьте x в дерево в последнем положении и поверните дерево в соответствии с "pcomp".
: Постоянность.
Броски: Если "pcomp" бросает, сильная гарантия.
Примечание: Если "new_node" меньше, чем самые большие инварианты вставленного ключевого дерева, сломаны. Эта функция немного быстрее, чем использование «insert_before».
: "header" должен быть узлом заголовка дерева. "new_node" должен быть, согласно используемому порядку, не больше, чем самый низкий вставленный ключ. NodePtrPriorityCompare является объектом приоритетной функции, который вызывает строгий слабый порядок, совместимый с тем, который используется для создания дерева. NodePtrПриоритет Сравните два узла_ptrs.
: Вставьте x в дерево в первом положении и поверните дерево в соответствии с "pcomp".
: Сложность: Постоянное время.
Броски: Если "pcomp" бросает, сильная гарантия.
Примечание: Если "new_node" больше, чем самые низкие инварианты вставленного ключевого дерева сломаны. Эта функция немного быстрее, чем использование «insert_before».
: «заголовок» должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. Узел PtrCompare сравнивает KeyType with a node_ptr.
Последствия: Проверяет, есть ли эквивалентный узел для «ключа» в дереве по «компу» и получает необходимую информацию для реализации вставки узла постоянного времени, если нет эквивалентного узла.
Возвращает : Если есть эквивалентное значение возвращает пару, содержащую узел_ptr, к уже существующему узлу и ложному. Если эквивалентный ключ не может быть вставлен в булевой ключ возвращаемой пары и заполняет «commit_data», который предназначен для использования с функцией «insert_commit» для достижения функции вставки в постоянное время.
Сложность : Средняя сложность в лучшем случае логарифмическая.
: Если «comp» бросает.
Примечания : Эта функция используется для повышения производительности при строительстве узла дорого и пользователь не хочет иметь два эквивалентных узла в дереве: если есть эквивалентное значение, построенный объект должен быть отброшен. Много раз, часть узла, которая используется, чтобы навязать заказ, намного дешевле построить, чем узел, и эта функция предлагает возможность использовать эту часть, чтобы проверить, будет ли вставка успешной.
Если проверка успешна, пользователь может построить узел и использовать «insert_commit» для вставки узла в постоянное время. Это придает полную логарифмическую сложность вставке: check(O(log(N)) + commit(O(1)).
"commit_data" остается действительным для последующего "insert_unique_commit" только в том случае, если из набора не вставлено или стерто больше объектов.
: «заголовок» должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. NodePtrCompare сравнивает KeyType with a node_ptr. "hint" is node from the "header"'s tree.
Effects: Проверяет, есть ли эквивалентный узел "ключу" в дереве согласно "comp", используя "hint" в качестве подсказки к тому, где он должен быть вставлен, и получает необходимую информацию для реализации вставки узла постоянного времени, если нет эквивалентного узла. Если «подсказка» является верхней_связанной, функция имеет постоянную временную сложность (два сравнения в худшем случае).
Возвращает: Если есть эквивалентное значение возвращает пару, содержащую узел_ptr, к уже существующему узлу и ложную. Если эквивалентный ключ не может быть вставлен в булевой ключ возвращаемой пары и заполняет «commit_data», который предназначен для использования с функцией «insert_commit» для достижения функции вставки в постоянное время.
Сложность: Средняя сложность в лучшем случае логарифмическая, но это амортизированное постоянное время, если новый_узел должен быть вставлен непосредственно перед «подсказкой».
: Если бросает «комп».
Заметки: Эта функция используется для повышения производительности при строительстве узла : Пользователь не хочет иметь два эквивалентных узла в дереве: если есть эквивалентное значение, построенный объект должен быть отброшен. Много раз, часть узла, которая используется, чтобы навязать заказ, намного дешевле, чем узел, и эта функция предлагает возможность использовать эту часть, чтобы проверить, будет ли вставка успешной.
Если проверка успешна, пользователь может построить узел и использовать «insert_commit» для вставки узла в постоянное время. Это придает полную логарифмическую сложность вставке: check(O(log(N)) + commit(O(1)).
"commit_data" остается действительным для последующего "insert_unique_commit" только в том случае, если из набора не вставлено больше объектов.
: "header" должен быть узлом заголовка дерева. "commit_data" должно быть получено из предыдущего вызова "insert_unique_check". Никакие объекты не должны были быть вставлены или удалены из набора между «insert_unique_check», который заполнил «commit_data» и вызовом «insert_commit».
: Вставьте новый_node в набор, используя информацию, полученную из «commit_check», которую заполнил предыдущий «insert_check».
: Постоянное время.
Броски: Ничто.
Примечания: Эта функция имеет смысл только в том случае, если ранее была выполнена «insert_unique_check» для заполнения «commit_data». Не следует вставлять или стирать значение между вызовами «insert_check» и «insert_commit».
: header1 и header2 должны быть заголовками деревьев tree1 и tree2 соответственно, z незаголовочный узел tree1. NodePtrCompare - функция сравнения дерева1..
: Переносит узел "z" с дерева1 на дерево2, если дерево1 не содержит узел, эквивалентный z.
: Верно, если узел был трассферирован, ложно иначе.
: header1 и header2 должны быть заголовками деревьев tree1 и tree2 соответственно, z незаголовочный узел tree1. NodePtrCompare — функция сравнения дерева1..
Статья Class template treap_algorithms раздела The Boost C++ Libraries BoostBook Documentation Subset Reference может быть полезна для разработчиков на c++ и boost.
