Дерево AVL с повторяющимися значениями и двойным сравнением

Question 1

Мне нужно создать структуру данных (используя в основном деревья AVL) объектов с двумя значениями: уровень (не уникален) и идентификатор (уникален).

Мне нужно поддерживать поиск по идентификатору, печать по порядку уровней, а также объединение двух таких деревьев и поддержание этих функций с новым деревом.

У меня уже есть несколько решений на примете, но я хотел спросить о конкретном:

Будет ли работать реализация этой структуры с помощью единственного дерева AVL, в котором два узла сначала сравниваются в соответствии с их уровнем, а затем их идентификаторами? В основном я изо всех сил пытаюсь понять, как может работать слияние двух таких деревьев, особенно в случае, если у нас есть дерево A, где все объекты имеют уровень x, и дерево B, где все объекты имеют уровень y.

РЕДАКТИРОВАТЬ: Также для поиска идентификатора дополнительно будет дерево, отсортированное только по идентификатору.

Может ли этот метод сработать?

Question 2

единственное дерево AVL, в котором сначала сравниваются два узла в соответствии с их уровнем, а затем их идентификаторы?

К сожалению, нет. Если вы сделаете это, вы не сможете эффективно найти узел по его идентификатору-вам нужно будет просмотреть все возможные "уровни", которые вы не указали, поэтому я предполагаю, что они могут быть неограниченными.

Я думаю, что вы, возможно, захотите вместо этого вставить каждый узел в два отдельных дерева AVL. Одно дерево AVL будет упорядочивать узлы по уровню, другое-по их идентификатору. Все запросы, вставки, удаления и слияния можно выполнять в каждом дереве отдельно.

Другими словами, вы создадите два индекса над своими данными.

В коде:

struct Node {
    int id;
    int level;

    // by id
    int id_bf;
    Node *id_left, *id_right;

    // by level
    int level_bf;
    Node *level_left, *level_right;
};

РЕДАКТИРОВАТЬ: Также для поиска идентификатора дополнительно будет дерево, отсортированное только по идентификатору.

Тогда вы, по сути, описываете то же самое, что и я. Однако ваше дерево, отсортированное по составному (level, id) ключ расточителен; все, что вам нужно, - это дерево, отсортированное по (level) и дерево, отсортированное по (id) (скалярные ключи). Среди предоставленных вами операций нет необходимости сортировать по (level, id) и (id).

Yakov Galka · Answer 1 · 2021-11-23T19:29:44

единственное дерево AVL, в котором сначала сравниваются два узла в соответствии с их уровнем, а затем их идентификаторы?

К сожалению, нет. Если вы сделаете это, вы не сможете эффективно найти узел по его идентификатору-вам нужно будет просмотреть все возможные "уровни", которые вы не указали, поэтому я предполагаю, что они могут быть неограниченными.

Я думаю, что вы, возможно, захотите вместо этого вставить каждый узел в два отдельных дерева AVL. Одно дерево AVL будет упорядочивать узлы по уровню, другое-по их идентификатору. Все запросы, вставки, удаления и слияния можно выполнять в каждом дереве отдельно.

Другими словами, вы создадите два индекса над своими данными.

В коде:

struct Node {
    int id;
    int level;

    // by id
    int id_bf;
    Node *id_left, *id_right;

    // by level
    int level_bf;
    Node *level_left, *level_right;
};

РЕДАКТИРОВАТЬ: Также для поиска идентификатора дополнительно будет дерево, отсортированное только по идентификатору.

Тогда вы, по сути, описываете то же самое, что и я. Однако ваше дерево, отсортированное по составному (level, id) ключ расточителен; все, что вам нужно, - это дерево, отсортированное по (level) и дерево, отсортированное по (id) (скалярные ключи). Среди предоставленных вами операций нет необходимости сортировать по (level, id) и (id).

Спасибо за ответ, к сожалению, я просто забыл упомянуть, что дополнительно у меня будет дерево, отсортированное по идентификатору для этой функции. Я подумал о вашем решении,мне просто было интересно узнать об этом конкретном решении, которое мне сказал одноклассник, и я думаю, что оно не сработает из-за слияния,
@user3917631: дерево, отсортированное по (уровню, идентификатору), также сортируется по (уровню). Таким образом, если у вас есть дерево, отсортированное по (идентификатору) в дополнение к любому из них, вы сможете эффективно выполнять операции, как я описал. Немного расточительно сортировать по (уровню, идентификатору), если все, что вам нужно, - это (уровень).
Я знаю, я спрашиваю только из интереса, может ли это сработать? Возможно ли, чтобы два дерева были отсортированы по (уровню, идентификатору) обоим целым числам и объединили их в O(n) (n количество объединенных узлов).
@user3917631: да, это возможно, и ничем не отличается от объединения двух деревьев, отсортированных по чему-либо еще. Деревья бинарного поиска основаны на сравнении, поэтому им все равно, что вы используете для своего ключа, если это полностью упорядоченный набор. Кортеж целых чисел-это набор. Статья Википедии о деревьях AVL описывает, как эффективно выполнять слияние; там это называется объединением. Однако для этого вы можете сохранить высоту узла вместо коэффициента баланса.

Дерево AVL с повторяющимися значениями и двойным сравнением

Вопрос

Лучший ответ

На других языках

Эта страница на других языках

Популярное в этой категории

Популярные вопросы в этой категории