В поисках эффективного алгоритма дерева интервалов

Question

У меня есть набор объектов, которые хранят интервалы, заданные низким и высоким значением. Я ищу данные, которые позволят мне получить все объекты, чьи интервалы перекрываются с данной точкой в ​​режиме реального времени. Мне также нужно иметь возможность добавлять и удалять отдельные объекты как можно быстрее. Деревья интервалов на основе красно-черных деревьев имеют время вставки и удаления O (log n) и пространство O (n). Но запрос на поиск всех перекрытий занимает время O (k log n), что может быть хуже, чем поиск методом перебора, если существует много перекрывающихся интервалов. Есть ли лучший способ сделать это?

Answer 1

Деревья интервалов сделаны для этой работы. Поиск всех интервалов, которые перекрывают точку, занимает время O (k + log n), а не O (k log n).

Это «дерево центрированных интервалов», как упомянуто в вашей ссылке в Википедии. Разумно реализовать одно из них на основе красно-черных деревьев:

• Основным деревом будет красно-черное дерево. Каждый узел будет иметь свою центральную точку и список интервалов. Вы создаете новый узел всякий раз, когда вставляете новый интервал, который не перекрывает какие-либо существующие центральные точки. Вы удаляете узел всякий раз, когда удаляете все его интервалы, перекрывающие центральную точку.
• Операции вращения, выполняемые для балансировки дерева RB, потребуют от вас переместить некоторые интервалы, перекрывающие центральную точку, из дочерних узлов в их новые родители. Каждый узел должен хранить свои списки интервалов, перекрывающих центральную точку, в других красно-черных деревьях, чтобы это движение можно было выполнить за время log (n). Обратите внимание, что дерево RB выполняет амортизированное постоянное число вращений на одну вставку / удаление.

Однако ... поскольку кажется, что вы не уже сделали это с деревьями RB и RB-деревья сложные, я бы предложил вместо этого сделать то же самое с трепами: https://en.wikipedia.org/wiki/Treap

Трэпс будет намного проще, чем с деревьями RB, потому что их проще начать с, и они не требуют поворотов, чтобы поддерживать их баланс, что значительно упрощает ведение списков интервалов, перекрывающих центральную точку. Эти интервалы также могут храниться в трэпах.

Намного проще ... но все же не так просто: -)