Небольшие вопросы по структуре данных

Question

Я пытаюсь найти родителя узла с помощью алгоритма Крускала. Моя программа работает просто отлично, но я думаю, что слышал о методе, позволяющем повысить скорость алгоритма путем реконструкции дерева при поиске родительского узла и его подключении к родительскому узлу. Я почти уверен, что слышал об этом где-то, может быть, на лекции. Кто-нибудь может освежить мою память?

А также, учитывая количество массивов, при поиске минимального и максимального значения из определенного раздела массива, как называется дерево, которое может вычислить минимальное / максимальное значение из массива, сделав двоичное дерево, которое имеет минимальное / максимальное значение каждого массива в O (log N)?

Answer 1

Для первого вопроса вам нужна структура данных Disjoint-set .

Что касается второго вопроса, я предполагаю, что вы задали вопрос о минимальном / максимальном диапазоне запросов. Структура данных для этого - декартово дерево .

Answer 2

По поводу вашего второго вопроса: я думаю, вы говорите о куче . Куча может извлечь вам минимум или максимум в O (1) и удалить его в O (log n).

Однако существуют некоторые сложные структуры данных, предназначенные для обработки полных списков (т.е. они не предназначены для минимального / максимального доступа, в частности). Они также поддерживают доступ к минимуму и максимум одновременно. Несколько ярких примеров:

• Red-Black-Tree
• B-Tree (амортизированный O (log n))
• Splay-Tree (амортизированный O (log n))

Относительно вашего первого вопроса: Алгоритм Крускала используется для вычисления минимального связующего дерева . Но поскольку вы упоминаете «родительский узел», я предполагаю, что ваша рассматриваемая структура уже является деревом. Но если структура уже является деревом, алгоритм Крускала просто возвращает само дерево. Не могли бы вы уточнить, что вы подразумеваете под «родительским узлом»