Сообщение Re: Дерево с O(1) доступом по ID от 10.01.2026 11:58
Изменено 10.01.2026 12:02 Pavel Dvorkin
Re: Дерево с O(1) доступом по ID
Здравствуйте, Hоmunculus, Вы писали:
H>У меня есть дерево. То есть нулевой узел с дочерними узлами и каждый дочерний содержит свои дочерние и так далее
H>При создании ноды пользователю отдается unsigned int ID. И вот по этому ID нужен доступ за константное время. Идеально было бы как-то отразить дерево в вектор и чтоб ID был номером элемента в векторе. Но как-то криво выходит. Две структуры для одного и того же. Криво.
Ничего кривого я тут не вижу.
1. Есть некая структура из элементов (пусть дерево, а впрочем, любая) организованная на каком-то принципе, не привязанном к ID.
2. Есть необходимость доступа по ID, причем O(1)
3. Делаем массив, где ID — индекс, а элемент — указатель на элемент из (1). При удалении элемента заносим туда null. Вот и все.
Вот пример аналогичного класса, внутри которого 2 структуры
https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html
Внутри hashmap для доступа по ключу и linkedlist — список по порядку добавления.
Не совсем то, конечно, но очень похоже.
H>У меня есть дерево. То есть нулевой узел с дочерними узлами и каждый дочерний содержит свои дочерние и так далее
H>При создании ноды пользователю отдается unsigned int ID. И вот по этому ID нужен доступ за константное время. Идеально было бы как-то отразить дерево в вектор и чтоб ID был номером элемента в векторе. Но как-то криво выходит. Две структуры для одного и того же. Криво.
Ничего кривого я тут не вижу.
1. Есть некая структура из элементов (пусть дерево, а впрочем, любая) организованная на каком-то принципе, не привязанном к ID.
2. Есть необходимость доступа по ID, причем O(1)
3. Делаем массив, где ID — индекс, а элемент — указатель на элемент из (1). При удалении элемента заносим туда null. Вот и все.
Вот пример аналогичного класса, внутри которого 2 структуры
https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html
Внутри hashmap для доступа по ключу и linkedlist — список по порядку добавления.
This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).
Не совсем то, конечно, но очень похоже.
Re: Дерево с O(1) доступом по ID
Здравствуйте, Hоmunculus, Вы писали:
H>У меня есть дерево. То есть нулевой узел с дочерними узлами и каждый дочерний содержит свои дочерние и так далее
H>При создании ноды пользователю отдается unsigned int ID. И вот по этому ID нужен доступ за константное время. Идеально было бы как-то отразить дерево в вектор и чтоб ID был номером элемента в векторе. Но как-то криво выходит. Две структуры для одного и того же. Криво.
Ничего кривого я тут не вижу.
1. Есть некая структура из элементов (пусть дерево, а впрочем, любая) организованная на каком-то принципе, не привязанном к ID.
2. Есть необходимость доступа по ID, причем O(1)
3. Делаем массив, где ID — индекс, а элемент — указатель на элемент из (1). При удалении элемента заносим туда null. Вот и все.
Вот пример аналогичного класса, внутри которого 2 структуры
https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html
Внутри hashmap для доступа по ключу и linkedlist — список по порядку добавления.
Не совсем то, конечно, но очень похоже. Вместо "insrtion order" тебе нужен "ID order", ну а коль нужен O(1) — массив, а не список.
H>У меня есть дерево. То есть нулевой узел с дочерними узлами и каждый дочерний содержит свои дочерние и так далее
H>При создании ноды пользователю отдается unsigned int ID. И вот по этому ID нужен доступ за константное время. Идеально было бы как-то отразить дерево в вектор и чтоб ID был номером элемента в векторе. Но как-то криво выходит. Две структуры для одного и того же. Криво.
Ничего кривого я тут не вижу.
1. Есть некая структура из элементов (пусть дерево, а впрочем, любая) организованная на каком-то принципе, не привязанном к ID.
2. Есть необходимость доступа по ID, причем O(1)
3. Делаем массив, где ID — индекс, а элемент — указатель на элемент из (1). При удалении элемента заносим туда null. Вот и все.
Вот пример аналогичного класса, внутри которого 2 структуры
https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html
Внутри hashmap для доступа по ключу и linkedlist — список по порядку добавления.
This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).
Не совсем то, конечно, но очень похоже. Вместо "insrtion order" тебе нужен "ID order", ну а коль нужен O(1) — массив, а не список.