Описание тега treap
Treap - это форма структуры данных двоичного дерева поиска, которая поддерживает динамический набор упорядоченных ключей и позволяет выполнять двоичный поиск среди ключей.
1
ответ
Что я должен выбрать для простого в коде сбалансированного бинарного дерева поиска?
Я хотел бы знать, какой сбалансированный BST будет легко кодировать на C++, и при этом его сложность будет примерно равна O(logn). Я уже пробовал деревья Red Black, но хотел бы найти альтернативу, которая менее сложна для кодирования. Я работал с Tr…
27 июл '14 в 14:21
0
ответов
Количество элементов в [L,R] больше чем X с использованием неявного трэпа
Мне нужно обработать три типа запросов к данному массиву. Назначение х в сегмент [L , R] Обратный сегмент [L , R] Найти количество элементов в [L , R] которые больше чем x Я знаю, как сделать 1 и 2 типа, используя неявный трепет, но как я могу обраб…
14 окт '17 в 11:33
1
ответ
Алгоритм Прима с Трепами
Может ли алгоритм Прима быть реализован с помощью трэпов, чтобы ускорить выполнение, потому что нормальная куча создаст проблему при обновлении значения ключей при сохранении вершин в кучах, что в противном случае потребовало бы пространства O(V) дл…
13 апр '14 в 06:31
1
ответ
Как Treap помогает обновить эту упорядоченную очередь?
У меня возникают проблемы с пониманием этого решения проблемы на HackerRank. Пожалуйста, смотрите код решения ниже, по-видимому, Кимиюки Онака. Проблема: дан список уникальных номеров, и m запросы типа "move the current ith to jth elements (l,r) to …
07 июн '16 в 17:19
2
ответа
Генерация приоритетов в структуре данных Treap
Я изучаю структуру данных Treap. При вставке узла трепа генерирует приоритет узла. Но что если сгенерированный приоритет 69 узла равен 13 на рисунке выше? Приоритет родителя должен быть выше приоритета ребенка. Атрибут бинарного дерева treap конфли…
30 июл '14 в 04:22
3
ответа
Когда полезен трепан?
В какой ситуации Treap является оптимальной структурой данных для использования? Я искал ответы на этот вопрос, но на самом деле не нашел ничего конкретного. Есть другой stackru вопрос о том, когда использовать треп, но там нет примеров из реальной …
15 мар '15 в 16:10
0
ответов
Удалить ключ в трепе
Я учусь о трепе. Я застрял при вставке и стирании ключей в этих структурах данных. Я хочу, чтобы он работал как мультимножество, но я столкнулся с некоторыми проблемами. Если я вставлю те же ключи в Treap, когда я захочу удалить ключ "x", он также у…
23 ноя '18 в 13:01
1
ответ
Что быстрее на практике: Treap или Splay tree?
Я выучил как Treap, так и Splay tree и решил несколько проблем, используя их. Теоретически, их сложность в среднем равна O(log n), но в худшем случае сложность Treap равна O(n), а у Splay Tree амортизируется O(log n). В каком случае наихудший случай…
06 янв '18 в 21:17
1
ответ
Ошибка при удалении трэпа
У меня есть Procudere удаляет для моего трепа, и на линии p=merge(l, merge(m, rs)); у меня ошибка error: non-const lvalue reference to type 'nodeptr' (aka 'node *') cannot bind to a temporary of type 'nodeptr'Так вот реализация удалений и слияния no…
11 дек '13 в 19:41
1
ответ
Высота бинарного дерева в Java без параметров
Я знаю, что есть много функций, которые можно найти там, где вы можете легко получить высоту дерева двоичного поиска, рекурсивно вызывая функцию и используя корень узла в качестве параметра каждый раз для левого и правого поддерева. Но что я должен …
15 окт '13 в 01:26
4
ответа
Treap с неявными ключами
Существует структура данных, называемая treap: это рандомизированное дерево двоичного поиска, которое также является кучей случайно генерируемых так называемых "приоритетов". Существует вариант этой структуры, где ключи неявные, они не хранятся в де…
16 авг '10 в 22:18
1
ответ
В чем полезность структуры данных Treap?
В настоящее время я изучаю сложные структуры данных и натолкнулся на странную структуру данных под названием Treap. Я понимаю, что такое Treap, но не могу найти его полезным в сценарии правильного использования. Почему вы должны использовать такую …
29 мар '18 в 19:32
0
ответов
Сегмент неисправности в некоторых особых неизвестных случаях, сводящих меня с ума
Я отлаживал весь день, и я действительно полностью потерян. Помогите! Я тестировал множество случаев локально в Visual Studio. Работает нормально. Но в системе онлайн-судейства нашей школы есть несколько случаев, сообщающих RE(код выхода 6), что озн…
27 дек '15 в 12:44
0
ответов
Как этот код генерирует случайное число?
В настоящее время я изучаю трэп, и я пришел к реализации, в которой парень использовал какой-то странный способ генерировать случайные числа для приоритета. Я не могу его получить. Кто-нибудь возражает объяснить мне, как это работает. struct xor_128…
02 ноя '15 в 09:26
0
ответов
Проблемы с трепом (без неявных ключей)
Извините за мой плохой английский. Мне нужно удалить ключ в моем трепе, но моя реализация не позволит мне это сделать. Более ясно, если мой треп выглядит так: 2 3 5 5 5 8 10 12 12. Я хочу стереть ключ '5', чтобы он выглядел так: 2 3 5 5 8 10 12 12 /…
25 ноя '18 в 01:34
1
ответ
Какая структура данных наиболее подходит для реализации словаря?
Я должен написать программу-словарь в качестве семестрового проекта для курса бакалавриата по структурам данных и алгоритмам, и я должен найти наиболее подходящее решение (структура данных) для этой проблемы. Я решил использовать хеш-таблицу или Tri…
26 дек '15 в 17:38
2
ответа
Как генерировать случайные приоритеты для узлов Treap?
В большинстве примеров, которые я видел в Интернете, считается, что существует какой-то внешний генератор случайных чисел, который будет выдавать случайные (разные!) Приоритеты. Из того, что я помню, был метод для фактической генерации приоритетов с…
28 апр '15 в 02:56
8
ответов
Почему вставка в мое дерево быстрее при сортированном вводе, чем при произвольном вводе?
Теперь я всегда слышал, что двоичные деревья поиска быстрее строятся из случайно выбранных данных, чем из упорядоченных данных, просто потому, что упорядоченные данные требуют явной перебалансировки, чтобы поддерживать высоту дерева на минимуме. Нед…
13 мар '10 в 08:21
6
ответов
Когда использовать трепан
Может ли кто-нибудь привести реальные примеры того, когда лучшим способом хранения ваших данных является treap? Я хочу понять, в каких ситуациях трэп будет лучше, чем кучи и древовидные структуры. Если это возможно, приведите несколько примеров из р…
15 апр '13 в 06:57
1
ответ
Используя "Treap", чтобы сравнить два набора
Я хочу использовать структуру Treap, но я плохо знаком с этим типом дерева. У меня есть два набора, и я хочу написать метод, чтобы сравнить их с Treap. Этот метод должен возвращать значение, которое показывает сходство двух наборов. (Моя работа - из…
16 июн '13 в 08:39